2009/12/12 Fede Martinez <federicoemartinez@???>:
> 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@???
Para obtener el resto de direcciones-comando, mande un mensaje a:
pyar-help@???
PyAr - Python Argentina - Sitio web:
http://www.python.com.ar/
(text/plain)