Velocity Reviews > Re: Is there a better way of doing this?

# Re: Is there a better way of doing this?

Peter Otten
Guest
Posts: n/a

 03-06-2009
mattia wrote:

> Hi, I'm new to python, and as the title says, can I improve this snippet
>
> def get_fitness_and_population(fitness, population):
> return [(fitness(x), x) for x in population]
>
> def selection(fitness, population):
> '''
> Select the parent chromosomes from a population according to their
> fitness (the better fitness, the bigger chance to be selected)
> '''
> selected_population = []
> fap = get_fitness_and_population(fitness, population)
> pop_len = len(population)
> # elitism (it prevents a loss of the best found solution)
> # take the only 2 best solutions
> elite_population = sorted(fap)
> selected_population += [elite_population[pop_len-1][1]] +
> [elite_population[pop_len-2][1]]
> # go on with the rest of the elements
> for i in range(pop_len-2):
> # do something

def selection1(fitness, population, N=2):
rest = sorted(population, key=fitness, reverse=True)
best = rest[:N]
del rest[:N]
# work with best and rest

def selection2(fitness, population, N=2):
decorated = [(-fitness(p), p) for p in population]
heapq.heapify(decorated)

best = [heapq.heappop(decorated)[1] for _ in range(N)]
rest = [p for f, p in decorated]
# work with best and rest

Both implementations assume that you are no longer interested in the
individuals' fitness once you have partitioned the population in two
groups.

In theory the second is more efficient for "small" N and "large"
populations.

Peter

Peter Otten
Guest
Posts: n/a

 03-06-2009
mattia wrote:

> Il Fri, 06 Mar 2009 14:06:14 +0100, Peter Otten ha scritto:
>
>> mattia wrote:
>>
>>> Hi, I'm new to python, and as the title says, can I improve this
>>>
>>> def get_fitness_and_population(fitness, population):
>>> return [(fitness(x), x) for x in population]
>>>
>>> def selection(fitness, population):
>>> '''
>>> Select the parent chromosomes from a population according to their
>>> fitness (the better fitness, the bigger chance to be selected) '''
>>> selected_population = []
>>> fap = get_fitness_and_population(fitness, population) pop_len =
>>> len(population)
>>> # elitism (it prevents a loss of the best found solution) # take
>>> the only 2 best solutions
>>> elite_population = sorted(fap)
>>> selected_population += [elite_population[pop_len-1][1]] +
>>> [elite_population[pop_len-2][1]]
>>> # go on with the rest of the elements for i in range(pop_len-2):
>>> # do something

>>
>> def selection1(fitness, population, N=2):
>> rest = sorted(population, key=fitness, reverse=True) best = rest[:N]
>> del rest[:N]
>> # work with best and rest
>>
>>
>> def selection2(fitness, population, N=2):
>> decorated = [(-fitness(p), p) for p in population]
>> heapq.heapify(decorated)
>>
>> best = [heapq.heappop(decorated)[1] for _ in range(N)] rest = [p for
>> f, p in decorated]
>> # work with best and rest
>>
>> Both implementations assume that you are no longer interested in the
>> individuals' fitness once you have partitioned the population in two
>> groups.
>>
>> In theory the second is more efficient for "small" N and "large"
>> populations.
>>
>> Peter

>
> Ok, but the fact is that I save the best individuals of the current
> population, than I'll have to choose the others elements of the new
> population (than will be N-2) in a random way. The common way is using a
> roulette wheel selection (based on the fitness of the individuals, if the
> total fitness is 200, and one individual has a fitness of 10, that this
> individual will have a 0.05 probability to be selected to form the new
> population). So in the selection of the best solution I have to use the
> fitness to have a chance to be selected. Obviously the old population anf
> the new population must have the same number of individuals.

You're right, it was a bad idea.

Peter

Gabriel Genellina
Guest
Posts: n/a

 03-07-2009
En Fri, 06 Mar 2009 21:31:01 -0200, mattia <(E-Mail Removed)> escribió:

> Thanks, I've found another solution here:
> http://www.obitko.com/tutorials/
> genetic-algorithms/selection.php
> so here is my implementation:
>
>
> def get_fap(fitness, population):
> fap = []
> total = 0
> for x in population:
> f = fitness(x)
> fap += [(f, x)]
> total += f
> return sorted(fap, reverse=True), total

Imagine you're working with someone side by side. You write a note in a
piece of paper, put it into an envelope, and hand it to your co-worker. He
opens the envelope, throws it away, takes the note and files it inside a
folder right at the end. And you do this over and over. What's wrong in
this story?

Please save our trees! Don't waste so many envelopes - that's just what
this line does:

fap += [(f, x)]

Environmentally friendly Pythoneers avoid using discardable intermediate
envelopes:

fap.append((f, x))

--
Gabriel Genellina

Paul Rubin
Guest
Posts: n/a

 03-07-2009
"Gabriel Genellina" <(E-Mail Removed)> writes:
> > for x in population:
> > f = fitness(x)
> > fap += [(f, x)]
> > total += f
> > return sorted(fap, reverse=True), total

> ...
> Environmentally friendly Pythoneers avoid using discardable
> intermediate envelopes:
>
> fap.append((f, x))

I'd probably use:

fap = list((fitness(x),x) for x in population)
total = sum(x for x,y in fap)
return sorted(fap, reverse=True), total

Lie Ryan
Guest
Posts: n/a

 03-07-2009
mattia wrote:
> Il Sat, 07 Mar 2009 00:05:53 -0200, Gabriel Genellina ha scritto:
>
>> En Fri, 06 Mar 2009 21:31:01 -0200, mattia <(E-Mail Removed)> escribiÃ³:
>>
>>> Thanks, I've found another solution here:
>>> http://www.obitko.com/tutorials/
>>> genetic-algorithms/selection.php
>>> so here is my implementation:
>>>
>>>
>>> def get_fap(fitness, population):
>>> fap = []
>>> total = 0
>>> for x in population:
>>> f = fitness(x)
>>> fap += [(f, x)]
>>> total += f
>>> return sorted(fap, reverse=True), total

>> Imagine you're working with someone side by side. You write a note in a
>> piece of paper, put it into an envelope, and hand it to your co-worker.
>> He opens the envelope, throws it away, takes the note and files it
>> inside a folder right at the end. And you do this over and over. What's
>> wrong in this story?
>>
>> Please save our trees! Don't waste so many envelopes - that's just what
>> this line does:
>>
>> fap += [(f, x)]
>>
>> Environmentally friendly Pythoneers avoid using discardable intermediate
>> envelopes:
>>
>> fap.append((f, x))
>>

>
>>>> rw = [[2,4], [4,5,6],[5,5]]
>>>> rw += [[1,1]]*2
>>>> rw

> [[2, 4], [4, 5, 6], [5, 5], [1, 1], [1, 1]]
>>>> rw = [[2,4], [4,5,6],[5,5]]
>>>> rw.append([1,1]*2)
>>>> rw

> [[2, 4], [4, 5, 6], [5, 5], [1, 1, 1, 1]]
>>>> rw = [[2,4], [4,5,6],[5,5]]
>>>> rw.append([[1,1]]*2)
>>>> rw

> [[2, 4], [4, 5, 6], [5, 5], [[1, 1], [1, 1]]]
> How can I recicle in this way using append?

Not .append() but .extend()

>>> rw = [[2,4], [4,5,6],[5,5]]
>>> rw.extend([[1,1]]*2)
>>> rw

> [[2, 4], [4, 5, 6], [5, 5], [1, 1], [1, 1]]

Peter Otten
Guest
Posts: n/a

 03-07-2009
Lie Ryan wrote:

> mattia wrote:

>>>>> rw = [[2,4], [4,5,6],[5,5]]
>>>>> rw += [[1,1]]*2
>>>>> rw

>> [[2, 4], [4, 5, 6], [5, 5], [1, 1], [1, 1]]

>> How can I recicle in this way using append?

>
> Not .append() but .extend()

Whether you use

items += [item]*N

or

items.extend([item]*N)

is mostly a matter of style. You can avoid the intermediate list with

items.extend(itertools.repeat(item, N))

but I don't think this approach is faster.

Peter

Steven D'Aprano
Guest
Posts: n/a

 03-08-2009
Gabriel Genellina wrote:

> Imagine you're working with someone side by side. You write a note in a
> piece of paper, put it into an envelope, and hand it to your co-worker. He
> opens the envelope, throws it away, takes the note and files it inside a
> folder right at the end. And you do this over and over. What's wrong in
> this story?
>
> Please save our trees! Don't waste so many envelopes

Nice story, but the moral "conserve what you use" is not always good advice.
Bits are not envelopes -- sometimes it is more environmentally friendly to
throw them away and create new ones. Consider:

mylist[:] = [x for x in mylist if not condition(x)]

versus:

for i in xrange(len(mylist)-1, -1, -1):
x = mylist[i]
if condition(x):
del mylist[i]

The first "wastefully" creates a new list, and the second tries to recycle
bits by deleting the items in place. Unless mylist is so huge that your
computer starts thrashing trying to make two copies in memory, the first is
not only simpler to write and understand, but almost certainly much, much
faster than the second.

That's not the case in this specific example, but as a general principle,
it's worth remembering that it's often better to be wasteful with temporary
objects than to use miserly algorithms invented for machines with 64K of
memory.

(The same lessons can apply for re-world considerations as well. Recycling
doesn't just happen, it requires energy and water and other costs. If the
environmental costs of recycling something are worse than the environmental
costs of throwing it away and making a new one, then recycling that object
is actually harmful. But I digress.)

--
Steven

Tim Wintle
Guest
Posts: n/a

 03-08-2009
On Sun, 2009-03-08 at 15:49 +1100, Steven D'Aprano wrote:
> If the environmental costs of recycling something are worse than the
> environmental costs of throwing it away and making a new one, then
> recycling that object is actually harmful. But I digress.

Unless you live in a country that imports most of these goods, in which
case by recycling you keep money in the economy rather than buying goods
from elsewhere - it's never mentioned, but I'm fairly certain that's one
of the main reasons that the UK government loves forcing us to recycle
so much.

(obviously doesn't change how "environmentally harmful" something is)

Tim Wintle