2009/12/12 Fede Martinez <federicoemartinez@gmail.com>:
> Si N es la cantidad de cosas que tenes, n las que queres sacar:
>
> El heap lo podes armar en O(N). Despues sacar el minimo te cuesta O(log(N)),
> como vas a sacar n veces el minimo, lo que te queda es un O(n*log(N))

Hasta donde entiendo, armar el heap es N.log(N). Pero igual tomar los
primeros n parece que está bien optimizado:

$ python -m timeit 'import random,heapq;
l=random.sample(xrange(100000000),1234567); m=sorted(l)[:10]'
10 loops, best of 3: 3.08 sec per loop

$ python -m timeit 'import random,heapq;
l=random.sample(xrange(100000000),1234567); m=heapq.nsmallest(10,l)'
10 loops, best of 3: 1.76 sec per loop

Matías

---------------------------------------------------------------------
Para dar de baja la suscripcion, mande un mensaje a:
   pyar-unsubscribe@decode.com.ar

Para obtener el resto de direcciones-comando, mande un mensaje a:
   pyar-help@decode.com.ar

PyAr - Python Argentina - Sitio web: http://www.python.com.ar/