E' chiaro che l'algoritmo ha complessità O(N^2), e credo che anche nella teoria non si possa fare molto meglio, al limite O(N*log N)... (ebbene si, anche io ho studiato la teoria
); ho i miei dubbi che si possa raggiungere O(N).
E' chiaro anche, come dici, che dipende dai casi.
Nel caso attuale la lista non supera i 100 elementi e non è possibile cacharli perchè la lista su cui operare è diversa ad ogni esecuzione
Per numeri così piccoli, O(N^2) e O(N) non differiscono di molto.
Quello che provai a suo tempo aveva una lista di 500000 elementi e questo awk mi dava una performance decente, sicuramente migliore (ma moooolto migliore) di quello che feci io a suo tempo:
Codice: Seleziona tutto
cat pippo.txt |cut -c-1|sort -u >lista.txt
for a in `cat lista.txt`;do grep -m 1 ^$a pippo.txt;done
entrambi gli algoritmi hanno O(N^2)
anche il metodo sopradescritto
ha complessità O(N^2)
Ma quello che conta in un programma non è solamente O(qualcosa).
Quì compare:
1) il K, cioè il fattore moltiplicativo di O, che non so perchè mi è stato insegnato che se con un algoritmo ci voglio due istruzioni per elaborare un dato, e se con un algoritmo ce ne vuole uno, quando elabori N dati comunque si scrive O(N). Nel caso attuale, K influisce molto perchè è il tempo di accesso al disco. Nel caso dell'algoritmo con il ciclo for, ad ogni ciclo deve venir caricato il comando grep e pippo.txt (per fortuna esiste la cache). l'altro comando carica subito 5 comandi fissi in ram, ma deve eseguire 3 manipolazioni testuali e 2 ordinamenti. l'awk fa due accessi al disco, uno per il caricamento di awk e uno per il caricamento della lista (che poi, nel mio caso, viene fornita in pipe)
2) la ram che occupa. In questo caso ha poco senso perchè i numeri sono piccoli. Ma ho fatto recentemente un programma che per aumentare le performance teneva in ram dati ridondanti. I numeri sono cresciuti e la ram dedicata al programma (16M) è schioppata. Ho dovuto rifare buona parte dell'algoritmo.
3) la semplicità di scrittura e il tempo per scriverlo. talvolta preferisco fare un algoritmo non ottimizzato, ma semplice e veloce da scrivere (e da leggere) piuttosto che mettermi a fare 100 calcoli per scoprire quello migliore. E' quindi prassi comune fare due comandi quando è possibile darne uno.
4) l'eleganza (e si, va contato pure questo), sia di come è scritto sia di come esegue. scrivere awk ecc al posto di un grosso algoritmo più ottimizzato è decisamente meglio.
5) il collo di bottiglia. se so elaborare velocemente i dati, ma la fonte li genera lentamente è tutto un cavolo che mi sono scervellato.
6) appunto la diatriba tra teoria e pratica che dici... quello che funziona una volta non è garantito che funziona sempre, ma se l'insieme dei dati rientra in quelle che hanno già funzionato, non mi interessa che per altri casi potrebbe non funzionare. Per esempio, il caso con il for è sicuro che non funziona se all'interno del file ci sono spazi. Anzi, fastidio gli danno pure i punti (che grep interpreta come carattre jolly). E ancora, sempre nel caso del for, l'algoritmo non funziona se nel file ci sono parole e sottoinsiemi di queste parole
7) la probabilità di bug. più un algoritmo è complesso più ci può scappare il bug, anche se la teoria non contempla questo fattore
murphy: "dato un algoritmo deve accettare dati inseriti dall'utente, se l'algoritmo è stato scritto per contemplare tutte le possibili problematiche, l'utente puntualmente scoverà una unica eccezione che è sfuggita al programmatore"
vabbé, ho esagerato un poco, si potrebbe litigare all'infinito,
ingegneri informatici contro informatici teorici, fisici contro matematici, sistemisti contro programmatori.
Io sono un sistemista, e i sistemisti gli servono le cose veloci da ottenere, anche se approssimative.
Come programmatore mi ci diletto e basta.
.