[Python-ideas] About adding a new iterator methodcalled "shuffled"

Jacob Holm jh at improva.dk
Tue Mar 24 23:22:11 CET 2009

Terry Jones wrote:
> Steven> On Wed, 25 Mar 2009 07:20:00 am Steven D'Aprano wrote:
>>> On Wed, 25 Mar 2009 03:03:31 am Raymond Hettinger wrote:
>>>>> On Tue, Mar 24, 2009, Roy Hyunjin Han wrote:
>>>>>> I know that Python has iterator methods called "sorted" and
>>>>>> "reversed" and these are handy shortcuts.
>>>>>> Why not add a new iterator method called "shuffled"?
>>>> You can already write:
>>>>        sorted(s, key=lambda x: random())
>>>> But nobody does that.  So you have a good
>>>> indication that the proposed method isn't needed.
>>> That's nice -- not as readable as random.shuffle(s) but still nice.  And
>>> fast too: on my PC, it is about twice as fast as random.shuffle() for
>>> "reasonable" sized lists (tested up to one million items).
> Note that using sorting to shuffle is likely very inefficient.
> The sort takes O(n lg n) comparisons whereas you can do a perfect
> Fischer-Yates (aka Knuth) shuffle with <= n swaps.  The model of
> computation here is different (comparisons vs swaps), but there is a vast
> literature on number of swaps done by sorting algorithms. In any case
> there's almost certainly no reason to use anything other than the standard
> Knuth shuffle, which is presumably what random.shuffle implements.
It is, I just checked. Other than implementing it in C, I don't see any 
way of significantly speeding this up.

- Jacob

More information about the Python-ideas mailing list