9/26/2008

09-26-08 - 2

If you search for pages on sorting (real world practical fast sorting), you might find Paul Hsieh's page or this comparison and good implementation or this detailed page with lots of graphs . But all of them are slower than std::sort. Where's the guy who wrote std::sort ? Why doesn't he have a web page? And why aren't there tons of web pages of sorts that beat it? std::sort should certainly NOT be the fastest sort at everything. It's a very very very good implementation, but it's a compromise that trades off reasonable code size and flexibility, and of course sorts are fickle bitches and it should be easy to cook up some test set where your weird sort is better than std::sort. It's kind of like these guys came up with compression algorithms that are worse than pkzip, but they published them anyway, when something better is right there for anyone to use for free.

Of course it's all sort of pointless because if you actually are doing something where sort speed really matters you should use a sort that's customized for your application. For string suffixes I'm currently using Michael Maniscalco's . For floats you can use Pierre Terdiman's radix sort. Hmm.. I just searched for the link and Google tells me the site will harm me. Better wear an e-condom if you go to coder corner. Oh yeah, apparently Michael Herf has an improved version of Pierre's radix, so just go there.

Actually it's not pointless. Having the std::sort as a good baseline is extremely valuable. It's a sanity check that lets you know if you're doing something reasonable. Good libraries like this are extremely valuable *even when you don't use them* because you can test your code against them and know you're not off in lala land. Stuff like dlmalloc and tcmalloc are great for the same reason; I've never actually shipped a product with either, but I consider them invaluable because I can easily link with them and make sure my allocator is at least as good as they are.

No comments:

old rants