Sorting Lists Faster

[airerdem]

Hi,

I have following code but it is very slow during sorting.

list<double> fitness;

for(i=0;i<250;i++)
{
fitness.push_back(Random Number);
}

fitness.sort();

Is there any other method about list sorting ?

Thanks in advance
ico

[m4ster_r0shi]

Don't use a list. Use a vector or a deque and std::sort.

Useful links:

http://cplusplus.com/reference/stl/vector/
http://cplusplus.com/reference/stl/deque/
http://cplusplus.com/reference/algorithm/sort/

[m4ster_r0shi]

Hmmm... On second thought, a list of 250 doubles isn't really a big list.
Plus, list::sort's complexity is the same as std::sort's (N log N comparisons).

Are you really sure that sorting the list is what slows you down?

[airerdem]

Hmmm... On second thought, a list of 250 doubles isn't really a big list.
Plus, list::sort's complexity is the same as std::sort's (N log N comparisons).

Are you really sure that sorting the list is what slows you down?

Actually I launched the performance wizard in visual studio 2010 it showed bigger inclusive sample ratio in sorting lines. Is that mean this line slows down the program ?

[m4ster_r0shi]

Oh, I see. Is this an implementation of a genetic algorithm or something?

I'm not familiar with VS's performance wizard but
I can tell you a couple of things you can do...

First, since you already know the size of your container,
you can simply use an array instead of a list. Second,
you should declare it outside the loop. Something like...

#include <algorithm> // for std::sort

//...

double fitness[250];

loop_2000_times
{
    //...

    for(i = 0; i < 250; ++i)
        fitness[i] = random_number;

    std::sort(fitness, fitness + 250);

    //...
}

Doing it like this saves you creating and destroying your container 2000 times.
Also, using an array saves you the dynamic memory allocation overhead.

Now, what else is inside that loop that runs 2000 times?

[airerdem]

Oh, I see. Is this an implementation of a genetic algorithm or something?

I'm not familiar with VS's performance wizard but
I can tell you a couple of things you can do...

First, since you already know the size of your container,
you can simply use an array instead of a list. Second,
you should declare it outside the loop. Something like...

#include <algorithm> // for std::sort

//...

double fitness[250];

loop_2000_times
{
    //...

    for(i = 0; i < 250; ++i)
        fitness[i] = random_number;

    std::sort(fitness, fitness + 250);

    //...
}

Doing it like this saves you creating and destroying your container 2000 times.
Also, using an array saves you the dynamic memory allocation overhead.

Now, what else is inside that loop that runs 2000 times?

it is a genetic algorithm as you guessed. I already declared it outside the loop.

I think using array will be more efficient, I will try and let you know.

Thanks ;)

[airerdem]

But I need descending order that is why I used list, there is reverse() function.

Yours is ascending order right ?

[m4ster_r0shi]

This is not a real problem. You can...

(1) either traverse the array backwards after you sort it,
(2) or pass an extra argument to std::sort:

//...

bool compare(double d1, double d2) { return d1 > d2; }

//...

std::sort(fitness, fitness + 250, compare);

//...

Now, std::sort sorts in descending order.

I suspect that the first solution is faster.

[mike_2000_17]

As m4ster_r0shi said, you can use a different comparator to get a descending order for the sorting. I would just add that you can use the standard one instead of a custom compare() function, as so:

std::sort(fitness, fitness + 250, std::greater<double>()); //the default comparator is 'std::less<double>()'

And yes, definitely, an array (or an std::vector or std::deque) will be more efficient than a list in this case.

As this is a genetic algorithm, I would recommend you use a "tournament selection" instead of using all the data. For example, say you have 250 individuals and you plan to choose the "best" 50 for reproduction. Then, instead of sorting the entire array of 250 elements, you can pick 10 tournaments involving 10 random individuals from the population, sort those small 10-individual arrays and pick the best 5. This will be much more efficient and perform very well (I know by experience).