El día 12/12/09, Matias Graña <matias.alejo@???> escribió:
>
> 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/
>
>
> Armar el heap es n*log(n) si vas agregando los elementos de a uno. Si tenes
todos en un arreglo y lo queres "heapifycar" lo podes hacer en O(n).
(text/plain)