www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - D2's std.algorithm and sorting

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]
[-10, -10, -9, -7, -3, 2, 2, 4, 7, 10]
[2, 2, -3, 4, 7, -7, -9, -10, 10, -10] 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