fastest method to choose a random element

[ajaksu]

On Jan 5, 11:36 pm, c... at mailinator.com wrote:
>
> This one is good. Someone commented that you destroy the list, but
> that can be fixed:
>
>  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]= seq[L - i - 1],seq[r]
>
> just pushing elements without the property to the end of the list
> (list is mutated, true, but shuffle will do that too). In each
> iteration of the for loop, there is only one random element, one check
> of the property, and rebinding of elements without altering the lenght
> of the list. This is optimal and has all the functionality.
>
> Two more comments:
> for buzcor: deleting an element in the middle of a list is costly
> for martin: that is certainly enough for me
>
> Thanks everybody!

How about some benchmarks as a token of gratitude? ;) Or at least a
nice hint on your expected number of lists (and their sizes) :)