Three dumb questions (ordered by dumbness descending)

[Terry Reedy]

"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?

> 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.

> import time, sys, operator
> from random import random
>
> def shuffle_org(x):
>     for i in xrange(len(x)-1, 0, -1):
>         # pick an element in x[:i+1] with which to exchange x[i]
>         j = int(random() * (i+1))
>         x[i], x[j] = x[j], x[i]
>
> def shuffle_ian(x):
>     newList = [(random(), i) for i in x]
>     newList.sort()
>     x[:] = [i[1] for i in newList]
>
>
> biggie = range(200)
>
> def timit(func, N=1000):
>     repeat = [None] * N
>     start = time.clock()
>     for x in repeat: func(biggie)
>     stend = time.clock()
>     return "%2.2f %s" % (stend-start, func.__name__)
>
> print sys.version
> for i in range(2):
>     for func in shuffle_org, shuffle_ian:
>         print timit(func)
>
>
> [alex at lancelot linud]$ python -O timo.py
> 2.2.1 (#2, Jul 15 2002, 17:32:26)
> [GCC 2.96 20000731 (Mandrake Linux 8.1 2.96-0.62mdk)]
> 1.59 shuffle_org
> 1.87 shuffle_ian
> 1.60 shuffle_org
> 1.86 shuffle_ian

2.2.1 (#34, Apr 15 2002, 09:51:39) [MSC 32 bit (Intel)]

biggie = range(20000)
def timit(func, N=10):
...
10.76 shuffle_org
19.25 shuffle_ian
10.75 shuffle_org
19.81 shuffle_ian

biggie = range(200000)
def timit(func, N=1):
...
11.24 shuffle_org
23.18 shuffle_ian

Terry J. Reedy