[Java] ricerca e ordinamento

[wizard1993]

salve a tutti, nel mio studio dei linguaggi di programmazzione mi sono ritrovato ad affrontare i sistemi di ricerca e ordinamento.
ora dopo varie analisi mi sono posto alcuni quesiti che da solo non riesco a risolvere (ed essendo autodidatta) e che non so a chi chiedere
1)mettiamo un array utilizzato una sola volta nell'esecuzione di un programma, nel quale va ricercato un valore, qui io ho davanti due alternative: ricerca lineare o ordinamento+ricerca binaria.
se sceglo la prima so che nel caso peggiore avrò una complessità di O(n), se scelgo la seconda avrò per la ricerca una complessità pari a O(log n) più una complessità derivata dall'ordinamento che nel caso dei più efficenti sistemi è di O(n log n).
facendo ora due conti viene fuori che nel primo caso la complessità nel caso peggiore è O(n), nel secondo O(log n+n log n), difatto mettendo un array di 20 elementi nel primo caso avrei 20 confronti, nel secondo 2^4+ 20*2^4=336.
da qui si evince che il primo costa meno del secondo in termini di prestazioni, escludendo gli alberi binari ma operando solo su degli array, esistono altre scappatoie o effettivamente conviene la ricerca lineare?
2) dovendo ordinare una array mi conviene sfruttare un algoritmo di ordinamento, o mi conviene sfruttare gli alberi binari?

[wingman87]

Scusa ma log(20) non fa 2^4
Ad ogni modo devi considerare anche il fatto che in genere nel campo pratico le ricerche non si fanno su una quantità di elementi così piccola

PS: mi sono dimenticato di aggiungere che, sempre nel campo pratico, gli elementi non vengono ordinati nel momento in cui devi fare una ricerca ma in genere viene fatto un inserimento ordinato

[wizard1993]

Originariamente inviato da wingman87

Scusa ma log(20) non fa 2^4
Ad ogni modo devi considerare anche il fatto che in genere nel campo pratico le ricerche non si fanno su una quantità di elementi così piccola

PS: mi sono dimenticato di aggiungere che, sempre nel campo pratico, gli elementi non vengono ordinati nel momento in cui devi fare una ricerca ma in genere viene fatto un inserimento ordinato

per il primo punto considero il logaritomo di base due arrotondato per difetto fatto a mente (non trovo una calcolatrice che lo abbia)

per il secondo punto lo so, ma visto che solo per 20 elementi la dimensione aumenta, mi immagino cosa succede con un array di un miliardo, comunque il primo è più una sottigliezza teorica che un qualcosa che mi serve, quel che mi interessa è il secondo punto

[wingman87]

Originariamente inviato da wizard1993

per il primo punto considero il logaritomo di base due arrotondato per difetto fatto a mente (non trovo una calcolatrice che lo abbia)

per il secondo punto lo so, ma visto che solo per 20 elementi la dimensione aumenta, mi immagino cosa succede con un array di un miliardo, comunque il primo è più una sottigliezza teorica che un qualcosa che mi serve, quel che mi interessa è il secondo punto

Allora log(16)=4 e log(32)=5
Per il secondo punto vedi il PS del mio primo post

EDIT: Aggiungo anche che se non devi fare una sola ricerca ma diciamo n ricerche, è meglio fare l'ordinamento una volta e poi tutte le ricerche con il metodo binario.

[gugoXX]

Originariamente inviato da wizard1993

salve a tutti, nel mio studio dei linguaggi di programmazzione mi sono ritrovato ad affrontare i sistemi di ricerca e ordinamento.
ora dopo varie analisi mi sono posto alcuni quesiti che da solo non riesco a risolvere (ed essendo autodidatta) e che non so a chi chiedere
1)mettiamo un array utilizzato una sola volta nell'esecuzione di un programma, nel quale va ricercato un valore, qui io ho davanti due alternative: ricerca lineare o ordinamento+ricerca binaria.
se sceglo la prima so che nel caso peggiore avrò una complessità di O(n), se scelgo la seconda avrò per la ricerca una complessità pari a O(log n) più una complessità derivata dall'ordinamento che nel caso dei più efficenti sistemi è di O(n log n).
facendo ora due conti viene fuori che nel primo caso la complessità nel caso peggiore è O(n), nel secondo O(log n+n log n), difatto mettendo un array di 20 elementi nel primo caso avrei 20 confronti, nel secondo 2^4+ 20*2^4=336.
da qui si evince che il primo costa meno del secondo in termini di prestazioni, escludendo gli alberi binari ma operando solo su degli array, esistono altre scappatoie o effettivamente conviene la ricerca lineare?

Certo, se devi cercare qualcosa una volta sola, in un insieme disordinato, allora ti conviene la ricerca lineare.
Resta che se devi cercare l'esistenza di un valore in un insieme, la struttura migliore non e' la lista ordinata. La lista ordinata serve quando devi cercare range di valori (Es: Tutti i valori compresi tra X e Y), oppure quando devi cercare elementi per posizione in una lista ordinata secondo un criterio (ES: Voglio sapere qual e' il quinto elemento se avessi ordinato gli elementi con questo criterio)
Se invece devi cercare semplicemente l'esistenza di un valore in un insieme, la struttura migliore e' la hastable, che si costruisce in O(1) per ogni elemento (quindi O(n) per il tuo caso) e si interroga in poco piu' di O(1) ogni volta che si cerca qualcosa.

Quindi perche' non costruire la hastable anche nel tuo caso limite, ovvero quando si cerca una volta sola, dato che costa O(n)? Perche' la hastable occupa anche memoria, solitamente si approssima per eccesso in 2n, dove n e' l'occupazione della memoria della lista non ordinata di partenza (Sia che sia un array semplice, sia che sia una lista in senso stretto, ovvero in cui ogni elemento ha il proprio valore, e poi il riferimento (puntatore) al prossimo elemento della lista)
Quindi nel tuo caso la complessita' sarebbe O(n) comunque, e, non servendo piu' la hastable, "consumi meno" a scorrere tutta la lista disordinata e cercare il tuo elemento.

Ora, parentesi. E' la terza volta in 3 settimane che mi ritrovo a rinfrescare l'esistenza delle hashtable e dl loro utilizzo. Ma per caso non vengono piu' spiegate? Vengono spiegate male e non si capiscono? Booh?
edit: Scusa, ho visto ora che sei autodidatta, e quindi tanto di cappello per la tua volonta'.

2) dovendo ordinare una array mi conviene sfruttare un algoritmo di ordinamento, o mi conviene sfruttare gli alberi binari?

Io userei un algoritmo di ordinamento, ma solo a pelle, proprio perche' voglio ottenere un array ordinato.
Questo perche' se non sbaglio c'era qualcosa (un teorema? Boh?) che affermava che e' possibile rappresentare un albero binario come una lista ordinata, ma anche il viceversa. Secondo questa affermazione sarebbero equivalenti.

[wizard1993]

Originariamente inviato da gugoXX

...

questo è quello che volevo sapere.
Per l'ultimo caso però forse ho espresso male la mia richiesta: vorrei sapere se per ordinare un array è più conveniente sfruttare, che ne so, un quicksort, o un ordinamento con albero binario e poi ritirarlo fuori tramite una lettura inordine. ecco quello che vorrei, se non mi sbaglio a livello complessità computazionale il sistema ad albero binario è più efficente se non mi sbaglio log2 n in entrata e lo stesso valore in uscita quindi 2 *(log2 n ), mentre per un quicksort serve n*log n, quindi teoricamente è più conveniente un albero binario, solo che un array occupa meno memoria di un intera classe ricorsiva e si accede più velocemente a dei suoi elementi, quindi non so quanto tempo alla fine possa servire. secondo te quale è più conventiente?

[k0nt3]

Originariamente inviato da gugoXX

Se invece devi cercare semplicemente l'esistenza di un valore in un insieme, la struttura migliore e' la hastable, che si costruisce in O(1) per ogni elemento (quindi O(n) per il tuo caso) e si interroga in poco piu' di O(1) ogni volta che si cerca qualcosa.

in realtà una ricerca tramite hash table non è in O(1), ma nel caso peggiore è in O(d) dove d è numero di elementi che stanno nella tabella. ma in pratica l'efficienza di una hash table dipende dalla frequenza delle collisioni che a sua volta dipende dal rapporto fra numero massimo di elementi e grandezza della tabella e dalle funzioni di hash utilizzate.

nel caso in esame io userei:
- ricerca lineare se il numero di elementi non è molto grande
- lista ordinata (mediante inserimenti ordinati) + ricerca binaria se il numero di elementi è molto grande

[gugoXX]

Originariamente inviato da wizard1993

questo è quello che volevo sapere.
Per l'ultimo caso però forse ho espresso male la mia richiesta: vorrei sapere se per ordinare un array è più conveniente sfruttare, che ne so, un quicksort, o un ordinamento con albero binario e poi ritirarlo fuori tramite una lettura inordine. ecco quello che vorrei, se non mi sbaglio a livello complessità computazionale il sistema ad albero binario è più efficente se non mi sbaglio log2 n in entrata e lo stesso valore in uscita quindi 2 *(log2 n ), mentre per un quicksort serve n*log n, quindi teoricamente è più conveniente un albero binario, solo che un array occupa meno memoria di un intera classe ricorsiva e si accede più velocemente a dei suoi elementi, quindi non so quanto tempo alla fine possa servire. secondo te quale è più conventiente?

No, hai sbagliato il costo dell'albero binario.
Vediamo se riesco a farti capire in modo intuitivo il costo:
Immagina di essere a meta' dell'algoritmo di costruzione di un albero binario, ovvero che tu abbia gia' inserito N elementi della tua lista disordinata nell'albero, ma che te ne manchino altrettanti.
Devi inserire l'N+1 esimo. Quanto costa inserirlo? Costa Log(n), perche' log(n) saranno i confronti che dovrai fare (al massimo) per cercare la posizione giusta del tuo nuovo elemento.
E quindi, poiche' ogni elemento costa log(N) , ma tu hai N elementi da inserire nell'albero, ne consegue che anche costruire un albero binario a partire da un insieme disordinato costa N Log(N), proprio come il quicksort e altri algoritmi di ordinamento ottimi.
Anche perche' se avessi trovato un modo di ordinare una lista ordinata in meno di O( N LOG(n)), allora avresti trovato un algoritmo di ordinamento migliore del quicksort, mergesort, etc. E chi ce lo farebbe fare di studiare e usare ancora quegli algoritmi li' e non il tuo?

Concluderei quindi che in quanto a costo sono equivalenti. E questo rafforza la mia ipotesi di prima sul teorema che non ricordo piu', e che sicuramente non riusciro' a trovare.

[wizard1993]

Originariamente inviato da gugoXX

No, hai sbagliato il costo dell'albero binario.
Vediamo se riesco a farti capire in modo intuitivo il costo:
Immagina di essere a meta' dell'algoritmo di costruzione di un albero binario, ovvero che tu abbia gia' inserito N elementi della tua lista disordinata nell'albero, ma che te ne manchino altrettanti.
Devi inserire l'N+1 esimo. Quanto costa inserirlo? Costa Log(n), perche' log(n) saranno i confronti che dovrai fare (al massimo) per cercare la posizione giusta del tuo nuovo elemento.
E quindi, poiche' ogni elemento costa log(N) , ma tu hai N elementi da inserire nell'albero, ne consegue che anche costruire un albero binario a partire da un insieme disordinato costa N Log(N), proprio come il quicksort e altri algoritmi di ordinamento ottimi.
Anche perche' se avessi trovato un modo di ordinare una lista ordinata in meno di O( N LOG(n)), allora avresti trovato un algoritmo di ordinamento migliore del quicksort, mergesort, etc. E chi ce lo farebbe fare di studiare e usare ancora quegli algoritmi li' e non il tuo?

Concluderei quindi che in quanto a costo sono equivalenti. E questo rafforza la mia ipotesi di prima sul teorema che non ricordo piu', e che sicuramente non riusciro' a trovare.

ok, grazie a tutti

[gugoXX]

Originariamente inviato da k0nt3

in realtà una ricerca tramite hash table non è in O(1), ma nel caso peggiore è in O(d) dove d è numero di elementi che stanno nella tabella. ma in pratica l'efficienza di una hash table dipende dalla frequenza delle collisioni che a sua volta dipende dal rapporto fra numero massimo di elementi e grandezza della tabella e dalle funzioni di hash utilizzate.

nel caso in esame io userei:
- ricerca lineare se il numero di elementi non è molto grande
- lista ordinata (mediante inserimenti ordinati) + ricerca binaria se il numero di elementi è molto grande

Attento Kont, questo non e' un ragionamento corretto. Nelle valutazioni delle complessita' algoritmiche non si usa il caso peggiore. Altrimenti Quicksort sarebbe O(N^2) e non O(N logN). Anche l'insertion sort da te proposto degraderebbe in O(N^2) nel caso peggiore. Addirittura degrada a O(N^2) piu' in fretta del Quicksort. E' per questo che si preferisce il quicksort invece che l'insertion sort quando ci sono grandi quantitativi di dati da ordinare, in condizioni di limiti di memoria.

Direi quindi che nel caso della ricerca di esistenza la hastable continuerebbe ad essere la migliore anche valutando il caso peggiore.

[k0nt3]

Originariamente inviato da gugoXX

Attento Kont, questo non e' un ragionamento corretto. Nelle valutazioni delle complessita' algoritmiche non si usa il caso peggiore. Altrimenti Quicksort sarebbe O(N^2) e non O(N logN). Anche l'insertion sort da te proposto degraderebbe in O(N^2) nel caso peggiore. Addirittura degrada a O(N^2) piu' in fretta del Quicksort. E' per questo che si preferisce il quicksort invece che l'insertion sort quando ci sono grandi quantitativi di dati da ordinare, in condizioni di limiti di memoria.

Direi quindi che nel caso della ricerca di esistenza la hastable continuerebbe ad essere la migliore anche valutando il caso peggiore.

beh si usa il caso peggiore... non vedo perchè dovresti preferire un algoritmo che nel caso peggiore è in O(N^2) quando esistono algoritmi che nel caso peggiore sono in O(NlogN), come merge sort o heap sort.
comunque io non ho affatto consigliato insertion sort ho detto che nel caso in cui gli elementi sono molti è conveniente mantenere una lista ordinata mentre li si inseriscono. in questo modo è possibile usare una ricerca binaria.

[gugoXX]

Originariamente inviato da k0nt3

beh si usa il caso peggiore... non vedo perchè dovresti preferire un algoritmo che nel caso peggiore è in O(N^2) quando esistono algoritmi che nel caso peggiore sono in O(NlogN), come merge sort o heap sort.
comunque io non ho affatto consigliato insertion sort ho detto che nel caso in cui gli elementi sono molti è conveniente mantenere una lista ordinata mentre li si inseriscono. in questo modo è possibile usare una ricerca binaria.

Non ho capito il tuo ragionamento, dove sarebbe O(N^2) la hastable.
Comunque, nel caso peggiore, per costruire una hastable ci metto O(N), e per andare a cercare un valore invece che il "medio (non migliore)" O(1), ci metto di nuovo O(N), perche' tutti gli elementi sono collassati nella stessa chiave.
Quindi a costruirla ci metto O(N) e a cercare ci metto O(N).
Nel caso peggiore quindi siamo a O(N)+O(N) = O(N)

Nel caso medio di un algoritmo di ordinamento tra quelli ottimi, scegli quello che vuoi, ci metterai N LOG(N) ad ordinare, e LOG(N) a cercare.
NLOG(N) + LOG(N) = NLOG(N)

Mi sai dire dove ci guadagni a costruire la lista ordinata per poi cercare dentro?

Invece sul ragionamento "mantenere la lista ordinata mentre li si inseriscono" si puo' applicare sia alla hastable che al caso della lista ordinata.
Per inserire un elemento in una hastable ci metto O(1), per inserirlo in una lista gia' ordinata ci metto O(LOG(N)). Di nuovo, non vedo nessun vantaggio.

[k0nt3]

Originariamente inviato da gugoXX

Non ho capito il tuo ragionamento, dove sarebbe O(N^2) la hastable.

non ho mai affermato ciò
probabilmente non ci siamo capiti

ps. ah per il O(N^2) mi riferivo a quicksort.
quicksort in realtà è molto utilizzato perchè ha una complessità spaziale minore di molti altri algoritmi, non per la sua efficienza temporale (anche se un NlogN nel caso medio è di tutto rispetto)

Originariamente inviato da gugoXX

Comunque, nel caso peggiore, per costruire una hastable ci metto O(N), e per andare a cercare un valore invece che il "medio (non migliore)" O(1), ci metto di nuovo O(N), perche' tutti gli elementi sono collassati nella stessa chiave.
Quindi a costruirla ci metto O(N) e a cercare ci metto O(N).
Nel caso peggiore quindi siamo a O(N)+O(N) = O(N)

Nel caso medio di un algoritmo di ordinamento tra quelli ottimi, scegli quello che vuoi, ci metterai N LOG(N) ad ordinare, e LOG(N) a cercare.
NLOG(N) + LOG(N) = NLOG(N)

Mi sai dire dove ci guadagni a costruire la lista ordinata per poi cercare dentro?

infatti io non ho consigliato da nessuna parte di usare un algoritmo di ordinamento

Originariamente inviato da gugoXX

Invece sul ragionamento "mantenere la lista ordinata mentre li si inseriscono" si puo' applicare sia alla hastable che al caso della lista ordinata.
Per inserire un elemento in una hastable ci metto O(1), per inserirlo in una lista gia' ordinata ci metto O(LOG(N)). Di nuovo, non vedo nessun vantaggio.

il concetto di ordine degli elementi nell'hash table si perde, in ogni caso non è corretto dire che l'inserimento è in O(1). è in O(1) nel caso migliore, ma a questo punto anche nella lista ordinata l'inserimento è in O(1) nel caso migliore (cioè inserisco gli elementi dal più grande al più piccolo).
se valutiamo il caso peggiore allora l'inserimento nella hash table è in O(n) dove n indica il numero di elementi presenti nella hash table (cioè caso in cui l'elemento da inserire collide con tutti gli elementi già presenti).

[gugoXX]

Originariamente inviato da k0nt3

il concetto di ordine degli elementi nell'hash table si perde, in ogni caso non è corretto dire che l'inserimento è in O(1). è in O(1) nel caso migliore, ma a questo punto anche nella lista ordinata l'inserimento è in O(1) nel caso migliore (cioè inserisco gli elementi dal più grande al più piccolo).
se valutiamo il caso peggiore allora l'inserimento nella hash table è in O(n) dove n indica il numero di elementi presenti nella hash table (cioè caso in cui l'elemento da inserire collide con tutti gli elementi già presenti).

Ecco l'errore. il caso peggiore di inserimento in una hashtable e' sempre O(1).
Anche qualora tu avessi la collisione, e' suffiente appendere l'elemento alla lista degli elementi di quella chiave, tipicamente in coda o in testa. E' sempre O(1), anche nel caso collassato, non hai bisogno di scorrere tutti gli elementi per farlo.

[k0nt3]

Originariamente inviato da gugoXX

Ecco l'errore. il caso peggiore di inserimento in una hashtable e' sempre O(1).
Anche qualora tu avessi la collisione, e' suffiente appendere l'elemento alla lista degli elementi di quella chiave, tipicamente in coda o in testa. E' sempre O(1), anche nel caso collassato, non hai bisogno di scorrere tutti gli elementi per farlo.

beh nel caso in cui usi il chaining per risolvere le collisioni allora sì, gli inserimenti sono in O(1), io pensavo più ad altre soluzioni. cercare un elemento invece nel caso peggiore (tutti gli elementi collidono) è in O(n), quindi effettivamente potrebbe essere una scelta da prendere in considerazione. ma visto il contesto io non userei una hash table.. se ho pochi elementi la ricerca lineare è in O(n) sempre nel caso peggiore, mentre se ho molti elementi è molto meglio far sì che l'array sia ordinato proprio mentre lo si costruisce per poi poter fare ricerche in log(n) nel caso peggiore. su numeri grossi si vede la differenza.

ps. ciò non toglie che le hash table siano estremamente utili in molti contesti

[gugoXX]

Originariamente inviato da k0nt3

beh nel caso in cui usi il chaining per risolvere le collisioni allora sì, gli inserimenti sono in O(1), io pensavo più ad altre soluzioni. cercare un elemento invece nel caso peggiore (tutti gli elementi collidono) è in O(n), quindi effettivamente potrebbe essere una scelta da prendere in considerazione. ma visto il contesto io non userei una hash table.. se ho pochi elementi la ricerca lineare è in O(n) sempre nel caso peggiore, mentre se ho molti elementi è molto meglio far sì che l'array sia ordinato proprio mentre lo si costruisce per poi poter fare ricerche in log(n) nel caso peggiore. su numeri grossi si vede la differenza.

ps. ciò non toglie che le hash table siano estremamente utili in molti contesti

Allora, diciamo cosi'.
Se ti senti particolarmente sfortunato usa la lista ordinata, perche' inserisci in O(lOG(N)) e cerchi in O(LOG(N))

Se invece ti senti una persona nella media, allora usa la hashtable, inserisci in O(1) e cerchi in poco piu' di O(1).

Per questo problema, nei grandi numeri io preferisco la hastable, perche' nei grandi numeri e' probabile essere nella media.

Tu che algoritmo useresti per la cache nei microprocessori?
Preferiresti che ogni volta che il microprocessore cerca un indirizzo, allora lo va a cercare in O(Ln(N)) su tutta la cache e ogni volta che deve inserirne uno ci mette O(LN(N)) oppure preferiresti usare una hastable come effettivamente fanno?

[k0nt3]

Originariamente inviato da gugoXX

Allora, diciamo cosi'.
Se ti senti particolarmente sfortunato usa la lista ordinata, perche' inserisci in O(lOG(N)) e cerchi in O(LOG(N))

Se invece ti senti una persona nella media, allora usa la hashtable, inserisci in O(1) e cerchi in poco piu' di O(1).

ma anche no stai confrontando il caso pessimo del primo con il caso ottimo del secondo. in una hash table cerchi in O(n).

Originariamente inviato da gugoXX

Per questo problema, nei grandi numeri io preferisco la hastable, perche' nei grandi numeri e' probabile essere nella media.

Tu che algoritmo useresti per la cache nei microprocessori?
Preferiresti che ogni volta che il microprocessore cerca un indirizzo, allora lo va a cercare in O(Ln(N)) su tutta la cache e ogni volta che deve inserirne uno ci mette O(LN(N)) oppure preferiresti usare una hastable come effettivamente fanno?

ma non stiamo parlando della cache di un processore giusto?

[gugoXX]

Originariamente inviato da k0nt3

ma anche no stai confrontando il caso pessimo del primo con il caso ottimo del secondo. in una hash table cerchi in O(n).

In una hashtable si inserisce sempre in O(1), e nel caso medio si cerca in O(1)

Hash tables support the efficient insertion of new entries (O(1)), and the time spent searching for the required data is often independent of the number of items stored (O(1) on average).

ma non stiamo parlando della cache di un processore giusto?

Si', stiamo parlando dell'algoritmo della cache dei processori

Hash tables are often used to implement associative arrays, sets and caches

http://en.wikipedia.org/wiki/Hashtable

[k0nt3]

Originariamente inviato da gugoXX

In una hashtable si inserisce sempre in O(1), e nel caso medio si cerca in O(1)

sarebbe interessante sapere come hanno calcolato il caso medio, come minimo ci vorrebbero un paio di calcoli di probabilità.
ma in fondo non è che mi interessi più di tanto la faccenda, il mio consiglio l'ho dato e volevo solo precisare che le hash table non risolvono tutti i mali del mondo.

[gugoXX]

Originariamente inviato da k0nt3

sarebbe interessante sapere come hanno calcolato il caso medio, come minimo ci vorrebbero un paio di calcoli di probabilità.

Hanno solo riportato quello che e' stato calcolato da altri, non e' verbo di Wikipedia.

volevo solo precisare che le hash table non risolvono tutti i mali del mondo.

Ma questo e' poco ma sicuro.
Le hashtable non servono per rispondere a domande tipo:
Quale e' il piu' alto?
Quale e' il piu' basso?
Quale e' il sesto se li ordinassi con questo criterio?
Quali sono i valori tra 5 e 75, presenti in questo elenco?

Per queste risposte ci vuole il concetto di ordinamento, che una hastable classica non ha.
Una lista ordinata invece e' nella maggior parte dei casi il modo migliore, soprattutto se queste domande non sono spot, ma sono ripetute piu' volte nel tempo.

Ma per rispondere a una domanda come "C'e' il 753 in questo elenco di valori disordinati?", che e' proprio la domanda da cui e' partito questo post, allora la hashtable e' la soluzione ottima, soprattutto se la domanda e' ripetuta in modo simile piu' volte nel tempo.