Destruct1 wrote:I think it is at least a good alternative to the default. In Python the "sort with the compare method" has been removed after nobody could show a decent example why it needs to stay. Fitness functions are now the only way to sort.
The compare strtegy has several disadvantages:
a) You might get not transitive comparisions, like a>b and b>c and c>a. These are difficult to solve and I hate thinking about crap like that.
b) When two elements have the same function result the order is not easy to determine.But it doesnt matter. Simply say that the order of the original list will be preserved or that it is implementation specific (like in the Lisp Set functions). If you care enough as a programmer make sure your fitness function is unambigious.
c) I think it is slower. The computer is very efficient in comparing numerical values but a complex comparision function kills the sort algorythm. Even if you have a matrix which caches the compare (a,b) result, a NxN matrix is needed. With bubble sort you need the whole matrix filled and with merge sort a good part of it must be computed. The fitness function needs a O(n) mapcar and thats it.
a) In the case presented, that is not a problem. In other cases, the transitivity would be your concern as much as creating a good fitness function that preserves your ordering.
b) Note that in Common Lisp you need to use
stable-sort to preserve the order of the original list. And, in the case presented, collisions are a problem because they make the shuffling less effective. They will be less of a problem if you use a big number in your random function, though.
c) Again, in the example given, this method will actually be slower, since it also needs a function to make the comparison, even if it is the function #'<. In Common Lisp's implementation, the only case where sorting with numbers is faster is to inline the
sort function, maybe not even in that case. If you
need a comparison function, you will probably need to create a good correspondence between you values and numbers, which would be tiresome, and its computation could consume more time than the sorting itself. Your method would also need to cons a list of tuples and restore the original list, which creates a lot of garbage.
In any case, I understand you point, you could gain little to lots of time of your sorting with a fitness function, but I still believe that in many cases it won't be faster. I'll make some tests here and see if I am right or not.