Re: Is there a better way of doing this?

Discussion in 'Python' started by Peter Otten, Mar 6, 2009.

  1. Peter Otten

    Peter Otten Guest

    mattia wrote:

    > Hi, I'm new to python, and as the title says, can I improve this snippet
    > (readability, speed, tricks):
    >
    > 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, Mar 6, 2009
    #1
    1. Advertising

  2. Peter Otten

    Peter Otten Guest

    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
    >>> snippet (readability, speed, tricks):
    >>>
    >>> 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 in order to get the best individual, the last individual 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
    Peter Otten, Mar 6, 2009
    #2
    1. Advertising

  3. En Fri, 06 Mar 2009 21:31:01 -0200, mattia <> 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))

    Please recycle!

    --
    Gabriel Genellina
    Gabriel Genellina, Mar 7, 2009
    #3
  4. Peter Otten

    Paul Rubin Guest

    "Gabriel Genellina" <> 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
    Paul Rubin, Mar 7, 2009
    #4
  5. Peter Otten

    Lie Ryan Guest

    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 <> 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))
    >>
    >> Please recycle!

    >
    > Yes, sorry, I have to recycle! But how about this:
    >>>> 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]]
    Lie Ryan, Mar 7, 2009
    #5
  6. Peter Otten

    Peter Otten Guest

    Lie Ryan wrote:

    > mattia wrote:


    >> Yes, sorry, I have to recycle! But how about this:


    >>>>> 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
    Peter Otten, Mar 7, 2009
    #6
  7. 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
    if condition(x):
    del mylist


    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
    Steven D'Aprano, Mar 8, 2009
    #7
  8. Peter Otten

    Tim Wintle Guest

    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
    Tim Wintle, Mar 8, 2009
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Hardeep Rakhra

    A better way of doing this menu?

    Hardeep Rakhra, Feb 6, 2004, in forum: HTML
    Replies:
    6
    Views:
    399
    Hardeep Rakhra
    Feb 6, 2004
  2. Michael
    Replies:
    6
    Views:
    305
    Steven D'Aprano
    Jun 2, 2005
  3. Paul Rubin
    Replies:
    5
    Views:
    408
    Hendrik van Rooyen
    Aug 6, 2009
  4. Damjan Rems

    Is there a better way of doing this

    Damjan Rems, Apr 23, 2009, in forum: Ruby
    Replies:
    16
    Views:
    154
    Damjan Rems
    Apr 24, 2009
  5. Bill H

    Is there a better way of doing this?

    Bill H, Aug 24, 2007, in forum: Perl Misc
    Replies:
    5
    Views:
    77
    Bill H
    Aug 25, 2007
Loading...

Share This Page