5 ms·

What's the problem? From D. Knuth's The Art of Computer Programming: Sorting and Searching, (1) if sorting n records by comparing pairs of keys, then the Gle

by graycat 11y ago

What's the problem? From D. Knuth's The Art of Computer Programming: Sorting and Searching, (1) if sorting n records by comparing pairs of keys, then the Gleason bound shows that on average can't sort faster than O( n ln(n) ). (2) Heap sort sorts n records in both worst case and average case in time O( n ln(n) ). Net, when sorting by comparing pairs of keys, in main memory, on a simple machine architecture, with a single processor, ..., can't improve on Heap sort. So, just use Heap sort. That's what I do.

nightcracker 11y ago
Big O hides all constants. A hybrid algorithm using Quicksort for the heavy lifting is O(n log n) in the worst case, but is a significant amount faster than heapsort - mainly due to cache effects. See pdqsort for examples (benchmarks included): https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort. It shows that on average it's twice as fast on the random input distribution.
- graycat 11y ago
  Now and long the usual criterion of performance is big-O notation, and that is what I considered, with the Gleason bound and heap sort and, thus, showed that, with various common assumptions, can't do better than heap sort. As far as I know, I was correct. So, to claim to beat heap sort, have to set aside some of the usual assumptions and the big-O criterion. Quicksort is great with a cache since as it has great locality of reference when working with the partitions that fit into the cache. But, worst case of Quicksort is still O( n^2 ) so what happens if Quicksort encounters such a partition? Just intuitively, it appears that heap sort has a tough time making much exploitation of usual cache designs. We know that. There is a modification of heap sort that helps it work better when have to do virtual memory paging. I used to get torqued at considering big-O, and did this just because it ignores constants; as a programmer, I worked hard to do well with such constants. But in the end I gave in and gave up and just accepted big-O notation as the most appropriate, simple, single criterion. And, for judging algorithms by how they do with cache exploitation, I gave up on that, also: Or, broadly it's the responsibility of such speedup techniques to work on ordinary code written for a simple processor architecture, not the responsibility of such code to do tricky things to exploit tricky architectures. In the land of big-O, a factor of only 2 is considered not very exciting. If relax some of the assumptions, then can beat heap sort and O( n ln(n) ): Use radix sort. That was the sorting algorithm of the old punch card sorting machines. E.g., if have 100 billion records to sort where each key is an alpha-numeric string 10 characters long, then radix sort does all the work in just 10 passes of the 100 billion records. Or for keys m characters long, can sort n records in O( nm ). So that's faster when m < ln(n). Or, to make the arithmetic easier, m < log(n). But log(100 billion) = 12, so radix sort should be faster with m = 10 and n = 100 billion. So, for a hybrid sort routine, consider also radix sort. Am I excited about radix sort? Nope!
  - strmpnk 11y ago
    You should check out the sort your parent linked. It talks all about what happens and the overhead involved. ;-)
  - nightcracker 11y ago
    > But, worst case of Quicksort is still O( n^2 ) so what happens if Quicksort encounters such a partition? I'd strongly suggest you to read the readme I wrote for https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort, which explains in detail how I beat heapsort (and other sorting algorithms). It also shows how I prevent the O(n^2) worst case. > I used to get torqued at considering big-O, and did this just because it ignores constants; as a programmer, I worked hard to do well with such constants. But in the end I gave in and gave up and just accepted big-O notation as the most appropriate, simple, single criterion. We have already established that O(n log n) is the lower bound, and we have reached this lower bound. This is where big O stops being useful. A metric that compares equal for every relevant algorithm (mergesort, introsort, pdqsort, timsort, smoothsort, heapsort) is not a useful metric. > In the land of big-O, a factor of only 2 is considered not very exciting. I live in the land of real-world performance, powered by actual benchmarks. In this land a factor of 2 is very exciting. > So, for a hybrid sort routine, consider also radix sort. I worked in the scope of std::sort, which is strictly a comparison sort.
    - taeric 11y ago
      > We have already established that O(n log n) is the lower bound, and we have reached this lower bound. This is where big O stops being useful. A metric that compares equal for every relevant algorithm (mergesort, introsort, pdqsort, timsort, smoothsort, heapsort) is not a useful metric. With the explosion of cores and special purpose hardware, it is interesting to think of how long before sorting network routines are more practical. Dropping the runtime to O(lg n) would be enticing. :)
    - graycat 11y ago
      I assumed that we were talking about in place sorting. "I feel your pain." As I tried to explain, the first time I saw big-O notation taken seriously as the main metric for evaluating the actual running time of actual code on actual data on an actual computer, I had your reaction, that the constants are important and the big-O criterion, not good. There's another point: The silent assumption of the big-O criterion is that we are interested in (A) something fundamental about algorithms, just the algorithms, and not (B) actual running time of actual code on actual data on actual computers. And big progress in algorithms is also important and, as we know, in some cases can give much better performance gains in real computing than anything a programmer can do without the big progress. And we have a great example: There were days before heap sort, shell sort, quicksort when the in place sorting algorithm people coded were bubble sort or something closely related and also O(n^2). Then in practice, the difference was just huge. Early in my career, I ran into that at Georgetown University: A prof had coded up some software for teaching statistics and had used the IBM Scientific Subroutine Package (SSP) for a most of the actual calculations. One of the SSP routines was to find ranks, and it had two loops, each essentially bubble sort. In testing, the thing ran all lunch time. Well, the data to be ranked was 32 bit integers, and an array index was a 16 bit integer. So, I was able to do a tricky overlay of two 16 bit integers on the 32 bit data, use heap sort, and get O( n ln(n) ). In actually running time on nearly any possible real data, my code as so much faster than IBM's SSP that I blew the doors off the SSP. Lesson 1: O( n ln(n) ) instead of O( n^2 ) can be much better in practice. Lesson 2: Progress in big-O in algorithms can be terrific stuff. Back to practice, early in writing the software for my startup, I tried to write a polymorphic version of heap sort. I wrote in Microsoft's Visual Basic .NET. For the data type to be sorted, I passed just the type object. The software ran correctly right away. Then I did some careful timings -- the software commonly ran ballpark 10 times longer than I would have guessed. What the heck? Well, the run time was smart enough to figure out the actual data type and do the comparison, but the overhead here was enormous. Then I learned that for polymorphic code I was supposed to write some interfaces, one for each data type to be sorted, and for sorting a particular data type pass the corresponding interface. Okay. My confusion was that that use of an interface didn't sound polymorphic to me and sounded no different than what I'd long done passing entry variables in PL/I and Fortran. Okay, for polymorphism, use interfaces. And in the code of the interface, have to work essentially without strong typing, essentially with untyped pointers. Okay -- been there, done that, in both PL/I and Fortran; I was surprised that a serious object oriented language with polymorphism would have essentially just syntactic sugar over what I'd been doing in PL/I and Fortran. Okay. Lesson learned: There are cases of hype in parts of programming languages. Heck, in PL/I my approach to sort an array of PL/I structures would be to pass a PL/I structure that had an element variable that was an entry variable to a procedure that would do the comparisons. That is, could have some conventions that would let PL/I structures be self-describing. Then could write code that was more general. Maybe under the covers, that's just what's going in the Microsoft common language run time (CLR) that Visual Basic .NET used for me without letting me know -- more syntactic sugar? So, when I rewrote my polymorphic heap sort to do the comparisons with a passed interface, the performance got okay. Still, I have non-polymorphic versions for the more important element data types, and they are faster in just they way you emphasized. Yup, been there, done that. So, I, too, was concerned about actual running time of actual data. But for the algorithm itself, I was still using just heap sort and didn't try to write a hybrid routine that sometimes might exploit, say, radix sort. On the pros and cons of using big-O for the only criterion, there's a big example in linear programming: In practice, the simplex algorithm is fantastically fast. Intuitively, in practice, the early iterations in effect focus what to do to get to the optimal solution (assuming feasibility, no unboundedness, etc.). But due to some work of Klee and Minty, the worst case of simplex is exponential and just awful. Intuitively the Klee and Minty examples trick simplex into making really bad choices! So, there was research to find a polynomial algorithm for linear programming. Eventually there was an ellipsoid algorithm that was polynomial but the constant was so high that whenever in practice ellipsoid beat simplex both ran too long to be practical. So, really, the concern about simplex and the effort for ellipsoid was as progress just in algorithms and in the big-O criterion. And in practice, right away, the constant was so large that ellipsoid was a flop. Still, in algorithms, people are straining to do better in the sense of the big-O criterion. Of course the biggest effort here is to find an algorithm that shows that P = NP, maybe the one of the most important problems in both math and computer science, based on big-O for some polynomial. With all of that, I decided in my own work, for something as simple as sorting, just to go with heap sort, maybe even a polymorphic heap sort. Indeed, with all the emphasis on polymorphism, people can't be very concerned about constants! :-)!
crpatino 11y ago
In theory, there's no significant differences between theory and practice. In practice, things are never so simple. When you use Big-Oh notation, O(f(n)), you claim that there exist one function F(n) that accurately characterizes the running time of an algorithm based on the size of the input, and that f(n) is the higher order component of that function. I looks something like this: F(n) = A*f(n) + B*g(n) + C*h(n) + ... + K where A,B,C,..K are constants and f,g,h,... are functions. You approximate F(n) ~= Af(n) because for n big enough, this component will dominate the growth of such function. But A is different for different algorithms... so, in the case of sorting, you have several options - quicksort, mergesort, heapsort - that are in paper all "the same" but each has a different constant, and there are real advantages of using the one with the smallest constant. Furthermore, if you are not trying to sort infinitely big data (most real world cases) you must consider that other components of the actual F(n) function, such as g and h, may dominate the performance of the algorithm in the range of data sizes that you are more likely to encounter. There are other measures of algorithmic complexity that deal with this (I recall there is one Small-Oh notation, among others), but they don't teach you that at school unless you are a posgraduate student doing highly relevant work in complexity theory. I suspect most guys, like myself, find out by not taking Knuth as holy gospel and reading further material. And then there are the degenerate cases, where your data can get sorted in quasi-linear time if you apply one of the slow dumb O(n^2) dinosaurs.

by graycat 11y ago

nightcracker 11y ago

Big O hides all constants. A hybrid algorithm using Quicksort for the heavy lifting is O(n log n) in the worst case, but is a significant amount faster than heapsort - mainly due to cache effects. See pdqsort for examples (benchmarks included): https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort. It shows that on average it's twice as fast on the random input distribution.

graycat 11y ago
Now and long the usual criterion of performance is big-O notation, and that is what I considered, with the Gleason bound and heap sort and, thus, showed that, with various common assumptions, can't do better than heap sort. As far as I know, I was correct. So, to claim to beat heap sort, have to set aside some of the usual assumptions and the big-O criterion. Quicksort is great with a cache since as it has great locality of reference when working with the partitions that fit into the cache. But, worst case of Quicksort is still O( n^2 ) so what happens if Quicksort encounters such a partition? Just intuitively, it appears that heap sort has a tough time making much exploitation of usual cache designs. We know that. There is a modification of heap sort that helps it work better when have to do virtual memory paging. I used to get torqued at considering big-O, and did this just because it ignores constants; as a programmer, I worked hard to do well with such constants. But in the end I gave in and gave up and just accepted big-O notation as the most appropriate, simple, single criterion. And, for judging algorithms by how they do with cache exploitation, I gave up on that, also: Or, broadly it's the responsibility of such speedup techniques to work on ordinary code written for a simple processor architecture, not the responsibility of such code to do tricky things to exploit tricky architectures. In the land of big-O, a factor of only 2 is considered not very exciting. If relax some of the assumptions, then can beat heap sort and O( n ln(n) ): Use radix sort. That was the sorting algorithm of the old punch card sorting machines. E.g., if have 100 billion records to sort where each key is an alpha-numeric string 10 characters long, then radix sort does all the work in just 10 passes of the 100 billion records. Or for keys m characters long, can sort n records in O( nm ). So that's faster when m < ln(n). Or, to make the arithmetic easier, m < log(n). But log(100 billion) = 12, so radix sort should be faster with m = 10 and n = 100 billion. So, for a hybrid sort routine, consider also radix sort. Am I excited about radix sort? Nope!
- strmpnk 11y ago
  You should check out the sort your parent linked. It talks all about what happens and the overhead involved. ;-)
- nightcracker 11y ago
  > But, worst case of Quicksort is still O( n^2 ) so what happens if Quicksort encounters such a partition? I'd strongly suggest you to read the readme I wrote for https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort, which explains in detail how I beat heapsort (and other sorting algorithms). It also shows how I prevent the O(n^2) worst case. > I used to get torqued at considering big-O, and did this just because it ignores constants; as a programmer, I worked hard to do well with such constants. But in the end I gave in and gave up and just accepted big-O notation as the most appropriate, simple, single criterion. We have already established that O(n log n) is the lower bound, and we have reached this lower bound. This is where big O stops being useful. A metric that compares equal for every relevant algorithm (mergesort, introsort, pdqsort, timsort, smoothsort, heapsort) is not a useful metric. > In the land of big-O, a factor of only 2 is considered not very exciting. I live in the land of real-world performance, powered by actual benchmarks. In this land a factor of 2 is very exciting. > So, for a hybrid sort routine, consider also radix sort. I worked in the scope of std::sort, which is strictly a comparison sort.
  - taeric 11y ago
    > We have already established that O(n log n) is the lower bound, and we have reached this lower bound. This is where big O stops being useful. A metric that compares equal for every relevant algorithm (mergesort, introsort, pdqsort, timsort, smoothsort, heapsort) is not a useful metric. With the explosion of cores and special purpose hardware, it is interesting to think of how long before sorting network routines are more practical. Dropping the runtime to O(lg n) would be enticing. :)
  - graycat 11y ago
    I assumed that we were talking about in place sorting. "I feel your pain." As I tried to explain, the first time I saw big-O notation taken seriously as the main metric for evaluating the actual running time of actual code on actual data on an actual computer, I had your reaction, that the constants are important and the big-O criterion, not good. There's another point: The silent assumption of the big-O criterion is that we are interested in (A) something fundamental about algorithms, just the algorithms, and not (B) actual running time of actual code on actual data on actual computers. And big progress in algorithms is also important and, as we know, in some cases can give much better performance gains in real computing than anything a programmer can do without the big progress. And we have a great example: There were days before heap sort, shell sort, quicksort when the in place sorting algorithm people coded were bubble sort or something closely related and also O(n^2). Then in practice, the difference was just huge. Early in my career, I ran into that at Georgetown University: A prof had coded up some software for teaching statistics and had used the IBM Scientific Subroutine Package (SSP) for a most of the actual calculations. One of the SSP routines was to find ranks, and it had two loops, each essentially bubble sort. In testing, the thing ran all lunch time. Well, the data to be ranked was 32 bit integers, and an array index was a 16 bit integer. So, I was able to do a tricky overlay of two 16 bit integers on the 32 bit data, use heap sort, and get O( n ln(n) ). In actually running time on nearly any possible real data, my code as so much faster than IBM's SSP that I blew the doors off the SSP. Lesson 1: O( n ln(n) ) instead of O( n^2 ) can be much better in practice. Lesson 2: Progress in big-O in algorithms can be terrific stuff. Back to practice, early in writing the software for my startup, I tried to write a polymorphic version of heap sort. I wrote in Microsoft's Visual Basic .NET. For the data type to be sorted, I passed just the type object. The software ran correctly right away. Then I did some careful timings -- the software commonly ran ballpark 10 times longer than I would have guessed. What the heck? Well, the run time was smart enough to figure out the actual data type and do the comparison, but the overhead here was enormous. Then I learned that for polymorphic code I was supposed to write some interfaces, one for each data type to be sorted, and for sorting a particular data type pass the corresponding interface. Okay. My confusion was that that use of an interface didn't sound polymorphic to me and sounded no different than what I'd long done passing entry variables in PL/I and Fortran. Okay, for polymorphism, use interfaces. And in the code of the interface, have to work essentially without strong typing, essentially with untyped pointers. Okay -- been there, done that, in both PL/I and Fortran; I was surprised that a serious object oriented language with polymorphism would have essentially just syntactic sugar over what I'd been doing in PL/I and Fortran. Okay. Lesson learned: There are cases of hype in parts of programming languages. Heck, in PL/I my approach to sort an array of PL/I structures would be to pass a PL/I structure that had an element variable that was an entry variable to a procedure that would do the comparisons. That is, could have some conventions that would let PL/I structures be self-describing. Then could write code that was more general. Maybe under the covers, that's just what's going in the Microsoft common language run time (CLR) that Visual Basic .NET used for me without letting me know -- more syntactic sugar? So, when I rewrote my polymorphic heap sort to do the comparisons with a passed interface, the performance got okay. Still, I have non-polymorphic versions for the more important element data types, and they are faster in just they way you emphasized. Yup, been there, done that. So, I, too, was concerned about actual running time of actual data. But for the algorithm itself, I was still using just heap sort and didn't try to write a hybrid routine that sometimes might exploit, say, radix sort. On the pros and cons of using big-O for the only criterion, there's a big example in linear programming: In practice, the simplex algorithm is fantastically fast. Intuitively, in practice, the early iterations in effect focus what to do to get to the optimal solution (assuming feasibility, no unboundedness, etc.). But due to some work of Klee and Minty, the worst case of simplex is exponential and just awful. Intuitively the Klee and Minty examples trick simplex into making really bad choices! So, there was research to find a polynomial algorithm for linear programming. Eventually there was an ellipsoid algorithm that was polynomial but the constant was so high that whenever in practice ellipsoid beat simplex both ran too long to be practical. So, really, the concern about simplex and the effort for ellipsoid was as progress just in algorithms and in the big-O criterion. And in practice, right away, the constant was so large that ellipsoid was a flop. Still, in algorithms, people are straining to do better in the sense of the big-O criterion. Of course the biggest effort here is to find an algorithm that shows that P = NP, maybe the one of the most important problems in both math and computer science, based on big-O for some polynomial. With all of that, I decided in my own work, for something as simple as sorting, just to go with heap sort, maybe even a polymorphic heap sort. Indeed, with all the emphasis on polymorphism, people can't be very concerned about constants! :-)!

crpatino 11y ago

In theory, there's no significant differences between theory and practice. In practice, things are never so simple. When you use Big-Oh notation, O(f(n)), you claim that there exist one function F(n) that accurately characterizes the running time of an algorithm based on the size of the input, and that f(n) is the higher order component of that function. I looks something like this: F(n) = A*f(n) + B*g(n) + C*h(n) + ... + K where A,B,C,..K are constants and f,g,h,... are functions. You approximate F(n) ~= Af(n) because for n big enough, this component will dominate the growth of such function. But A is different for different algorithms... so, in the case of sorting, you have several options - quicksort, mergesort, heapsort - that are in paper all "the same" but each has a different constant, and there are real advantages of using the one with the smallest constant. Furthermore, if you are not trying to sort infinitely big data (most real world cases) you must consider that other components of the actual F(n) function, such as g and h, may dominate the performance of the algorithm in the range of data sizes that you are more likely to encounter. There are other measures of algorithmic complexity that deal with this (I recall there is one Small-Oh notation, among others), but they don't teach you that at school unless you are a posgraduate student doing highly relevant work in complexity theory. I suspect most guys, like myself, find out by not taking Knuth as holy gospel and reading further material. And then there are the degenerate cases, where your data can get sorted in quasi-linear time if you apply one of the slow dumb O(n^2) dinosaurs.