[Python] Algoritmo in CSV

Giuseppe Amato giuamato a gmail.com
Ven 3 Set 2010 21:10:11 CEST


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

 

Giuseppe

-------------- parte successiva --------------
Un allegato HTML  stato rimosso...
URL: http://lists.python.it/pipermail/python/attachments/20100903/89a8887d/attachment.htm 


Maggiori informazioni sulla lista Python