Re: [boost] Anyone downloaded the sorting library from vault?
On March 16, Lewis Hyatt wrote I took a look at it. Some of my thoughts: -You should provide random access iterator interfaces, not just a bare pointer. -Your docs say you require T to be an integral type or have operator< defined, I think you meant to say "built-in arithmetic type" or something similar. You should also let the user provide their own comparison functor instead of requiring them to overload operator< -Based on your descriptions, it looks like merge_sort is the same as std::stable_sort and quicksort is the same as std::sort, more or less. (Except the standard functions have more generic interfaces). What advantage are they supposed to have over the standard functions? I tried some timings, and found that for both ints and doubles, on my system, your quicksort is about 50% slower than std::sort, and your mergesort is about 5% faster than std::stable_sort, at least for the case of already-sorted data. -It might make more sense to focus on radix sort, since that is not already offered in the standard library... Are you sure about the quicksort speed difference? That seems like a huge difference. Did you have inlining enabled? Also, the current versions are not the final forms. I am implementing random-access iterators and user-provided functions.
Are you sure about the quicksort speed difference? That seems like a huge difference. Did you have inlining enabled? Also, the current versions are not the final forms. I am implementing random-access iterators and user-provided functions.
Yes, this was on cygwin compiled with g++ -O3. One thing to keep in mind is that your routines are competing with the standard library, which can be highly optimized for whatever target platform the compiler was written for. Unless you have a dramatically improved algorithm, it is unlikely that your sorting routines will beat std::sort in general, even if they do on some platforms. As an example, suppose your goal was to write an equivalent of std::bitset which beat the standard implementation. It is unlikely that you could exceed the performance of std::bitset::count(), for instance, because most implementations use native assembly instructions to do this whenever possible. (e.g., gcc uses its built-in popcount function on platforms where it is available.) On the other hand, if you hand-coded a version with the best algorithm you could find, it might beat a few poor implementations, but in general it would be inferior. The only way to make it better in general would be to implement all these optimizations yourself for each target platform, but at that point, it's just not worth the time. I don't think it's true that std::sort, std::stable_sort, and std::partial_sort are the end of the story, but I think any work in a sorting library should focus on needs which are not already met. So far, only radix sort appears to fall in that category, but you would also need to demonstrate a case in which radix sort is preferable to std::sort. -lewis
participants (2)
-
Lewis Hyatt -
Sam Schetterer