digitalmars.D - D2's std.algorithm and sorting
- bearophile <bearophileHUGS lycos.com> Dec 20 2007
Bill Baxter:sort!("a > b")(array); I just wanted to say that this is BRILLIANT! Zero call overhead, zero syntax overhead, compile-time lambda functions!
Sorry for raising this thread again (with a different name) after so much time, I want to say something that comes from my experience. Python list.sort()/sorted(iterable) accepts an optional cmp() function too, but later they have added the "key" optional parameter too, and today most of the times you use key instead of cmp. http://docs.python.org/lib/typesseq-mutable.html key specifies a function of one argument that is used to extract a comparison key from each list element, like key=str.lower. An example:l = [7,2,2,-10,10,-10,-3,4,-9,-7] sorted(l)
Using key requires more memory (for the "decorated" elements), but it's often much simpler to use. A good sorting routine has many conflicting goals: - easy to use with a short and simple syntax, for 99% of situations where you have a small array and you both don't need max sorting speed nor to use as little memory as possible. - very fast and memory-lean when used on LOT of data. - able to sort really fast already partially sorted arrays. - etc. The key() parameter is useful for the first situation, that is very common. For all the other situations you can accept a more fussy syntax, that allows you to use less memory and/or to sort faster. So I think the "a > b" idea is cute and useful where you need to save memory, but in many easy situations a key function as parameter is better (simpler to use). (I have developed a large library of D function/classes, mostly for functional-style programming (but useful for other things too), it has both a much faster sort than the built-in one, and a sort/sorted functions (for arrays and AAs, iterable classes, etc) that accept an optional key() function too. Maybe such stuff may be useful for Phobos/Tango). Bye, bearophile
Dec 20 2007