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 _______________________________________________ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
