search

ikalganov / aforge

Automatically exported from code.google.com/p/aforge
0 stars 0 forks source link

Slow performance of PermutationChromosome.CreateChildUsingCrossover #152

Closed GoogleCodeExporter closed 8 years ago

GoogleCodeExporter commented 8 years ago 
What steps will reproduce the problem?
1. Create setup using PermutationChromosome with genes > 1000
2. Use some profiler etc or timers
3. Crossover is very slow

What is the expected output? What do you see instead?

In the PermutationChromosome.CreateChildUsingCrossover method there is a loop 
which performs inner array scan/loops of the parent chromosome's genes 
resulting in very slow performance when the number of genes in a chromosome is 
large and also degrades in poor time as number of genes increase

It seems sensible to replace this with an indexed lookup.

I implemented a naive replacement of the original scan:

for (j = 0; j < k; j++)
    {
     if (parent1[j] == prev)
       break;
    }

To an index-lookup using a SortedList<ushort,int>:

if (parent1Index.ContainsKey(prev))
{
    j = parent1Index[prev];
}
else j = k;

This results in a dramatic improvement (hours to minutes) of the performance 
PermutationChromosome class when using chromosomes with large numbers of genes. 
Even if you just build the SortedList<> in a fairly naive fashion in the 
crossover.

Thanks,

Matthew.
mrdunn@gmail.com

Original issue reported on code.google.com by MRD...@gmail.com on 3 Sep 2010 at 4:49

GoogleCodeExporter commented 8 years ago 
Done some additional testing seems like Dictionary<> is a better choice, gives 
a further performance gain.

Original comment by MRD...@gmail.com on 3 Sep 2010 at 5:01

GoogleCodeExporter commented 8 years ago

Original comment by andrew.k...@gmail.com on 3 Sep 2010 at 5:36

GoogleCodeExporter commented 8 years ago 
Modified PermutationChromosome.CreateChildUsingCrossover() to use dictionaries 
for fast lookup of genes' indexes in parents' chromosomes.

Committed in revision 1337. Will be released in version 2.1.5.

Original comment by andrew.k...@gmail.com on 11 Nov 2010 at 3:42

GoogleCodeExporter commented 8 years ago 
Changed recent fix to use ordinary array instead of dictionaries, since those 
are not required here actually.

Original comment by andrew.k...@gmail.com on 25 Nov 2010 at 12:05

GoogleCodeExporter commented 8 years ago

Original comment by andrew.k...@gmail.com on 12 Jan 2011 at 11:41