[Python] Algoritmo in CSV

[Pietro Battiston]

Il giorno ven, 03/09/2010 alle 21.44 +0200, Pietro Zambelli ha scritto:
> 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...

Ah, ecco...

(il bello è che io l'avevo aggiunto, ma sbadatamente _prima_ di
"start=time.clock()"...)

> se aggiungi lista.sort() io ottengo:
> 
> Lista generata
> Max time: 0.09
> Sort time: 2.52
> 

... che in effetti è dell'ordine di grandezza di...

In [1]: 0.09 * log(2000000, 2)
Out[1]: 1.8838411712391756

ciao

Pietro