[Python] Algoritmo in CSV
Pietro Zambelli
peter.zamb a gmail.com
Ven 3 Set 2010 21:44:50 CEST
In data venerdì 3 settembre 2010 21:10:11, Giuseppe Amato ha scritto:
> >Ma il problema vero è che il sort ha costo più che lineare, mentre il
> >
> >max ha costo lineare
>
> Non mi sono mai occupato di max finding quindi non so se è più veloce o
> meno, ho cercato qualcosa, ma con scarsi risultati, mi puoi indicare
> qualche risorsa dove trovare informazioni?
>
> Però mi sono occupato di sorting e il caso O(n) è uno dei peggiori
> (utilizzando algoritmi shell sort o quick sort), mentre O(log(n)) è più
> probabile ed è comunque minore di O(n) (200x2e6=2e8,
> 200xlog(2e6)=~1300,2e6xlog(200)=~4e6).
>
> Ma ripeto potrei sbagliare, allora ho scritto il semplice script di seguito
> e vi consiglio di provarlo e confrontare i risultati.
>
>
>
> #------------
>
> import time
>
> import random
>
>
>
> n=2000000
>
> lista=[]
>
> for i in range(n):
>
> lista.append(random.randint(0,10000000))
>
>
>
> print 'Lista generata'
>
> start=time.clock()
>
> max(lista)
>
> print 'Max time:',time.clock()-start
>
>
>
> start=time.clock()
>
> print 'Sort time:',time.clock()-start
>
> #-----------------
>
>
>
> Il sort vince sempre, va pari se invece di interi si devono confrontare
> classi. Ma il nostro amico doveva valutare interi se non ho capito male.
manca l'ordinamento della lista...
se aggiungi lista.sort() io ottengo:
Lista generata
Max time: 0.09
Sort time: 2.52
ciao!
pietro
Maggiori informazioni sulla lista
Python