Efficienza algoritmo di ordinamento
- Claudio_F
- Entusiasta Emergente
- Messaggi: 1463
- Iscrizione: lunedì 28 maggio 2012, 18:49
- Desktop: Mate/Gnome
- Distribuzione: Ubu22.04
Re: Efficienza algoritmo di ordinamento
Credo che il quick sort sia troppo veloce per notare grosse differenze. Sarebbe da provare con un metodo di sort MOLTO più pesante, come il bubble sort.
-
- Imperturbabile Insigne
- Messaggi: 2739
- Iscrizione: mercoledì 16 gennaio 2013, 17:28
- Desktop: ubuntu-2d
- Distribuzione: Ubuntu 12.04.2 LTS i686
- Località: Airuno(Lecco)
Re: Efficienza algoritmo di ordinamento
Provo a implementare con python che usa un mix tra mege e insertion sort se non erro, e cambia anche in base alla lunghezza dell'input.
In C non ci sono sostanziali differenze
In C non ci sono sostanziali differenze
- DoctorStrange
- Imperturbabile Insigne
- Messaggi: 2855
- Iscrizione: mercoledì 14 ottobre 2015, 9:33
- Desktop: Gnome3
- Distribuzione: Ubuntu 22.04 LTS Jammy Jellyfish
- Sesso: Maschile
- Località: Roma, Italia
Re: Efficienza algoritmo di ordinamento
Ma le differenze si trovano nella sola parte di merge. Se le due liste sono già ordinate separatamente, l'algoritmo si riduce a prendere sempre l'elemento piu basso preso dalle due liste per popolare la lista finale.
Qui la discussione non era sull'efficienza di ordinare una collection di elementi, ma di sapere se il merge di due liste già ordinate era piu efficiente. Se la domanda è rimasta quella originale del mio post di apertura, allora la risposta è si. Altrimenti, se vuoi sapere quale algoritmo di ordinamento è piu efficiente c'è letteratura accademica molto specifica in merito.
Qui la discussione non era sull'efficienza di ordinare una collection di elementi, ma di sapere se il merge di due liste già ordinate era piu efficiente. Se la domanda è rimasta quella originale del mio post di apertura, allora la risposta è si. Altrimenti, se vuoi sapere quale algoritmo di ordinamento è piu efficiente c'è letteratura accademica molto specifica in merito.
-
- Imperturbabile Insigne
- Messaggi: 2739
- Iscrizione: mercoledì 16 gennaio 2013, 17:28
- Desktop: ubuntu-2d
- Distribuzione: Ubuntu 12.04.2 LTS i686
- Località: Airuno(Lecco)
Re: Efficienza algoritmo di ordinamento
Ma infatti è quello che ho fatto: uno script che unisce due liste disordinate e poi fa il sort.Qui la discussione non era sull'efficienza di ordinare una collection di elementi, ma di sapere se il merge di due liste già ordinate era piu efficiente. Se la domanda è rimasta quella originale del mio post di apertura, allora la risposta è si. Altrimenti, se vuoi sapere quale algoritmo di ordinamento è piu efficiente c'è letteratura accademica molto specifica in merito.
Il secondo le ordina prima poi le fonde con il merge.
Lascia stare l'algoritmo che ho usato (quick sort) e il linguaggio, quello è perchè ero comodo così.
Dei 2 script non si nota molta differenza in termini di prestazione.
Forse ho inteso male io, ma bho...
- Claudio_F
- Entusiasta Emergente
- Messaggi: 1463
- Iscrizione: lunedì 28 maggio 2012, 18:49
- Desktop: Mate/Gnome
- Distribuzione: Ubu22.04
Re: Efficienza algoritmo di ordinamento
Scrivi un bubble sort base non ottimizzato ( n * n-1 iterazioni) per ordinare due array da 1000 e farne il merge, oppure per ordinare UN array da 2000 (inutile fare il merge su array non ordinati, si ottiene solo un altro array non ordinato), e vedrai che in un caso ci mette il doppio.
- vaeVictis
- Imperturbabile Insigne
- Messaggi: 4703
- Iscrizione: venerdì 27 luglio 2012, 17:58
- Desktop: Gnome
- Distribuzione: Ubuntu 20.04 64bit
Re: Efficienza algoritmo di ordinamento
Beh, in soldoni quello che sta facendo l'OP è una sorta di parallelizzazione dell'algoritmo.
Prende la lista, la divide in due, due processi/thread ordinano una singola lista per uno, poi la riuniscono.
In teoria, il tempo risultante per ordinare le due liste separatamente e poi riunirle dovrebbe essere la metà del tempo utilizzato per ordinare la lista "complessiva" più il tempo necessario per riunire le due liste, che è in effetti trascurabile se si considera che è lineare, mentre l'ordinamento è quadratico.
Tutto questo, ovviamente, se i due processi lavorano istantaneamente e contemporaneamente. Se uno ordina una lista oggi e l'altro ordina la seconda lista domani (perché magari ha ricevuto i dati più lentamente), il discorso non è più valido.
Se vi capita sotto mano "Concurrency in Action" di Anthony Williams (che tra l'altro mi ha anche mitologicamente risposto su StackOverflow a una domanda su quel capitolo che ora menziono), leggetevi il capitolo sul sorting parallelizzato, nel caso specifico parallelizza il quicksort. Tutto il libro merita, ma questo capitolo è attinente alla discussione
Prende la lista, la divide in due, due processi/thread ordinano una singola lista per uno, poi la riuniscono.
In teoria, il tempo risultante per ordinare le due liste separatamente e poi riunirle dovrebbe essere la metà del tempo utilizzato per ordinare la lista "complessiva" più il tempo necessario per riunire le due liste, che è in effetti trascurabile se si considera che è lineare, mentre l'ordinamento è quadratico.
Tutto questo, ovviamente, se i due processi lavorano istantaneamente e contemporaneamente. Se uno ordina una lista oggi e l'altro ordina la seconda lista domani (perché magari ha ricevuto i dati più lentamente), il discorso non è più valido.
Se vi capita sotto mano "Concurrency in Action" di Anthony Williams (che tra l'altro mi ha anche mitologicamente risposto su StackOverflow a una domanda su quel capitolo che ora menziono), leggetevi il capitolo sul sorting parallelizzato, nel caso specifico parallelizza il quicksort. Tutto il libro merita, ma questo capitolo è attinente alla discussione
Pirates arrrrrrrrrrr awesome!!!
«I fear not the man who has practiced 10000 kicks once,
but I fear the man who has practiced one kick 10000 times.»
«I fear not the man who has practiced 10000 kicks once,
but I fear the man who has practiced one kick 10000 times.»
-
- Imperturbabile Insigne
- Messaggi: 2739
- Iscrizione: mercoledì 16 gennaio 2013, 17:28
- Desktop: ubuntu-2d
- Distribuzione: Ubuntu 12.04.2 LTS i686
- Località: Airuno(Lecco)
Re: Efficienza algoritmo di ordinamento
Bho, mi sa che non hai dato un'occhiata a i codici, io faccio il merge su 2 array ordinati:...(inutile fare il merge su array non ordinati, si ottiene solo un altro array non ordinato), e vedrai che in un caso ci mette il doppio.
sort array1, sort array 2, poi merge.
Altro codice: array1+array2(non ordinati) poi sort globale.
Se un algoritmo non è ottimizzato o efficiente cade a priori il discorso direi, no?...Scrivi un bubble sort base non ottimizzato...
Comunque non voglio "impossessarmi" di 3d non mio, non vi seguo, nel senso che ho fatto come richiede l'autore e non noto sostanziali differenze
Ultima modifica di gila75 il mercoledì 18 maggio 2022, 20:28, modificato 1 volta in totale.
- vaeVictis
- Imperturbabile Insigne
- Messaggi: 4703
- Iscrizione: venerdì 27 luglio 2012, 17:58
- Desktop: Gnome
- Distribuzione: Ubuntu 20.04 64bit
Re: Efficienza algoritmo di ordinamento
No, anche se l'algoritmo non fosse ottimizzato ma tu avessi comunque l'espressione della sua complessita temporale (che in questo caso hai) potresti vedere che hai un fattore 1/2. E' sempre lo stesso algoritmo con la stessa complessità che viene applicato a input differenti. Stesso discorso se non riesci a calcolare matematicamente la complessità, ma hai l'algoritmo. Te la ricavi empiricamente facendolo girare su diversi input e vedi come il tempo di esecuzione varia in funzione dell'input fornito.
L'unica cosa che a te interessa, indipendentemente che tu possa calcolare la complessita matematicamente o ricavarla empiricamente, è che la complessità dell'algoritmo di "fusione" delle due liste sia minore della differenza della complessità dell'algoritmo sui diversi input.
Ovviamente, il discorso non ha più senso se la complessità varia (in senso funzionale) a seconda dell'input. In questo caso, su un input che è la metà di un altro, potrebbe avere due valor diversi.
Nota bene: quando scrivo "diversi input", in questo caso intendo liste di differente lunghezza.
L'unica cosa che a te interessa, indipendentemente che tu possa calcolare la complessita matematicamente o ricavarla empiricamente, è che la complessità dell'algoritmo di "fusione" delle due liste sia minore della differenza della complessità dell'algoritmo sui diversi input.
Ovviamente, il discorso non ha più senso se la complessità varia (in senso funzionale) a seconda dell'input. In questo caso, su un input che è la metà di un altro, potrebbe avere due valor diversi.
Nota bene: quando scrivo "diversi input", in questo caso intendo liste di differente lunghezza.
Pirates arrrrrrrrrrr awesome!!!
«I fear not the man who has practiced 10000 kicks once,
but I fear the man who has practiced one kick 10000 times.»
«I fear not the man who has practiced 10000 kicks once,
but I fear the man who has practiced one kick 10000 times.»
-
- Imperturbabile Insigne
- Messaggi: 2739
- Iscrizione: mercoledì 16 gennaio 2013, 17:28
- Desktop: ubuntu-2d
- Distribuzione: Ubuntu 12.04.2 LTS i686
- Località: Airuno(Lecco)
Re: Efficienza algoritmo di ordinamento
Mi sfugge evidentemente qualcosa allora. Fusione e merge hanno tempi pressochè uguali, non capisco. Mi faccio da parte se no creo confusione. Cerco di elaborare il concetto in dispartevaeVictis ha scritto: ↑mercoledì 18 maggio 2022, 20:26No, anche se l'algoritmo non fosse ottimizzato ma tu avessi comunque l'espressione della sua complessita temporale (che in questo caso hai) potresti vedere che hai un fattore 1/2. E' sempre lo stesso algoritmo con la stessa complessità che viene applicato a input differenti. Stesso discorso se non riesci a calcolare matematicamente la complessità, ma hai l'algoritmo. Te la ricavi empiricamente facendolo girare su diversi input e vedi come il tempo di esecuzione varia in funzione dell'input fornito.
L'unica cosa che a te interessa, indipendentemente che tu possa calcolare la complessita matematicamente o ricavarla empiricamente, è che la complessità dell'algoritmo di "fusione" delle due liste sia minore della differenza della complessità dell'algoritmo sui diversi input.
Ovviamente, il discorso non ha più senso se la complessità varia (in senso funzionale) a seconda dell'input. In questo caso, su un input che è la metà di un altro, potrebbe avere due valor diversi.
Nota bene: quando scrivo "diversi input", in questo caso intendo liste di differente lunghezza.
- vaeVictis
- Imperturbabile Insigne
- Messaggi: 4703
- Iscrizione: venerdì 27 luglio 2012, 17:58
- Desktop: Gnome
- Distribuzione: Ubuntu 20.04 64bit
Re: Efficienza algoritmo di ordinamento
Ho scritto fusione, ma intendevo merge.
Comunque c'è poco da capire. Puoi avere una lamborghini (algoritmo perfermante) o una panda (algoritmo non performante ma che ignora la scarsa attitudine alla performance e quindi performa lo stesso).
Sia con la lamborghini, sia con la panda, per fare 100 km ci metterai un tot.
Se alle stesse macchine (che siano lamborghini o panda) fai fare 50 km, vedrai che ci metteranno la metà del tempo che la stessa macchina ha impiegato a farne il doppio, ossia 100 km.
Non mi pare ci sia molto da capire. Per fare il doppio del lavoro, indipendentemente da quanto sei bravo, ci metti il doppio del tempo (se ovviamente la tua complessità è lineare, altrimenti ti regoli di conseguenza per altri andamenti).
Comunque c'è poco da capire. Puoi avere una lamborghini (algoritmo perfermante) o una panda (algoritmo non performante ma che ignora la scarsa attitudine alla performance e quindi performa lo stesso).
Sia con la lamborghini, sia con la panda, per fare 100 km ci metterai un tot.
Se alle stesse macchine (che siano lamborghini o panda) fai fare 50 km, vedrai che ci metteranno la metà del tempo che la stessa macchina ha impiegato a farne il doppio, ossia 100 km.
Non mi pare ci sia molto da capire. Per fare il doppio del lavoro, indipendentemente da quanto sei bravo, ci metti il doppio del tempo (se ovviamente la tua complessità è lineare, altrimenti ti regoli di conseguenza per altri andamenti).
Pirates arrrrrrrrrrr awesome!!!
«I fear not the man who has practiced 10000 kicks once,
but I fear the man who has practiced one kick 10000 times.»
«I fear not the man who has practiced 10000 kicks once,
but I fear the man who has practiced one kick 10000 times.»
-
- Imperturbabile Insigne
- Messaggi: 2739
- Iscrizione: mercoledì 16 gennaio 2013, 17:28
- Desktop: ubuntu-2d
- Distribuzione: Ubuntu 12.04.2 LTS i686
- Località: Airuno(Lecco)
Re: Efficienza algoritmo di ordinamento
Ok, grazie. Ma stando all' esempio, sembrerebbe che qui i km i siano gli stessi e i tempi pure. Quello non mi spiego. Ma ovviamente mi sono perso io.
- vaeVictis
- Imperturbabile Insigne
- Messaggi: 4703
- Iscrizione: venerdì 27 luglio 2012, 17:58
- Desktop: Gnome
- Distribuzione: Ubuntu 20.04 64bit
Re: Efficienza algoritmo di ordinamento
La lamborghini fa 200 km/h
Il primo percorso (la lista lunga) è 200 km. Ci mette un'ora.
Poi dividi il percorso a metà (le due liste del problema iniziale). Fai partire due macchine, ognuna che percorra metà percorso. Ci mettono la metà del tempo.
Ora rifai la stessa cosa con la Panda. Per percorrere entrambe mezzo percorso, due macchine impiegheranno la metà del tempo che impiegherebbe una singola macchina a percorrere il percorso completo.
Mi sembra abbastanza ovvio.
No?
Il primo percorso (la lista lunga) è 200 km. Ci mette un'ora.
Poi dividi il percorso a metà (le due liste del problema iniziale). Fai partire due macchine, ognuna che percorra metà percorso. Ci mettono la metà del tempo.
Ora rifai la stessa cosa con la Panda. Per percorrere entrambe mezzo percorso, due macchine impiegheranno la metà del tempo che impiegherebbe una singola macchina a percorrere il percorso completo.
Mi sembra abbastanza ovvio.
No?
Pirates arrrrrrrrrrr awesome!!!
«I fear not the man who has practiced 10000 kicks once,
but I fear the man who has practiced one kick 10000 times.»
«I fear not the man who has practiced 10000 kicks once,
but I fear the man who has practiced one kick 10000 times.»
- Claudio_F
- Entusiasta Emergente
- Messaggi: 1463
- Iscrizione: lunedì 28 maggio 2012, 18:49
- Desktop: Mate/Gnome
- Distribuzione: Ubu22.04
Re: Efficienza algoritmo di ordinamento
Ok, avevo confuso anch'io merge con fusione. Ripeto quanto detto nei due miei post precedenti.io faccio il merge su 2 array ordinati: sort array1, sort array 2, poi merge.
Altro codice: array1+array2(non ordinati) poi sort globale
Il merge in sé stesso non velocizza nulla. È il fatto di ordinare una lista lunga, oppure due mezze liste che fa la differenza. Differenza tanto più evidente quanto meno performante è l'algoritmo di ordinamento, quindi per notare una certa differenza usare il quick sort è la scelta peggiore.
Se usiamo un algoritmo "pessimo", che impiega un tempo che cresce quadraticamente con il numero di elementi, e diciamo che N2 vale un tempo 1, è semplice vedere che ordinare due mezze liste (e poi mergiarle) richiede la metà del tempo:(½N)2+(½N)2 = 0.5
Questa suddivisione in liste più piccole può continuare, ottenendo tempi sempre migliori. Il merge sort completo arriva a scomporre ogni lista in singole coppie di valori da ordinare, per poi mergiarle.
-
- Imperturbabile Insigne
- Messaggi: 2739
- Iscrizione: mercoledì 16 gennaio 2013, 17:28
- Desktop: ubuntu-2d
- Distribuzione: Ubuntu 12.04.2 LTS i686
- Località: Airuno(Lecco)
Re: Efficienza algoritmo di ordinamento
Ok ragazzi ora ho capito. Mi hanno confuso le prove col quick sort. Evidentenente troppo prestante in C per notare differenze come dice Claudio.
Grazie...e scusatemi ... che zuccone che sono ah ah!!
Grazie...e scusatemi ... che zuccone che sono ah ah!!
-
- Imperturbabile Insigne
- Messaggi: 2739
- Iscrizione: mercoledì 16 gennaio 2013, 17:28
- Desktop: ubuntu-2d
- Distribuzione: Ubuntu 12.04.2 LTS i686
- Località: Airuno(Lecco)
Re: Efficienza algoritmo di ordinamento
Questo potrebbe essere un semplice, stupidissimo algoritmo di ordinamento non efficiente su cui fare prove:
Molto interessante questa cosa del merge, proprio non la conoscevo
Codice: Seleziona tutto
#cerca il massimo e sposta in fondo
# poi riduce il campo di ricerca di max
# man mano che la lista si accorcia
import random #qui non serve
l=[1000,8,45,78,-101,303,10000,55,8,1500,-0.3,0.003,800,0,0,-101]
x=len(l)
i=0
while i<x-1:
r=l.index(max(l[:x-i]))
l[r],l[x-1-i],=l[x-1-i],l[r]
i+=1
print(l)
- Claudio_F
- Entusiasta Emergente
- Messaggi: 1463
- Iscrizione: lunedì 28 maggio 2012, 18:49
- Desktop: Mate/Gnome
- Distribuzione: Ubu22.04
Re: Efficienza algoritmo di ordinamento
Bubble sort base non ottimizzato, (N-1)2 iterazioni:
L'ottimizzazione (che in questo caso NON vogliamo, perché ci serve un algoritmo "pesante"), consisterebbe nel terminare tutta la procedura se nel corso di una intera iterazione del ciclo interno non c'è stato nessuno scambio, oppure se c'è stato un solo scambio.
Codice: Seleziona tutto
for h in range(x-1):
for i in range(x-1):
if l[i] > l[i+1]:
l[i], l[i+1] = l[i+1], l[i]
-
- Imperturbabile Insigne
- Messaggi: 2739
- Iscrizione: mercoledì 16 gennaio 2013, 17:28
- Desktop: ubuntu-2d
- Distribuzione: Ubuntu 12.04.2 LTS i686
- Località: Airuno(Lecco)
Re: Efficienza algoritmo di ordinamento
Me lo salvo il tuo bubble sort. Anche il mio codice sopra non e' ottimizzato (deriva da una vecchia prova in c, un po' migliore pero').
Appena posso faccio prove, m'incuriosisce la cosa
Appena posso faccio prove, m'incuriosisce la cosa
- vaeVictis
- Imperturbabile Insigne
- Messaggi: 4703
- Iscrizione: venerdì 27 luglio 2012, 17:58
- Desktop: Gnome
- Distribuzione: Ubuntu 20.04 64bit
Re: Efficienza algoritmo di ordinamento
Aumenta il numero di elementi nelle liste
Se non ricordo male io feci la prova con una lista da otto milioni di elementi divisa poi in otto (come i processi totali dell'architettura) liste da un milione di elementi.
La differenze si sentiva ed era circa un ottavo.
Il codice in C++ qui
Pirates arrrrrrrrrrr awesome!!!
«I fear not the man who has practiced 10000 kicks once,
but I fear the man who has practiced one kick 10000 times.»
«I fear not the man who has practiced 10000 kicks once,
but I fear the man who has practiced one kick 10000 times.»
-
- Imperturbabile Insigne
- Messaggi: 2739
- Iscrizione: mercoledì 16 gennaio 2013, 17:28
- Desktop: ubuntu-2d
- Distribuzione: Ubuntu 12.04.2 LTS i686
- Località: Airuno(Lecco)
Re: Efficienza algoritmo di ordinamento
Proverò a vedere vae, grazie. L'importante che ora ho capito il concetto del merge
Chi c’è in linea
Visualizzano questa sezione: 0 utenti iscritti e 5 ospiti