Re: fastest method to choose a random element

On Jan 5, 5:12 pm, Paul Hankin <paul.han...@xxxxxxxxx> wrote:
On Jan 5, 4:14 pm, c...@xxxxxxxxxxxxxx wrote:

On Jan 5, 5:07 pm, c...@xxxxxxxxxxxxxx wrote:

Hello, Paul and Arnaud.
While I think about your answers: do you think there is any way to
avoid shuffle?
It may take unnecessary long on a long list most of whose elements
have the property.

You could generate a random shuffle of range(len(seq)) lazily, and use
that to iterate over your sequence.

import random
import itertools

def randxrange(n):
    "Generate the numbers 0 to n-1 in a random order"
    x = range(n)
    for i in xrange(n):
        r = random.randrange(n - i)
        yield x[r]
        x[r] = x[n - i - 1]

def shuffled(seq):
    "Generate the elements of seq in a random order"
    return (seq[i] for i in randxrange(len(seq)))

def pick_random(seq, prop):
    return itertools.ifilter(prop, shuffled(seq)).next()

At the risk of filling this thread with my posts, here's a much
simplified and faster version of this code that uses no extra storage.

import random

def pick_random(seq, prop):
L = len(seq)
for i in xrange(L):
r = random.randrange(L - i)
if prop(seq[r]):
return seq[r]
seq[r] = seq[L - i - 1]

--
Paul Hankin
.

Relevant Pages

  • Re: Self function
    ... Python ... giving the programmer the ability to have a function refer to ... def parrot: ...     print inspect.getmembers ...
    (comp.lang.python)
  • Re: What c.l.pys opinions about Soft Exception?
    ... Actually, the latter is even less cluttered, misses a raise - if pure number ... Exception that aren't handled when no handler exists for it. ...     raise_soft ... def a_equal_b: ...
    (comp.lang.python)
  • Re: multiprocessing question/error
    ...     def calcula: ... def m1: ... from multiprocessing import Process, Pool ... def m2(self, arg): ...
    (comp.lang.python)
  • Re: How to launch a function at regular time intervals ?
    ...     func.start ... from datetime import datetime ... """Write timestamp in a file every 10 seconds in separate ... def stop: ...
    (comp.lang.python)
  • Re: question of style
    ...     if self.lower is None: ... values- Iterate through the values in sort order. ... def insert: ...
    (comp.lang.python)