Post by Alex MartelliPost by bhooLe liste nascondono al programmatore la gestione della memoria e tanto
meno sono la migliore soluzione per quanto riguarda la velocità di
esecuzione.
Non ti pare?
Non necessariamente. Tanto per avere un punto di riferimento
in comune, partiamo ad esempio con la Bibbia in inglese che e`
qui parli di prestazioni migliori..
Precisamente rispondo alla tua asserzione sul fatto che "le liste ...
tanto meno sono la migliore soluzione per quanto riguarda la velocita`
di esecuzione".
Analizza piuttosto il codice in C++, che paragona direttamente
l'uso di vettori (std::vector) e liste (std::list) mostrando che
non vi e` misurabile differenza nelle prestazioni ottenibili (e
quindi le liste sono a pari merito con i vettori, per questo
problema e su questa macchina, in termini di velocita` di esecuzione).
(ovviamente queste sono domande per capire meglio quello che vuoi dire)
Sai meglio di me (visto che ne sei un programmatore) che python è scritto
in C e qualsiasi algoritmo scritto in c puo' essere tradotto "quasi"
Non necessariamente: Python e` un _linguaggio_, le sue _implementazioni_
poi possono essere fatte in C (come e` Classic Python), in Java (come
e` Jython), in O'CAML (come e` Vyper), in Python stesso (come e` pypy),
in codice macchina (come e` per le accelerazioni eseguite dal compilatore
just-in-time psyco), in C# (come e` Python.NET), o in qualsiasi altro
linguaggio sufficientemente potente (e quasi tutti i linguaggi di
programmazione sono "Turing-completi" e quindi _per definizione_ potenti
a sufficienza per qualsiasi compito computabile, anche se naturalmente
in practica certi linguaggi possono essere pragmaticamente troppo onerosi
per farlo davvero -- ad esempio non vorrei certo dover programmare un
runtime Python in macro del vecchio vi, anche se e` dimostrabile che
dette macro costituiscono un linguaggio Turing-completo:-).
immediamente in codice c++ con "quasi" identiche prestazioni(poi dipende
dal compilatore).
Non so cosa intendi per "quasi immediatamente". Certamente puoi tradurre
codice fra due qualsiasi linguaggi Turing-completi (per definizione), ma
se per "quasi immediatamente" intendi che lo sforzo e` trascurabile, sbagli,
e cosi` pure nel ritenere che le prestazioni siano necessariamente "quasi
identiche" -- in realta` c'e` spazio per molte variazioni.
Ad esempio, il rutime di pypy nella prima versione "puramente didattica"
riusciva a rallentare di MIGLIAIA di volte l'esecuzione, poi gradualmente
aggiungendo le varie ottimizzazioni "ovvie" (tipo implementare i dizionari
con hashing invece che con l'equivalente di "liste d'associazione") si
torna grosso modo alle stesse prestazioni -- e, si spera, le si superera`,
in futuro, scatenando tutta la potenza delle analisi just-in-time alla
psyco (non a caso l'architetto principale di pypy e` lo stesso Armin Rigo
che e` l'autore di psyco, anche se a dargli una mano a tempo perso siamo
parecchi -- io, Samuele Pedroni [di Jython], Guido van Rossum [architetto
di Python], Christian Tismer [padre di Stackless Python], ecc, ecc).
Ma tutto questo non ha nulla a che vedere con la tua errata asserzione
riguardo le prestazioni delle liste.
Post by Alex Martellireturn len(s.split())
questa funzione richiama un codice C ....
No, richiama delle funzionalita` primitive ("intrinseche", ovvero
"built-in") di Python, che possono poi internamente essere implementate
in una miriade di modi diversi, vedi sopra. Se il Python in gioco e`
quello Classic, le due primitive in gioco sono in effetti codificate
attualmente in C.
Post by Alex Martellireturn [ (word_count(s), s) for s in file(filename) ]
anche qui si richiama codice C ....
Vedi sopra. Qui poi gran parte del lavoro e` fatto da primitive del
sistema operativo, che possono essere implementare in una miscela di
C e di linguaggio macchina (il C e` normalmente piu` usato al giorno
d'oggi, ma un minimo di linguaggio macchina generalmente resta).
Post by Alex Martelliitems = read_file("kjv.txt")
print "tot versetti", len(items)
items.sort()
print "primo:", items[0][1]
print "ultimo:", items[-1][1]
main()
e lo stesso qui ..
Ulteriormente, vedi sopra.
Mettiamo da parte anche i ritardi dovuti all'interprete per tutti i suoi
controlli,vorrei capire come fai a dire che il tuo codice abbia
prestazioni migliori di un altro scritto in C/C++ ?
Ho postato interamente i due programmi in C++ standard (sono molto
simili: uno usa le liste, l'altro i vettori) nonche` quello in Python
(Python 2.3 rigorosamente standard, ma compatibile anche con 2.2 --
non uso nessuna delle piccolissime aggiunte fatte nella 2.3). Quindi,
basta (anzitutto compilare, se si usano linguaggi che non compilano in
modo automatico e trasparente come Python, poi) eseguire e misurare le
prestazioni dei programmi per vedere, su di una particolare macchina
con la sua data dotazione di HW e SW, come vanno le prestazioni.
Naturalmente basta che cambi l'HW o il SW e le prestazioni potrebbero
similmente cambiare. Appunto facevo notare come la misurazione delle
prestazioni del programmino Python mostra piu` pagefault dell'assai
piu` verboso programma C++, per cui, se si deve girare su macchine con
una memoria virtuale molto male implementata (com'era tipico ad es.
delle prime release di Win/95), gia` solo questo _potrebbe_ fare una
differenza cruciale. Solo MISURANDO, in condizioni specifiche, si puo`
vedere cosa DAVVERO succede -- asserzioni astruse ed astratte come la
tua contro le prestazioni delle liste non possono dircelo (e infatti
l'uso di liste o vettori si dimostra irrilevante negli esempi C++ che
ho portato -- ancora, ripetiamolo, per le specifiche condizioni di
misurazione che ho accuratamente specificato).
Per fare un confronto valido bisognerebbe prendere lo stesso codice usato
da python e non un algoritmo che si presume identico...
Ma che balle dici? Se vuoi ad esempio confrontare le prestazioni di
un programma Java con quelle di un programma "esattamente equivalente"
(cioe` che svolge esattamente gli stessi compiti) scritto in C++, come
diavolo potresti "prendere lo stesso codice usato"?! E` ovvio che quel
che fai e` (per quanto possibile) garantire uso equivalente delle ben
diverse librerie standard dei due linguaggi, poi misuri le prestazioni
complessive comprese le qualita` di compilatori, libreria, JVM e suo
eventuale JIT nel caso di Java, sistema operativo, HW sottostante, ecc
ecc. E` solo su queste basi che si sente spesso affermare che C++ (per
molti compiti) e` "piu` veloce di Java", o al contrario che (in alcuni
specifici casi in cui un buon JIT puo` veramente sfoggiare le sue
caratteristiche) in quel dato programma Java puo` battere C++.
Se pensi che (ad esempio) Andrew Koenig e Barbara Moo abbiano pubblicato
un algoritmo poco performante per il conteggio delle parole (separate
da spazi bianchi) in una stringa, puoi facilmente pubblicare (forse
meglio su it.comp.lang.c++) il tuo algoritmo alternativo mostrandone
le svettanti prestazioni. Ecc, ecc.
Comunque, tutti questi dettagli non giustificano la tua errata
affermazione sopra riportata: se eventualmente potessi migliorare
l'algoritmo di conteggio delle parole, questo miglioramento avrebbe
eguale effetto sia sulla versione del programma C++ che usa le
liste, sia su quella che usa i vettori. Alla fin fine la differenza
per questo programma si riduce a:
-- costo di push_back su std::vector rispetto a std::list, e
-- costo di std::sort su std::vector rispetto a std::list::sort
Punto e basta. Ovviamente questi due costi dipendono poi solo ed
esclusivamente dalla qualita` di implementazione delle librerie
standard del C++ che hai a disposizione: lo standard C++ precisa
_ALCUNI_ aspetti relativi alle prestazioni delle librerie, ad esempio
"sai" che N push_back sul vector DEVONO avere un costo ammortizzato
O(N) ed e` vietato alle librerie usare "scorciatoie" che potrebbero
causare costi O(N^2) o che, ma si tratta appunto sempre di specifiche
del tipo O(), quindi "al netto di costanti" anche moltiplicative...
e quindi, ancora una volta, se le prestazioni ti interessano davvero
non hai proprio alternative rispetto a implementare le alternative
che stai considerando e MISURARE (sulle macchine di tuo interesse,
con sistemi operativi idem, ecc, ecc). A volte puoi risparmiarti,
almeno in teoria, di misurare alternative che "sai" porterebbero a
veri disastri prestazionali [del tipo O()], ma attenzione che se devi
trattare problemi "piccoli" a volte un algoritmo con un brutto O()
puo` essere comunque meglio se le sue constanti sono meravigliosamente
piu` piccole dell'algoritmo con un O() piu` soddisfacente (se puoi
pagare il prezzo, puo` persino convenirti implementare molteplici
algoritmi e commutare fra loro a seconda di stime o indicatori sulle
"dimensioni" in gioco per ogni specifico problema o sottoproblema:
un simile "fall-back" e` spesso fondamentale ad esempio nelle varie
implementazioni recursive di algoritmi di sort, visto che ad es. un
insertion sort e` certamente inaccettabile [O(N^2)] per problemi
grandi, ma quando via via suddividendo arrivi a N abbastanza piccoli
l'insertion sort puo` essere il modo giusto di trattare questi
"piccoli sottoproblemi" in cui scomponi il problemone quello grande).
Alex