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

[Terry Jones]

>>>>> "Steven" == Steven D'Aprano <steve at pearwood.info> writes:
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.

Terry