[RISOLTO] [awk?] eliminare duplicati da lista disordinata

[ZeroUno]

E' un problema che ebbi diverso tempo fa.
Non mi ricordo se chiesi quì o su usenet, ma non mi ricordo bene il comando per risolvere.

Supponiamo di avere una lista

ciao
pippo
pluto
topolino
pluto
minni
paperone
ciao
paperino

questa lista contiene dei duplicati che io voglio rimuovere.
il classico è sort -u, ma questo ha il difetto di lasciarmi la lista ordinata alfabeticamente, mentre io voglio ottenere
ciao
pippo
pluto
topolino
minni
paperone
paperino

cioè eliminate solo le seconde entry duplicate.

qualcuno per risolvere mi aveva detto awk con una certa sintassi, ma non me la ricordo più e non sono molto esperto (di awk conosco {print $1} e poco più).

Chi la sa?

[appo]

La soluzione più semplice sarebbe usare una hash table.

[Trotto@81]

Mario Vanoni saprò di certo aiutarti, senza nulla togliere agli altri.

[ZeroUno]

La soluzione più semplice sarebbe usare una hash table.

?!?!?
che intendi per usare una hash table?

se devo usare una cosa complicata uso questa:

Codice: Seleziona tutto

$ cat -n lista|sort -k2 |uniq -f1|sort -n|cut -f2-

ma quella in awk era più carina e performante.



EDIT: ho ritrovato il post, ed è decisamente una soluzione più elegante

Codice: Seleziona tutto

$ awk '!a[$0]++' lista

http://groups.google.it/group/it.comp.o ... 7af177b109

non sarei mai riuscito a ricostruirla da solo:

Quello che fa il programma e' molto semplice, lo puoi riscrivere cosi' che
probabilmente e' piu' leggibile:

Codice: Seleziona tutto

awk '!a[$0]{print} {a[$0]++}' file 

se a[<chiave>] vale 0, allora stampa la riga. Poi a[<chiave>] viene
incrementato di 1, Questo significa che verranno stampate solo le righe con
la prima occorrenza della chiave nel file.

[joseph]

Carina questa. Sinceramente non sapevo di tutte queste potenzialità di awk, mi sa che dovrò studiarmelo a fondo

[appo]

La soluzione più semplice sarebbe usare una hash table.

?!?!?
che intendi per usare una hash table?

se devo usare una cosa complicata uso questa:

Codice: Seleziona tutto

$ cat -n lista|sort -k2 |uniq -f1|sort -n|cut -f2-

ma quella in awk era più carina e performante.

Sull'efficienza non sono d'accordo. Ad ogni modo io mi occupo di teoria .

[ZeroUno]

Ad ogni modo io mi occupo di teoria .

Io mi occupo di pratica... se una cosa è sballata nella teoria e nella forma ma funziona beh... la uso!!

[appo]

Ad ogni modo io mi occupo di teoria .

Io mi occupo di pratica... se una cosa è sballata nella teoria e nella forma ma funziona beh... la uso!!

Recito la parte dello spocchioso. Quanto è lunga la lista? Quanti elementi distinti, in termini di valore atteso, ci saranno?
Senza entrare nella speciosa diàtriba tra teoria e pratica: quello che funziona una volta non è garantito che funzioni sempre .

[ZeroUno]

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

Codice: Seleziona tutto

$ cat -n lista|sort -k2 |uniq -f1|sort -n|cut -f2-

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.

[appo]

Oh, mamma, non volevo scatenare sto casino!
Solo qualche precisazione: quando lavori in memoria esterna, non usi la notazione O() in termini di numero di operazioni ma in termini di accessi alla memoria esterna. È il cosiddetto modello I/O.
In particolar modo, in tale modello, si trascurano tutte le operazioni effettuare in RAM, cosa per altro assai discutibile al giorno d'oggi. Ed il K di cui parli, quando si tratta di RAM, non si riferisce agli accessi alla memoria ma al fattore due a cui fai riferimento.
A parte queste piccolezze, capisco benissimo il tuo discorso e di fatto, come ho detto nel mio post, la mia era una amichevole provocazione, per usare un termine eccessivo.
Poi, "che te devo di'", c'è chi preferisce quick sort a merge sort!

[ZeroUno]

Poi, "che te devo di'", c'è chi preferisce quick sort a merge sort!

Non ricordo bene la differenza tra i due (che poi ce ne sono altri no? tipo il bubble sort e qualcun altro) in termini concettuale di forma, algoritmo e performance, ma se il primo si traduce letteralmente "ordinamento _semplice_" lo preferisco .
Tempo fa sono andato a vedere il sorgente di sort. Mi sembra che divide il file in chunk su file temporanei e li ordina, e poi alla fine li mette insieme.... questo è un merge sort?
Se ho capito bene si: Merge sort, Quicksort


A dire la verità c'è una cosa che preferisco di più di scrivere un algoritmo semplice...... non scriverlo affatto ed usare i prefatti (tipo sort buttato in pipe)... . Se poi ho bisogno di performance o di cose particolari... sicuramente su google trovo chi l'ha fatto prima di me



Beh, si, da come parlo sto mandando a farsi friggere i tre anni di studio alle superiori e i due esami di informatica all'università... ma che importa... basta che funziona......
In fondo di tutti i (pochi) esami che ho fatto, l'unico che veramente ho usato è 'sistemi operativi'.






Comunque, tornando al topic originale, tu come avresti fatto questo programma?