Efficienza algoritmo di ordinamento

Linguaggi di programmazione: php, perl, python, C, bash e tutti gli altri.
Avatar utente
Claudio_F
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1450
Iscrizione: lunedì 28 maggio 2012, 18:49
Desktop: Mate/Gnome
Distribuzione: Ubu20.04/22.04

Re: Efficienza algoritmo di ordinamento

Messaggio da Claudio_F »

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.
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2709
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

Messaggio da gila75 »

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
Avatar utente
DoctorStrange
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 2400
Iscrizione: mercoledì 14 ottobre 2015, 9:33
Desktop: Gnome3
Distribuzione: Ubuntu 18.04 Bionic Beaver
Sesso: Maschile
Località: Roma, Italia

Re: Efficienza algoritmo di ordinamento

Messaggio da DoctorStrange »

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.
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2709
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

Messaggio da gila75 »

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.
Ma infatti è quello che ho fatto: uno script che unisce due liste disordinate e poi fa il sort.
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...
Avatar utente
Claudio_F
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1450
Iscrizione: lunedì 28 maggio 2012, 18:49
Desktop: Mate/Gnome
Distribuzione: Ubu20.04/22.04

Re: Efficienza algoritmo di ordinamento

Messaggio da Claudio_F »

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.
Avatar utente
vaeVictis
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 4688
Iscrizione: venerdì 27 luglio 2012, 17:58
Desktop: Gnome
Distribuzione: Ubuntu 20.04 64bit

Re: Efficienza algoritmo di ordinamento

Messaggio da vaeVictis »

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 :)
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.»
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2709
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

Messaggio da gila75 »

...(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.
Bho, mi sa che non hai dato un'occhiata a i codici, io faccio il merge su 2 array ordinati:
sort array1, sort array 2, poi merge.
Altro codice: array1+array2(non ordinati) poi sort globale.

...Scrivi un bubble sort base non ottimizzato...
Se un algoritmo non è ottimizzato o efficiente cade a priori il discorso direi, no?

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.
Avatar utente
vaeVictis
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 4688
Iscrizione: venerdì 27 luglio 2012, 17:58
Desktop: Gnome
Distribuzione: Ubuntu 20.04 64bit

Re: Efficienza algoritmo di ordinamento

Messaggio da vaeVictis »

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.
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.»
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2709
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

Messaggio da gila75 »

vaeVictis ha scritto:
mercoledì 18 maggio 2022, 20:26
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.
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 disparte
Avatar utente
vaeVictis
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 4688
Iscrizione: venerdì 27 luglio 2012, 17:58
Desktop: Gnome
Distribuzione: Ubuntu 20.04 64bit

Re: Efficienza algoritmo di ordinamento

Messaggio da vaeVictis »

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).
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.»
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2709
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

Messaggio da gila75 »

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.
Avatar utente
vaeVictis
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 4688
Iscrizione: venerdì 27 luglio 2012, 17:58
Desktop: Gnome
Distribuzione: Ubuntu 20.04 64bit

Re: Efficienza algoritmo di ordinamento

Messaggio da vaeVictis »

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?
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.»
Avatar utente
Claudio_F
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1450
Iscrizione: lunedì 28 maggio 2012, 18:49
Desktop: Mate/Gnome
Distribuzione: Ubu20.04/22.04

Re: Efficienza algoritmo di ordinamento

Messaggio da Claudio_F »

io faccio il merge su 2 array ordinati: sort array1, sort array 2, poi merge.
Altro codice: array1+array2(non ordinati) poi sort globale
Ok, avevo confuso anch'io merge con fusione. Ripeto quanto detto nei due miei post precedenti.
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.
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2709
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

Messaggio da gila75 »

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!!
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2709
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

Messaggio da gila75 »

Questo potrebbe essere un semplice, stupidissimo algoritmo di ordinamento non efficiente su cui fare prove:

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)
Molto interessante questa cosa del merge, proprio non la conoscevo :)
Avatar utente
Claudio_F
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1450
Iscrizione: lunedì 28 maggio 2012, 18:49
Desktop: Mate/Gnome
Distribuzione: Ubu20.04/22.04

Re: Efficienza algoritmo di ordinamento

Messaggio da Claudio_F »

Bubble sort base non ottimizzato, (N-1)2 iterazioni:

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]
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.
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2709
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

Messaggio da gila75 »

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
Avatar utente
vaeVictis
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 4688
Iscrizione: venerdì 27 luglio 2012, 17:58
Desktop: Gnome
Distribuzione: Ubuntu 20.04 64bit

Re: Efficienza algoritmo di ordinamento

Messaggio da vaeVictis »

Claudio_F ha scritto:
mercoledì 18 maggio 2022, 13:00
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.
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.»
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2709
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

Messaggio da gila75 »

Proverò a vedere vae, grazie. L'importante che ora ho capito il concetto del merge :)
Scrivi risposta

Ritorna a “Programmazione”

Chi c’è in linea

Visualizzano questa sezione: 0 utenti iscritti e 1 ospite