Three dumb questions (ordered by dumbness descending)

[Alex Martelli]

Terry Reedy wrote:

> 
> "Alex Martelli" <aleax at aleax.it> wrote in message
> news:82Zj9.136094$ub2.2966822 at news1.tin.it...
>> Once you do have a random or pseudo-random generator that fully
>> satisfies you, Ian Bicking's snippet reimplementing shuffle as a
>> Decorate-Sort-Undecorate idiom is truly excellent -- a little jewel,
> 
> How is an O(n*log(n)) algorithm a 'jewel' compared to the simple and
> standard O(n) algorithm?

Not performance-wise, by any means -- it just LOOKS deucedly pretty!-)


>> It does, alas, end up a little slower than Tim Peters' original --
> [...]
>>and Ian's version only loses very very little indeed.
> 
> Increase n enough and it becomes arbitrarily slower and loses
> arbitrarily much.

You're right -- I should have mentioned that.  If you must shuffle
lists whose length N you cannot bound, AND you have no other
bottlenecks in your program that are worse than O(N log N), then
introducing an O(N log N) bottleneck is clearly out of the
question.


Alex