[Python] Algoritmo in CSV

[Pietro Battiston]

Il giorno ven, 03/09/2010 alle 21.10 +0200, 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?

Non me ne sono mai occupato neanch'io, però

- controllare uno per uno gli elementi e confrontarli con il "massimo
finora" ha costo lineare
- non possono esistere algoritmi con costo meno che lineare perché
ognuno degli n elementi può essere il massimo cercato quindi qualcosa
dovrai pur farci

> 
> 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).

ehm... non, manca un "n" davanti a "log(n)"?

Per gli algoritmi di sorting il costo lineare è (solitamente) il caso
_ottimo_.

> 
> 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.

Già, (per me) piuttosto sorprendente. Deve avere a che fare con il costo
del singolo confronto, che evidentemente il cpython riesce a tenere
molto basso in sort di soli interi. Però ancora non riesco a spiegarmi
perché allora max(.) non venga definito come sort(.)[-1]. Enrico
sapresti illuminarmi?

ciao

Pietro