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

[Jacob Holm]

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