sorting failed error

[Timon Gehr]

On 07/30/2012 02:36 PM, maarten van damme wrote:
> For fun I started implementing a program that uses genetics
> algorithm's to solve the travelling salesman problem. I want to sort
> an array of chromosome structures according to their fitness. I now
> get the error:
>
> core.exception.AssertError at C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm.
> d(6714): Failed to sort range of type chromosome[]. Actual result is: [chromosom
> e([city(20, 0), city(25, 25), city(10, 65), city(50, 50), city(75, 30), city(0,
> 10)]), chromosome([city(10, 65), city(50, 50), city(25, 25), city(75, 30), city(
> ...
>
> I have no idea what is wrong with my code and the error is not very informative.
> Does anyone have any idea as to what the problem could be?
>
> (full code is at
> https://dl.dropbox.com/u/15024434/travelling_salesman.d , If it's not
> something obvious then I'm going to try to reduce it to something as
> small as possible)
>
> Maarten

I'd claim it is a 32 bit specific compiler bug, but it is likely that
someone will differ.



reduced test case:

float foo(){
   auto f = 3f;
   return 1/f;
}
void main(){ assert(foo() == foo()); }

The problem is presumably that one of the operands is truncated to
float while the other remains at register precision.



workaround:

bool fitnessCompare(chromosome first,chromosome second){
   auto a = fitness(first), b = fitness(second);
   return a>b;
}

(the reason schwartzSort works is because it caches the fitnesses,
which is better anyway.)




I realize that the code is just for fun, but I have some comments:

- don't .dup stuff just in order to index directly. it never has
any effect other than performance degradation. (this could be a
compiler warning)

- crossOver and mutate mutate their parameters in-place. I assume this
is by mistake. reproduce effectively inserts every element a couple
times because of this -- this is why the bug manifests reliably.
(const, immutable annotations?)

- make use of $

int from=uniform(0,victim.dna.length);
int to=uniform(0,victim.dna.length);
swap(victim.dna[from],victim.dna[to]);

=>

swap(victim.dna[uniform(0,$)],
      victim.dna[uniform(0,$)]);

- sort is in-place

workers=array(sort!(fitnessCompare)(workers));

=>

sort!fitnessCompare(workers)

- mark local functions static if they do not need to access the
enclosing context.

- use size_t for array iteration variables (if necessary)

for(int x=0;x<cities.length-1;x++)
     travelled+=distance(cities[x],cities[x+1]);

=>

for(size_t x=1;x<cities.length;x++)
     travelled+=distance(cities[x-1],cities[x]);

I also removed the subtraction from the array length. This would be
correct in this case because cities.length>=2 is guaranteed, but it is
an error prone pattern.

- another way to do it is to drop the loop completely and to use
ranges instead:

return zip(cities,cities.drop(1))
       .map!(a=>distance(a.expand))
       .reduce!"a+b";


The benefit is that this is now obviously correct.


You might also want to consider not building up the cities array
and computing the terms at the boundary explicitly instead:

return distance(city(0,0), victim.dna[0]) +
        distance(victim.dna[$-1], city(0,0)) +
        zip(victim.dna, victim.dna.drop(1))
       .map!(a=>distance(a.expand))
       .reduce!"a+b";

The goal is to craft the shortest code possible that is still
efficient and easy to follow.

- type deduction?


further comments whose application does not lead to immediate benefit:

- in contracts are better specified in their dedicated section to push
the requirements onto the caller.

- consider for(;;) as a means for indefinite looping.

- the convention is upper case for type names