[Python] Algoritmo in CSV

[Andrea Ambu]

2010/9/3 Giuseppe Amato <giuamato a gmail.com>:
> 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?
>

In un array non ordinato e` necessario visitare tutti gli elementi una
volta per stabilirne il massimo, quindi l'algoritmo e` O(N) in tempo e
O(1) in spazio perche` ti conservi il massimo corrente.

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

Io non so quanto e come tu ci abbia lavorato ma se non ti sei confuso
con la notazione vorrei proprio sapere come fai il sorting tu! Nello
stato dell'arte degli algoritmi di sorting O(N) e` l'andamento
_desiderato_! ( http://en.wikipedia.org/wiki/Sorting_algorithm )


Tipicamente gli algoritmi buonivanno come O(nlog(n)), il TimSort di
Python va mediamente un po` meglio come O(log(N!)) anche se non
proprio formalmente, che e` comunque molto diverso da un andamento
lineare (che in questo caso e` gia` problematico) per N abbastanza
grande.

> Ma ripeto potrei sbagliare, allora ho scritto il semplice script di seguito
> e vi consiglio di provarlo e confrontare i risultati.
>

> [...]
>
> start=time.clock()
>
> print 'Sort time:',time.clock()-start
>
> [...]
>

Scusa ma stampi la differenza tra due tempi... senza fare il sort?


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

Il sort non puo` vincere su una array disordinato! Prova ad
immagginare di avere 100 numeri in fila, a mente/mano faresti prima a
trovare il massimo o a riordinarli? E` un esempio banale  ma dovrebbe
farti rendere conto della differenza che c'e` tra le due operazioni.

Comunque si parlava di lunghezza quindi probabilmente erano stringhe.



-- 
Andrea