Changing std:sort at Google’s scale and beyond
danlark.org
danlark.org
Go will use pdqsort in next release - https://news.ycombinator.com/item?id=31106157 - April 2022 (112 comments)
Next week I will hold another talk in the Dutch seminar on data systems design (https://dsdsd.da.cwi.nl/) on glidesort, a new stable sorting algorithm I've been working on. It is a combination of adaptive quicksort (like pdqsort, fully adaptive for many equal elements) and an adaptive mergesort (like timsort, fully adaptive for long pre-sorted runs). It is the first practical implementation of an algorithm I'm aware of that's fully adaptive for both. Like pdqsort it uses modern architecture aware branchless sorting, and it can use an arbitrary buffer size, becoming faster as you give it more memory (although if given a constant buffer size it will degrade to O(n (log n)^2) in theory, in practice for realistic workloads it's just a near-constant factor (c ~<= 3-5) slower).
The source code isn't publish-ready yet, I have to still do some extra correctness vetting and testing, and in particular exception-safety is still not yet fully implemented. This is important because I wrote it in Rust where we must always give back a valid initialized array, even if a comparison operator caused a panic. But I do have some performance numbers to quote, that won't significantly change.
For sorting 2^24 randomly shuffled distinct u32s using a buffer of 2^23 elements (n/2), glidesort beats Rust's stdlib slice::sort (which is a classic timsort also using a buffer of n/2) by a factor of 3.5 times. When stably sorting the same numbers comparing only their least significant 4 bits, it beats stdlib slice::sort by 12.5 times using 6.5 times fewer comparisons, both numbers on my Apple M1 Macbook. All of this is just using single-threaded code with a generic comparison function. No SIMD, no threads, no type-specific optimizations.
Finally, glidesort with a buffer size of >= n/2 is faster than pdqsort.
I've been doing a lot of work on sorting[2], in particular working to hybridize various approaches better. Very much looking forward to seeing how glidesort works.
[0] https://github.com/scandum/fluxsort
[1] https://github.com/scandum/crumsort
[2] https://mlochbaum.github.io/BQN/implementation/primitive/sor...
In particular, I was inspired by three things from scandum:
1. fluxsort's out-of-place stable partitioning. From this I got reminded that not only is out-of-place stable partitioning a thing, it's highly competitive. I've always had this as an idea in the back of my mind, but never went through with it because I kept getting discouraged by C++'s distinction of moving to uninitialized memory vs. moving into a moved-from value (which is why I implemented glidesort in Rust).
2. quadsort's "ping pong merge", which reduces unnecessary memcpys by merging both on the way out and on the way in the original array. I did have this idea before, but always dismissed it because I thought keeping track of what's where would be a massive pain. Simply waiting until there's 4 things to merge eliminates this problem and is just genius.
3. quadsort's "branchless parity merge", which merges from both ends of the array if the merge is perfectly balanced. I make no claim that I thought of this, it's just genius. I had two key takeaways from this: you can make some very fast small sorting algorithms with merges, and interleaving loops to reduce data dependencies are significantly faster.
So I combined #1 & #3 into what I call bidirectional stable partitioning, where I partition from both sides of the array into an out-of-place buffer through interleaved loops.
I extended the adaptiveness and applicability of #2 heavily by replacing the 'merge' operation in powersort (https://arxiv.org/abs/1805.04154) with a 'virtual merge' operation that delays merges until necessary. This is also what allows me to use quicksort in a bottom-up adaptive mergesort, because I don't eagerly sort small runs! Instead I simply keep unsorted runs around, 'merging' unsorted runs simply by concatenating them - purely in bookkeeping.
I heavily extended 3 for the mergesort part by realizing we don't need perfectly balanced merges, we can just take the `min` of the two runs and start off with a merge from both sides, and then look further. I also did more interleaving by doing a binary search to compute independent parallel merges where sensible, and interleaving those loops.
As a quick preview, here is a visualization of glidesort using a buffer size of n/2, where I have artificially limited the concatenation of unsorted runs to n/8 so that it won't just look only like quicksort, and both the quicksort and mergesort aspects are shown: https://cdn.discordapp.com/attachments/273539705595756544/96...
Stepped through the video a few times at 1/4 speed. The n/8 thing is a bit confusing, first because I didn't read it and second because it makes it hard to tell a partition result from the beginning of the next segment. I think I can follow what's going on, but I don't get the purpose of the bidirectional partition. It doesn't use less memory, does it? So is there something to do with fitting in with mergesort better? I'm not familiar with powersort; I'll read up on it.
Nope, it does the same amount of comparisons, same number of operations, same memory, etc. What it does do is it allows you to interleave two independent loops, which is also what makes the parity merge fast (I think scandum misidentifies the loop unrolling for this effect for large arrays - you can loop unroll merging large arrays either way - for small constant-size merging it is important however).
A modern CPU has a very long pipeline, and even though we like to pretend all instructions are one cycle with no latency, in reality there are real latencies to instructions and memory accesses, and multiple instructions can be executed in the same cycle. Since each iteration of the partition depends on the previous one (which pointer did we increment? we have to know before we can execute the next store), you can hide these latencies better if you interleave two independent loops. In addition you can use more instruction-level parallelism.
You can of course make partitioning embarrassingly parallel, look at IPS4o for that. But it is vastly more complicated, and involves overhead shuffling blocks after the partition.
I edited my comment to reflect this, I can see how it could've been misinterpreted. It was not my intention to deceive.
I am working in MapReduce/Data-pipelining/Dataproc efficiency internally and externally. In cloud you can check out Google Cloud Dataflow
We are working closely with general efficiency and bare metal teams, yes :). They definitely do a fascinating work. This one was my 20% project together with the google efficiency team
Yes.
> What about just an O(log N) size buffer?
That would effectively just be a constant sized buffer. Honestly O(log N) factors where N is the size of the input are overrated and are probably best seen as a constant factor. Like, even if you're sorting 16 gigabytes of 32-bit floats, log2 N is still just 32.
But on 64-bit machines log2(N) is always <= 64, so I just allocate a 64-element array of 4 word structs on the stack.
I think it's just much more productive and predictive to say that "glidesort has performance X when using a 512-element buffer" than "glidesort has performance X when using a c log (n) buffer".
FWIW, the 360p mp4 (youtube-dl -f18) encoding of this seems to be truncated ("Got server HTTP error: Downloaded 989757 bytes, expected 61794145 bytes."), so you might want to try and get youtube to reencode it. (-f22/720p works fine, so it's probably a transient error rather than a problem with your original upload.)
Towards the end of this post, the author mentions a bunch of places where std::sort() blows up if your data or your sort rule doesn't exhibit strict weak ordering. In some cases you get a bad sort, which feels fair enough since you violated the rules the sort algorithm is relying on, but in others it literally has Undefined Behaviour in C++.
Notably Rust's sort() and unstable_sort() do not have this problem, because of course these are safe Rust, and safe Rust doesn't have Undefined Behaviour. But why can this work?
First up, one bullet which gets dodged is that Rust's floating point types (f32 and f64) are not Ord. Rust acknowledges that NaN != NaN and therefore we can't expect to go around sorting a slice of floating point values. In C++ that's on the programmer, in C++ the fact you can write a < b means that type counts as ordered, even though it trivially isn't for several built-in types. So if you simply naively try to sort an [f32] Rust says you can't because it isn't Ord, you will need to write a lambda or whatever to Order these f32s and then if some of them are NaN your lambda is responsible for deciding what to do about that.
But even if we insist on getting in harm's way, safe Rust promises to protect us anyway. For example if I make an array of a thousand misfortunate::OnewayGreater<u8>s they're only one byte each, yet they all insist they're Ordered greater than each other and even than themselves, Rust's sort() doesn't cause Undefined Behaviour on this input. It may never succeed, since all the elements to be "sorted" insist they're greater than each other, but it definitely won't segfault, trash unrelated memory or cause chaos.
Running forever is pretty chaotic.
This argument feels like a difference in semantics, rather than any actual added safety.
Rust will happily let you run the sort with an unstable comparator, which then leads to undefined behavior in the sense that the final sorting order, or whether the sort completes at all, is not defined by the standard and is instead dependent on the internal implementation. The fact that this is not called "undefined behavior" in Rust is a difference in semantics only.
Added safety would be if Rust could detect the fact that the comparator is unstable and tell the user so they could fix the bug in their comparator.
What is perhaps more relevant here than any safety provided by the Rust language is that there is only one Rust compiler. Relying on internal implementation details of that compiler is much more accepted, and the distinction between "internal compiler implementation detail" and "behavior defined by the standard" is a lot less relevant than it is in C or C++, which have many different implementations.
If Rust is able to define its sort() as only ever affecting the array passed to it, with the possibility of looping forever, then that is very well defined behaviour in comparison.
One example of unspecified behaviour is the order in which function call parameters are evaluated (meaning any order is OK, and it could vary from call to call).
One example of implementation-defined behaviour is the value of sizeof(int).
You can't avoid allowing this in a general purpose sort. If Rust wanted to insist that the comparator must be "stable" in this sense, it would have to do that by defining an unsafe trait (maybe "ReallyReallyOrdered") implementations of which promise they're correct (hence the "unsafe" requirement, a safe trait like Ord can't promise anything the compiler can't prove).
There's no difference in semantics at work. In C++ sort() with a bad comparator has Undefined Behaviour and so might do absolutely anything, in Rust its behaviour is defined in a way you simply don't like.
> Added safety would be if Rust could detect the fact that the comparator is unstable and tell the user so they could fix the bug in their comparator.
This could only be a best-efforts check, since if you were to try a.cmp(b) a million times, nothing stops a's comparator from counting and giving a different answer on the next try after your millionth check.
I always meant to get around to writing some sort of misfortunate::RandomOrder (but with a cleverer name, maybe Tombola or ManekiNeko ?) which would exhibit completely random ordering, again this isn't methodically detectable, a detector can only have probabilistic success.
Unlike C++, all Rust's built-in types have proper behaviour here, so if you run into trouble either you're using a third party type, or a third party comparator for the sort itself, and since there is never Undefined Behaviour you can track down the problem.
Timsort https://en.wikipedia.org/wiki/Timsort :
> In the worst case, Timsort takes O(n log n) comparisons to sort an array of n elements. In the best case, which occurs when the input is already sorted, it runs in linear time, meaning that it is an adaptive sorting algorithm. [3]
> It is advantageous over Quicksort for sorting object references or pointers because these require expensive memory indirection to access data and perform comparisons and Quicksort's cache coherence benefits are greatly reduced. [...]
> Timsort has been Python's standard sorting algorithm since version 2.3 [~2002]. It is also used to sort arrays of non-primitive type in Java SE 7,[4] on the Android platform,[5] in GNU Octave,[6] on V8,[7] Swift,[8] and Rust.[9]
Sorting algorithm > Comparison of algorithms https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_o...
Schwartzian transform https://en.wikipedia.org/wiki/Schwartzian_transform :
> In Python 2.4 and above, both the sorted() function and the in-place list.sort() method take a key= parameter that allows the user to provide a "key function" (like foo in the examples above). In Python 3 and above, use of the key function is the only way to specify a custom sort order (the previously supported cmp= parameter that allowed the user to provide a "comparison function" was removed). Before Python 2.4, developers would use the lisp-originated decorate–sort–undecorate (DSU) idiom,[2] usually by wrapping the objects in a (sortkey, object) tuple
Big-O Cheatsheet https://www.bigocheatsheet.com/
Quicksort in Python 7 ways (and many other languages) on RosettaCode: https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Py...
https://github.com/fffaraz/awesome-cpp#debug
A standard way to benchmark and chart {sorting algorithms, web framework benchmarks,} would be great.
The TechEmpower "framework overhead" benchmarks might have at least average case sorting in there somewhere: https://www.techempower.com/benchmarks/#section=data-r20&hw=...
awesome-theoretical-computer-science > Machine Learning Theory, Physics; Grover's; and surely something is faster than Timsort: https://github.com/mostafatouny/awesome-theoretical-computer...
> The interdicplinary of Mathematics and Computer Science, Distinguisehed by its emphasis on mathemtical technique and rigour.
(Perhaps a witty satire on the reputation of mathmos for being godawful at anything literary...)
Update: I confused Timsort with IntroSort. I should have googled before posting ...
For starters, it's a stable sort, which excludes quicksort right out the gates.
Second, the primary hypothesis of timsort is that real-world data is non-random, timsort is biased for partially or almost-sorted sequences, which it can sort in as low as O(n). That would be the point westurner was making, timsort's creation is very much predicated on "really benchmark sorts on different data patterns".
Third, for very short sequences (also a common situation) it's an insertion sort, which is extremely efficient due to the low overhead (even more so combined with the adaptivity which insertion sort also has).
Negative, it excludes in-place quicksort but out-of-place quicksort can be stable just fine.
> Third, for very short sequences (also a common situation) it's an insertion sort, which is extremely efficient due to the low overhead (even more so combined with the adaptivity which insertion sort also has).
Every modern quicksort implementation also does this (or a similarly efficient smallsort).
Maybe for the third point, but once again, every implementation does this. For the first point, absolutely not. Just because in-place partitioning is often the only variant described, out-of-place partitioning is absolutely just quicksort, not an extension.
> Quite possibly you can extend quicksort similar to how timsort extended mergesort
Please see my top comment in this thread - I have done exactly that. Or rather, I have extended powersort (which is very similar to timsort) with quicksort.
> We saw a pattern of sort+resize a lot.
These seem like good opportunities for clang-tidy checks.
I find the pragmatism worthy of praise. I've been meaning to start blogging since forever but I keep planning and researching about blog platforms/tools and never get to the point.
I found Jekyll and never looked back.
Once you have the resulting list, the indices are sorted, then assigning each num_solid value to that index would result in the list being constant, and then could be sorted to give such worst case behavior.
I wish the article was more clear on this.
Edit: just wanted to clarify that the point I'm trying to make here is that if you want to ask someone if they've memorized the answer to that question, go ahead and ask it in a technical interview, because the real well-considered answer looks like the linked article, and my honest non-smartass answer is that one should use the library function and not try to implement it themselves until they've done sufficient research into the problem to prove to a reasonable degree that they indeed do need to re-implement sort() and that it's in the best interests of the business to fund such a project.
Would love to read this over the phone to a recruiter and have them tell me that it's not what they have on their sheet.
Being able to put together a sort from compares and swaps (or inserts, or whatever you have available) is at least evidence that you won't either panic or storm off when the tools you have are something less than ideal.
> [...] is at least evidence that you won't either panic or storm off when the tools you have are something less than ideal.
Maybe. Maybe not? Most of the time our tools are far from ideal anyway. Most of the time the important factors are a direct consequence of management/leadership/team. (Deadlines, feature creep, crazy engineering practices - eg. hand rolling sort, crazy interview practices - 8 hours of hardcore interview or whatnot, and so on.)
* I always have access to a decent stdlib and would not need to implement sort itself
* But I do need to design and implement bespoke algorithms
The algorithms are nothing groundbreaking - they're things like how to grow and shrink a buffer when reading from a socket. But I'd struggle if I didn't know a few examples of different algorithms and how to think about their trade offs, and basic sorting algorithms (not like this article!) are ideal for that. Maybe I'm doing unusual work but it doesn't really feel like it.
Edit: To put it another way: in a past job, we had some unfortunate examples of people being hired whose ability to work with algorithms was sadly not up to scratch, and it had a serious practical impact on their ability to do their job. If they had been asked a few questions about sorting algorithms in their interview then that could have been avoided.
Of course, knowing about specific algorithms is handy, and adjusting the question to find an appropriate spec to implement for a given problem could be a nice touch.
I think that either approach above is strictly better than implementing algorithms from memory and would produce a far better signal.
The project was written in SmallTalk, running on a very old implementation (last updated in 1999 I think) and we had a problem where clicking on column headers in the UI to sort would be very slow if most of the values were equal. The problem was that the standard library array sort was quicksort (which also meant that sorting on several columns broke since quicksort isn't stable), but since SmallTalk makes these things possible when you need to replacing the stdlib quicksort with mergesort was actually a fairly simple operation.
I've learned that big O notation is always and exclusively about the worst case, for average and best cases we use Theta Θ and Omega Ω, respectively.
Do people not follow these definitions strictly? Has the author committed a mistake or am I missing something?
I did experience an interviewer once saying that my complexity analysis was wrong as the worst case would be extremely rare to hit, I did try to explain nicely that big O notation is always about the worst case, and that they were thinking about big Theta instead, now I wonder if I was wrong.
Maybe I value "pure symbolic clairty" too much. I do see a very pragmatic usefullness to the complexity notation.
Not necessarily. It can be the "expected" number of steps over the range of unknown inputs even for a deterministic algorithm.
Wikipedia's bubble sort page -- as an example -- also uses it for all cases.
As explained elsewhere though, they are not notations for algorithmic complexity, they are notations for function categorization. It just happens that a common use for this notation in CS is to categorize the function "best/average/worse/... case complexity of an algorithm", but they are also used for other purposes.
Big O/Theta/Omega denotes sets of functions, and each of them can be applied to best/worst/amortized complexity analysis.
Ex: merge sort is Theta(n log(n)), but quick sort is not.
The author is likely saying "worst case O(n log(n))" as redundancy to emphasize that this is worst case behaviour.
It is redundant to say "worst case O(n^2)". By definition, O(X) means that the maximum of the number of operations over all possible inputs of length n is at most X.
Typically f is used to describe space or time complexity of an algorithm, but it can be used for any function that maps positive integers to the non-negative real numbers.
You can make any combination of best case/worst case/average case with O, Ω, Θ. In fact, you can even consider other cases as well such as amortized cases, 90th percentile cases, any case you want to investigate that can be defined as a function from positive integers to non-negative real numbers can be classified as having an asymptotic upper bound, lower bound, or tight bound.
"Average-case of algorithm X" can be a function function (average number of operations for all possible inputs of length n). And asymptotic bounds can be applied to arbitrary functions from R -> R.
You are wrong. It is perfectly formally correct to say "average case complexity is 2n log(100n) + 78n + 90, which is O(n log (n))".
> By definition, O(X) means that the maximum of the number of operations over all possible inputs of length n is at most X.
No, that is, in fact, a colloquial use of O(X). O(X), formally, is simply the set of all functions that are bigger than X up to some constant factor. It has nothing to do with number of operations in itself.
Instead, we formally define complexity functions for an algorithm, which are the minimum/average/maximum number of operations the algorithm will execute for any input of size N; call these functions Cmin(n), Cavg(n), Cmax(n). Then, we can say that C_(n) is in O(X(n)) (or, as a shorthand, C_(n) = O(X(n))) if there exists a number k such that C_(n) < k * X(n) for any n > n0.
So, we can say that the best case complexity of an algorithm, Cmin(n), is O(n^2); this means that even for the best possible input of length n, it will execute at least k * n^2 steps, for some k. Or, we can say that the worse case complexity of some algorithm, Cmax(n), is Omega(n^2); that is, that even in the worse case input of length n, it will execute less than k * n^2 steps, for some k.
In fact, the concept "number of steps that an algorithm will execute for any input of size n" is not a mathematical function at all (unlike min/max/avg number of steps), since there isn't, in general, a unique such number for any given size.
So, I would argue that saying "complexity O(n^2)" is in fact ill-defined formally, and that, if you want to be formal, you must specify "worst case complexity O(n^2)".
But that is a bit nit picky.
The much more important problem with "average case" complexity, particularly infamously for sorts, is just that practical "typical" inputs aren't distributed evenly over the space of possible inputs; pathological inputs have, after all, practically by definition, a nontrivial almost–computable property that informally gives them more of a reason to exist than than the average input.
No, you're overgeneralizing. It's true that the worst case term dominates if e.g. a constant fraction of inputs exhibit the worst-case behavior, so that average complexity is lower bounded by a constant fraction of the worst-case behavior.
This isn't true for the kind of algorithms where it's customary to talk about average case behavior. We only normally talk about average cases when as input size increases, the fraction of inputs with the higher complexity bound shrinks faster. For example, we can imagine an algorithm which, on inputs of size n, requires n^2 operations on 1/n of possible inputs, and n operations on the other (n-1)/n inputs. Then the average runtime is, formally, (n^2)*(1/n)+n*(n-1)/n=2n-1, which is still O(n), even though the worst-case runtime is still O(n^2).
Where this goes wrong is, e.g. perhaps the O(n^2) runtime occurs on "trivial" inputs which are disproportionately likely to appear. For example, if we the above hypothetical function is idempotent and runs in O(n^2) on all of its possible outputs, but O(n) on all other inputs, it'd be easy to accidentally quadratic by calling it on its result repeatedly under the assumption that it's safe to do so.*
My main line of reasoning is:
1. If I say "this algorithm time-complexity is O(X)", I mean that all possible cases are in O(X).
2. If all possible cases are in O(X), then the worst case is in O(X).
3. If the worst case is in O(X), then any other case will also be in O(X). This follows from our definition of "worst case".
4. Therefore, "all possible cases are in O(X)" <=> "worst case is in O(X)"
5. Therefore, "this algorithm time-complexity is O(X)" <=> "this algorithm time-complexity is worst-case O(X)"
If your thought is that 1) isn't a formal definition, fair enough. It may have been a convention we adopted within the department. But aside from that, I think the reasoning is solid.
It is perfectly valid to say "the best case is O(n)" which means the best case scales no worse than linearly. The "no worse" here is not describing the best case, but rather the strictness of your bound. You could say a sort algorithm is O(n!) since, yes, it does scale no worse than n! but it's not particularly helpful information.
Big O notation is used imprecisely frequently (see also people saying a dataset is O(millions) to describe scale).
When we say "X is O(f(n))" what we really mean is "the function that characterizes X is contained within the set of functions denoted by O(f(n))." Anything that can be described by a function hence can be given Big O, Theta, or Omega notation. So yes worst case time complexity could be described in this notation, but so could average time complexity.
But we could also describe things that have nothing to do with time or space complexity with big O notation as well. As long as we've turned it into a function, we can describe it with big O notation.
When analyzing an algorithm, you want to compute the number of steps it has to execute in certain cases as a function of its input size(s). That function will be something like 2n^2 + 67n + 189 steps. Since this is too much information, you can then express it instead as O(n^2) (or O(n^100)) or Ω(n^2) (or Ω(25n) ) or Θ(n^2).
You can then also compute the best case running time of the algorithm as a function of the size of the input, and get 2n^2 + 67n. Then you can say that the best case running time is also O(n^2).
Finally, you can (sometimes) define an "average" running time.
Now, what do we mean by "shortest running time"? Is that not always for n=0 or something? No - the best case running time has to do with the running time in a case where the input has a certain shape. For some sorting algorithms for example, if the input is already sorted, they will only go through the list once and do nothing, so they have a best case running time that is O(n). Other sorting algorithms will still perform steps even if the input is already sorted, so even their best case running time may be O(n log(n)).
Now, you can say that, given any possible input, the running time of the algorithm is O(worse case running time) and Ω(best case running time). You definitely CAN'T say in general that it is Θ(average case running time) though, as in will sometimes run in time that is shorter than "average case running time" (for best case scenarios); or sometimes it will run in time that is longer than "average case running time" (for worse case scenarios).
Basically, the worse/best/average case running times are an analysis of how properties other than the size of the input affect its running time.
Big-O notation and its friends have nothing to do with complexity analysis. They are a general notation for the asymptotic behavior of mathematical functions. Big-O is usually understood as an upper bound on a function, big-Ω is a lower bound, and Θ is a tight bound (the function f is by definition always within a factor of k above or below Θ(f)).
Edit: let's take an example. Say we have the following algorithm:
isAllOdd(array x):
if x is empty:
return true
if x[0] is even:
return false
return isAllOdd(x[1:])
In the worse case, all elements of the array are odd, so we have to go through all n elements to find that out. It will have to execute 6 instructions for each element in the array (2 comparisons, 2 array accesses, a call and a return), except for the last element where it will execute only 2 instructions (check size then return). So its worst case complexity function is worst(n) = 6(n-1) + 2, which is O(n), Θ(n), Ω(n).
In the average case, for every call we are flipping a coin, and we have n total flips. Since we can assume the coin is fair, we will expect to see an even number after log(n/2) calls of isAllOdd. So, our average case complexity is average(n) = 6*log((n-1)/2) + 2 steps, which is O(log n), Θ(log n), Ω(log n). (I am ignoring cases where n < 2, which is anyway irrelevant for asymptotic behavior).
Now, what is the overall complexity of isAllOdd? We can generalize the average case calculation if we want to get an exact value; but whatever that function, overall(n), is, we know for sure best(n) < overall(n) < worst(n); so overall(n) is O(n) and Ω(1). However, we can't define any Θ for it - there is no function which it will differ from by at most a constant factor for any n.
Why do the detailed analysis instead of saying this is O(n) and being done with it? Well, perhaps we know that we are in fact calling this function with a large number of even numbers, so we would actually over-estimate its complexity. If we instead know we are calling it with a large number of odd numbers, we would also find out from the average case analysis that it would be better to define a reverse funtion, isAllEven, and compute isAllOdd = !isAllEven.
Theta and Omega I use differently however.
I sometimes say, best case if X then it's O(n) or whatever.
+---------------------------------------+-------------------------------+--------------------------------+----------------------------------------+
| . | Best Case (little/no traffic) | Average Case (average traffic) | Worst Case (car accident, snow-in etc) |
+---------------------------------------+-------------------------------+--------------------------------+----------------------------------------+
| Max time, upper bound (Big O) | 30 minutes | 45 minutes | 1 hour 20 minutes |
| Both min and max, tight bound (Theta) | 25 minutes | 35 minutes | 1 hour |
| Minimum time, lower bound (Omega) | 15 minutes | 25 minutes | 50 minutes |
+---------------------------------------+-------------------------------+--------------------------------+----------------------------------------+
This also helps explain why Big O is generally more useful - we can almost always be early to something, but we can almost never be late to something. So showing up 5 minutes early usually is not a problem.
It also shows why Theta is better than both - in this case, if we had this table we could completely ignore both the Big O row and Omega row, because Theta is a better bound for both min and max time.
Of course, in algorithmic complexity we replace the times with functions in terms of some variables, usually just n.
I think the most important thing that needs to be clarified though is that algorithmic complexity is first and foremost a function, `WorseCaseComplexity(size of input) = max number of steps for any input of that size`. This function is often then classed into a "complexity class" using O/Theta/Omega etc, but that is only done for the sake of easier comparison of complexities between algorithms.
Big Theta for some functions is an empty set. Take for example bubble sort. It's O(n^2) and Ω(n), but there is no function that asymptotically bounds it above and below. In fact it is better if there isn't one as it means there exists fast cases. For bubble sort it's fast cases are ones where data is almost sorted and requires to scans of the array. If you know this is true of the input data you know bubble sort is more appropriate than something like merge sort which is Ω(nlog(n)). Now the O(n^2) worst case can still be significant so you may want to consider an alternate algorithm that doesn't break down as bad.
As the other reply pointed out we are talking about functions that bound some other function (in this context the amount of steps / operations / time an algorithm will take) when looking at how it behaves asymptotically.
Then, we can say best_case_complexity(n) = Theta(n), and worst_case_complexity(n) = Theta(n^2). We can also define the set of all functions representing the number of steps bubble sort will take for input of a certain "shape" of size n. We can then indeed say that any function in this set will be <= worst_case_complexity(n) and >= best_case_complexity(n), so this set will indeed be a subset of Omega(n) and of O(n^2).
f(x) = O(g(x)) <=> there exists k, x0 such that f(x) < k * g(x) for any x > x0
f(x) = o(g(x)) <=> for any k > 0, there exists x0 s.t. f(x) < k * g(x) for any x > x0
f(n) = 3*n^2 + 2n + 1
f(n) = O(n^2)?
let's take k = 10
3*n^2 + 2n + 1 < 2 * n^2 for any n > n0?
n = 0: 3 * 0^2 + 2*0 + 1 < 10 * 0^2 <=> 1 < 0 false
n = 1: 3 * 1^2 + 2*1 + 1 < 10 * 1^2 <=> 6 < 10 true
n = 2: 3 * 2^2 + 2*2 + 1 < 10 * 2^2 <=> 17 < 40 true
...
so, yes, f(n) = O(n^2) (n0 = 1)
f(n) = o(n^2) ?
let's take k = 2.
3*n^2 + 2n + 1 < 2 * n^2 for any n > n0?
3 * n^2 + 2 * n + 1 < 2 * n^2 <=>
3 * n^2 + 2 * n + 1 - 2 * n^2 < 0 <=>
n^2 + 2 * n + 1 < 0 false for any n > 0.
so no, f(n) != o(n^2). However, f(n) = o(10 * n^2), and f(n) = o(n^3).
Big-Theta is a tight bound around the function:
f(n) = Theta(g(n)) <=> there exists k1, k2, n0 such that k1*g(n) < f(n) < k2*g(n), for any n > n0.
I suspect there should be a new std::verify_weak_ordering to help people write tests that perform n^3 tests on potential data to ensure a comparator is safe to use.
Maybe there's some extra flag to turn on even more tests. I've always found MSVC STL to be completely impossible to use in debug mode for any real project.
std::sort(<some floats with NaNs>);
std::sort(..., [] (float a, float b) { return a <= b; });
std::sort(..., [] (float a, float b) { return true; });
I'd assume they don't want to introduce a check for the FP case as it would break pretty much all the code on earth which assumes that NaNs and Infs do not exist.
There are even compile flags that let the compiler assume that as well - some of them as benign sounding as -ffast-math or -Ofast.
- How does it perform on average?
- How does it perform on pathological inputs?
- Is it stable?
- Does it allocate?
Not to mention constraints that an application can take advantage of:
- What if the data is already mostly sorted? (insertion sort)
- What if writes are very expensive? (cycle sort)
- What if all the data are integers? (radix sort)
And so on. Trying to force a one-size-fits-all solution seems rather silly at this point.
Timsort being a somewhat famous example, which uses the fact that python datastructures are known length to figure out the best sorting method for the size.
If you need something more exotic then you likely know more about what you're doing, but most people writing software who need a sort function usually don't need more than timsort.
That... does not match with my knowledge of how timsort works. The sorting method is chosen based on the array length, and every sorting algorithm in every language knows that. It's extremely suboptimal for some types because Python's typing is so weak!
Timsort succeeds because it has many good heuristics to optimize common properties of its merge intervals.
The vast majority of the time, the default works well enough. Why make things more complicated than they need to be?
It also has the added benefits of helping more junior engineers when reading the code. "Cycle sort? What is that doing?" "Insertion sort? I was taught that was inefficient! I should spend time updating this code to a better sorting algorithm! My tech lead would love my initiative."
Or we just use sort(), and we all move on with our lives.
Does it? How? I suppose one has to store the standard library on the machine, which does notionally use up disk space, but I can’t see how it contributes by any reasonable performance-relevant meaning of ‘disk usage’ (presumably i.e. disk I/O during the runtime of the program). And for cache utilization I simply have no clue at all what you might be driving at.
Most of the time I don't care if it's timsort or quicksort, or if the hashmap uses Cuckoo hashing or buckets made of linked lists. Of course there are the 1% of cases where I notice that my sort or hashmap is a performance bottleneck and that a different algorithm might perform better. But standard libraries aren't good at serving that need because they have to be broadly applicable and conservative, if I already know that I want top performance for specific requirements I'm almost certainly better served by an external library.
I agree though, there should be the ability to specify which one, and every function in the standard library should have big O notation in the function description. Still makes sense to have a general-purpose good one as the default.
You can (and most people do) look at it from the other angle. Sort(seq) is a function which returns a permutation of seq such that every element is less-than-or-equal-to the next element. Usually, we use this function because we need this property to hold in our following code. A lot of the time, this function is called for very short sequences, where even the most naive implementation would be fats enough for even the highest scale program. So, in the vast majority of code we only care about the semantics of std::sort; and all of the above have the same semantics.
In fact, the fact that we do often get a stable sort as well shows that semantics are the most important characteristic, as stable and unstable sorts do have slightly different semantics.
Damn cool algorithm though.
The line spacing is weird though.
Failed at everything. Will improve
They also explain that down here you're at the mercy of the physical hardware. Emitting one fewer x86 instruction does not necessarily make your program faster, still if it's not slower then smaller programs are good too.
Also, typo: "compare functions much comply" -> "compare functions must comply"
https://github.com/shogun-toolbox/shogun/blob/9b8d85/src/sho...
Unrelated, but from the same section:
> Fixes are trivial, access the nth element only after the call being made. Be careful.
Wouldn't the proper fix to do the nth_element for the larget element first (for those cases that don't do that already) and then adjust the end to be the begin + larger_n for the second nth_element call? Otherwise the second call will check [begin + larger_n, end) again for no reason at all.
not everything is a linear relationship
OTOH if the measurement is risk of breaking something, then it's not nearly so clear, since larger organizations tend to have more software and hardware, and therefore more opportunities for things to get broken.
The way this is written, it sounds as if Andrei Alexandrescu is responsible for the 20 year delay.