Efficienza algoritmo di ordinamento
- 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
Efficienza algoritmo di ordinamento
Buonasera a tutti,
Vorrei avere un chiarimento ad un dubbio di carattere un po generale.
Io ho due liste di valori. Sono dei semplici interi positivi, ma in ordine casuale, in entrambe le liste. Ciò che vorrei ottenere è una terza lista composta da tutti gli elementi provenienti da entrambe le liste, ordinati con un ordine crescente.
La domanda è: trascurando la complessità del codice o l'impegno di CPU o risorse, se ordinassi le due liste di partenza separatamente, l'ordinamento finale nella terza lista prendendo elementi già ordinati delle due liste di partenza, sarebbe piu efficiente? Oppure è inutile?
Grazie
Vorrei avere un chiarimento ad un dubbio di carattere un po generale.
Io ho due liste di valori. Sono dei semplici interi positivi, ma in ordine casuale, in entrambe le liste. Ciò che vorrei ottenere è una terza lista composta da tutti gli elementi provenienti da entrambe le liste, ordinati con un ordine crescente.
La domanda è: trascurando la complessità del codice o l'impegno di CPU o risorse, se ordinassi le due liste di partenza separatamente, l'ordinamento finale nella terza lista prendendo elementi già ordinati delle due liste di partenza, sarebbe piu efficiente? Oppure è inutile?
Grazie
- corradoventu
- Imperturbabile Insigne
- Messaggi: 3815
- Iscrizione: domenica 27 aprile 2008, 22:23
- Desktop: GNOME
- Distribuzione: Ubuntu 20.04, 22.04, 23.10, 24.04
- Sesso: Maschile
- Località: Rezzoaglio (GE)
- Contatti:
Re: Efficienza algoritmo di ordinamento
La tecnica si chiama sort-merge, è indispensabile se la lista (o somma delle due liste) di partenza è troppo grande per essere contenuta in memoria, altrimenti credo non ci siano vantaggi.
Con o senza religione, i buoni si comportano bene e i cattivi male, ma ci vuole la religione per far comportare male i buoni.
(Steven Weinberg)
(Steven Weinberg)
- 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
Non ho capito la tua risposta. Non ho mai detto quale algoritmo di ordinamento uso. Volevo sapere se l'ordinamento finale è più efficiente se le liste di partenza sono già ordinate. Sarei tentato di pensare di sì, ma non saprei motivarlo.
- Actarus5
- Prode Principiante
- Messaggi: 218
- Iscrizione: mercoledì 3 luglio 2013, 17:15
- Desktop: Mate
- Distribuzione: Fedora
- Località: Abutalabashuneba
Re: Efficienza algoritmo di ordinamento
Ho una domanda, siccome hai parlato di liste tu intendi una linked list? La risposta può essere importante perché in una linked list non puoi accedere al generico elemento in O(1) come con gli array mentre per una lista in generale non è vero
"An extremely helpful console message: “SPANK! SPANK! SPANK! Naughty programmer!”. Really, I’m not joking about that one."
- 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
No "lista" lo intendo come concetto astratto. Una "collection" di elementi. L'implementazione di questa collezione potrebbe essere un array, una list, un Vector, od altro.
- Actarus5
- Prode Principiante
- Messaggi: 218
- Iscrizione: mercoledì 3 luglio 2013, 17:15
- Desktop: Mate
- Distribuzione: Fedora
- Località: Abutalabashuneba
Re: Efficienza algoritmo di ordinamento
Messa così non dovrebbe cambiare niente perché se S è la somma delle dimensioni dei 2 set, assumendo che concatenarli abbia complessità O(S) mentre l'ordinamento O(S*log(S)), alla fine hai O(S*log(S)).
Puoi fare considerazioni analoghe se decidi di ordinarli entrambi, qualcosa del tipo O(m*log(m)) + O(n*log(n)) + O(m + n); qui puoi fare delle considerazioni su m ed n, se "crescono" in maniera simile oppure una cresce molto più velocemente rispetto all'altra, ma giungi sempre al fatto che sono equivalenti.
Ovviamente è solo un'analisi asintotica e nella realtà ci possono essere altre considerazioni da fare, però dal punto di vista della complessità computazionale, a meno di miei errori, non vedo differenze!
Puoi fare considerazioni analoghe se decidi di ordinarli entrambi, qualcosa del tipo O(m*log(m)) + O(n*log(n)) + O(m + n); qui puoi fare delle considerazioni su m ed n, se "crescono" in maniera simile oppure una cresce molto più velocemente rispetto all'altra, ma giungi sempre al fatto che sono equivalenti.
Ovviamente è solo un'analisi asintotica e nella realtà ci possono essere altre considerazioni da fare, però dal punto di vista della complessità computazionale, a meno di miei errori, non vedo differenze!
"An extremely helpful console message: “SPANK! SPANK! SPANK! Naughty programmer!”. Really, I’m not joking about that one."
-
- 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
Io credo che ci sia un peggioramento.
Avresti 2 ordinamenti, una concatenazione poi un altro ordinamento, quando potresti concatenare e ordinare una volta sola.
Comunque con 2 righe che sia python, c o altro si puo' testare. Se ho tempo provo, ma la vedo dura che ci possa essere un miglioramento
Avresti 2 ordinamenti, una concatenazione poi un altro ordinamento, quando potresti concatenare e ordinare una volta sola.
Comunque con 2 righe che sia python, c o altro si puo' testare. Se ho tempo provo, ma la vedo dura che ci possa essere un miglioramento
- corradoventu
- Imperturbabile Insigne
- Messaggi: 3815
- Iscrizione: domenica 27 aprile 2008, 22:23
- Desktop: GNOME
- Distribuzione: Ubuntu 20.04, 22.04, 23.10, 24.04
- Sesso: Maschile
- Località: Rezzoaglio (GE)
- Contatti:
Re: Efficienza algoritmo di ordinamento
NO: Avresti 2 ordinamenti e poi un merge cioè lettura sequenziale dei due insiemi ordinati e inserimento degli elementi nella lista finale.
Con o senza religione, i buoni si comportano bene e i cattivi male, ma ci vuole la religione per far comportare male i buoni.
(Steven Weinberg)
(Steven Weinberg)
- 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
I due ordinamenti delle due liste di partenza, sarebbero effettuati da due nodi worker esterni al master, quindi gli ordinamenti delle liste di partenza non avrebbero alcuna incidenza sulle prestazioni del master, dove mi trovo io. Mi troverei quindi con le due liste di partenza già ordinate esternamente. A questo punto dovrei fare solamente il merge dei dati delle due liste, che corrisponde a prendere sempre l'elemento piu basso delle liste di partenza, e comporre la lista finale. Credo che il miglioramento sia in questo. Il nodo master dovrebbe semplicemente prendere i due elementi piu bassi delle due liste, ed inserirli nella lista finale. Immagino che prendere due elementi da due liste e scegliere il minore tra i due e reiterare il tutto per la lunghezza della lista sia un operazione molto piu efficiente di dover scorrere entrambe le liste alla ricerca di un possibile elemento piu basso.
E' corretto?
E' corretto?
-
- 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
Interessante, non capito benissimo perche' sto lavorando, ma sarebbe da provare.
Scrivi , se vuoi, un esempio in pseudocodice
Scrivi , se vuoi, un esempio in pseudocodice
- Actarus5
- Prode Principiante
- Messaggi: 218
- Iscrizione: mercoledì 3 luglio 2013, 17:15
- Desktop: Mate
- Distribuzione: Fedora
- Località: Abutalabashuneba
Re: Efficienza algoritmo di ordinamento
Ah certo, se sono già ordinate le liste di partenza è diverso, se le dimensioni sono m ed n, hai complessità O(m + n) usando il metodo che dicevi tu, praticamente la funzione Merge dell'algoritmo Mergesort, tra l'altro funziona bene anche con strutture dati diverse dall'array ( ad esempio linked list)DoctorStrange ha scritto: ↑giovedì 12 maggio 2022, 8:44I due ordinamenti delle due liste di partenza, sarebbero effettuati da due nodi worker esterni al master, quindi gli ordinamenti delle liste di partenza non avrebbero alcuna incidenza sulle prestazioni del master, dove mi trovo io. Mi troverei quindi con le due liste di partenza già ordinate esternamente. A questo punto dovrei fare solamente il merge dei dati delle due liste, che corrisponde a prendere sempre l'elemento piu basso delle liste di partenza, e comporre la lista finale. Credo che il miglioramento sia in questo. Il nodo master dovrebbe semplicemente prendere i due elementi piu bassi delle due liste, ed inserirli nella lista finale. Immagino che prendere due elementi da due liste e scegliere il minore tra i due e reiterare il tutto per la lunghezza della lista sia un operazione molto piu efficiente di dover scorrere entrambe le liste alla ricerca di un possibile elemento piu basso.
E' corretto?
"An extremely helpful console message: “SPANK! SPANK! SPANK! Naughty programmer!”. Really, I’m not joking about that one."
- vaeVictis
- Imperturbabile Insigne
- Messaggi: 4703
- Iscrizione: venerdì 27 luglio 2012, 17:58
- Desktop: Gnome
- Distribuzione: Ubuntu 20.04 64bit
Re: Efficienza algoritmo di ordinamento
Se hai due liste già ordinate non devi fare un ordinamento della lista finale, ma fai un merge delle due liste, che risulta più veloce dell'ordinamento di una generica lista disordinata risultato dell'unione di due liste disordinate.
Quindi la risposta è sì. Se ricevi due liste precedentente ordinate e le mergi la complessità temporale sarà minore rispetto alla complessità che avresti unendo le due liste disordinate e ordinando la loro unione
Il merge in genere ha complessità lineare, i sorting dipende ma puoi ipotizzare un NlogN per i sorting con confronto. Poi bisogna vedere in particolare che tipo di ordinamento stai usando, per capire nel dettaglio la complessità. Ma se "parallelizzi" il sorting (perché in sostanza lo hai parallelizzato) hai performance migliori.
Ciò detto, in che linguaggio stai programmando?
Se sei in C++, considera che nella std lib hanno introdotto la policy negli algoritmi. Puoi scegliere la versione da usare e chiedere che venga eseguito parallelamente
Quindi la risposta è sì. Se ricevi due liste precedentente ordinate e le mergi la complessità temporale sarà minore rispetto alla complessità che avresti unendo le due liste disordinate e ordinando la loro unione
Il merge in genere ha complessità lineare, i sorting dipende ma puoi ipotizzare un NlogN per i sorting con confronto. Poi bisogna vedere in particolare che tipo di ordinamento stai usando, per capire nel dettaglio la complessità. Ma se "parallelizzi" il sorting (perché in sostanza lo hai parallelizzato) hai performance migliori.
Ciò detto, in che linguaggio stai programmando?
Se sei in C++, considera che nella std lib hanno introdotto la policy negli algoritmi. Puoi scegliere la versione da usare e chiedere che venga eseguito parallelamente
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
Non conoscevo questa tecnica. Potreste fare un esempio con 2 liste brevi ?
- Claudio_F
- Entusiasta Emergente
- Messaggi: 1463
- Iscrizione: lunedì 28 maggio 2012, 18:49
- Desktop: Mate/Gnome
- Distribuzione: Ubu22.04
Re: Efficienza algoritmo di ordinamento
Qualcosa del genere:
siano A B due vettori sorgenti, e C il vettore risultato
siano i j k gli indici per i vettori A B C
siano lenA e lenB le lunghezze dei due vettori sorgenti (anche zero)
siano A B due vettori sorgenti, e C il vettore risultato
siano i j k gli indici per i vettori A B C
siano lenA e lenB le lunghezze dei due vettori sorgenti (anche zero)
Codice: Seleziona tutto
finché i<lenA or j<lenB:
se i==lenA:
C(k) = B(j)
j++
else se j==lenB:
C(k) = A(i)
i++
else se A(i)<B(j):
C(k) = A(i)
i++
else:
C(k) = B(j)
j++
k++
-
- 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
Grazie Claudio, provo a guardare con calma. A naso ci capisco poco...ah ah. Zuccone io
EDIT:
non so se l'hai pensato tu così Claudio, ma lo trovo di un'eleganza pazzesca questo codice, ora che ho capito come funziona.
Sarebbe interessante fare confronti come diceva l'utente che ha aperto il post.
Io l'ho scritto così, seguendo il tuo pseudo codice. Credo vada bene:
EDIT:
non so se l'hai pensato tu così Claudio, ma lo trovo di un'eleganza pazzesca questo codice, ora che ho capito come funziona.
Sarebbe interessante fare confronti come diceva l'utente che ha aperto il post.
Io l'ho scritto così, seguendo il tuo pseudo codice. Credo vada bene:
Codice: Seleziona tutto
#include <stdio.h>
#define N1 1
#define N2 4
#define N3 N1+N2
int main (void)
{
int array1[N1]={11};
int array2[N2]={-1,15,1555,2000,};
int array3[N3];
int k=0;
int j,z,i;
for (i=0,j=0; i<N1 || j<N2; )
{
if (i==N1)
{
array3[k]=array2[j];
j++;
}
else if (j==N2)
{
array3[k]=array1[i];
i++;
}
else if (array1[i]<array2[j])
{
array3[k]=array1[i];
i++;
}
else
{
array3[k]=array2[j];
j++;
}
k++;
}
for (z=0; z<N3; z++)
printf ("%d ",array3[z]);
puts("");
return 0;
}
- Claudio_F
- Entusiasta Emergente
- Messaggi: 1463
- Iscrizione: lunedì 28 maggio 2012, 18:49
- Desktop: Mate/Gnome
- Distribuzione: Ubu22.04
Re: Efficienza algoritmo di ordinamento
Si va bene, N3 non serve visto che il valore di k alla fine è già la lunghezza del risultato, per cui si poteva stampare con:
L'algoritmo l'ho pensato al momento. Poi sono andato a vedere come è implementato il merge negli esempi in rete e cambia poco. I punti fondamentali sono sempre gli stessi: elaborare finché c'è qualcosa negli array di partenza (cioè finché gli indici i e j non sono arrivati entrambi alla fine dei rispettivi array), e se uno degli array finisce prima, andare avanti copiando il resto dell'altro così come è. In rete trovo il merge realizzato con tre cicli: un while con condizione
i<N1 and j<N2
che elabora finché in entrambi c'è qualcosa, e due for successivi che se è il caso copiano la parte rimanente dell'array più lungo.
Per vedere se funziona l'ho provato in assembly Z80
Codice: Seleziona tutto
for (z=0; z<k; z++)
printf ("%d ",array3[z]);
i<N1 and j<N2
che elabora finché in entrambi c'è qualcosa, e due for successivi che se è il caso copiano la parte rimanente dell'array più lungo.
Per vedere se funziona l'ho provato in assembly Z80
Codice: Seleziona tutto
.org 32768
;---------------------------------------
; Merge di due vettori di byte
; singolarmente ordinati.
; IN: _a = primo vettore
; _b = secondo vettore
; _c = vettore risultato
; _lena = lunghezza primo vettore
; _lenb = lunghezza sec. vettore
; OUT: _k = lunghezza risultato
;---------------------------------------
merge LD A,0 ; azzeramento indici iniziale
LD (_i),A
LD (_j),A
LD (_k),A
;------ while _i < _lena or _j < _lenb
l000 LD A,(_lena)
LD E,A
LD A,(_i)
CP E
JP C,l100
LD A,(_lenb)
LD E,A
LD A,(_j)
CP E
RET NC ; fine merge, ritorna al chiamante
;------ if _i == _lena
l100 LD A,(_i)
LD E,A
LD A,(_lena)
CP E
JP NZ,l200
CALL btoc
JP l000
;------ else if _j == _lenb
l200 LD A,(_j)
LD E,A
LD A,(_lenb)
CP E
JP NZ,l300
CALL atoc
JP l000
;------ else if _a(_i) < _b(_j)
l300 LD A,(_j)
LD HL,_b
CALL rdvect
LD C,B
LD A,(_i)
LD HL,_a
CALL rdvect
LD A,B
CP C
PUSH AF
CALL C,atoc
POP AF
;------ else
CALL NC,btoc
JP l000
;---------------------------------------
; Legge _a(_i) in reg B
; Incrementa _i
;---------------------------------------
atoc LD A,(_i)
LD C,A
LD HL,_a
CALL rdvect
LD A,C
INC A
LD (_i),A
JP l400
;---------------------------------------
; Legge _b(_j) in reg B
; Incrementa _j
;---------------------------------------
btoc LD A,(_j)
LD C,A
LD HL,_b
CALL rdvect
LD A,C
INC A
LD (_j),A
;---------------------------------------
; Parte comune per atoc e btoc
; Scrive reg B in _c(_k)
; Incrementa _k
;---------------------------------------
l400 LD A,(_k)
LD E,A
LD D,0
LD HL,_c
ADD HL,DE
LD (HL),B
LD A,E
INC A
LD (_k),A
RET
;---------------------------------------
; Lettura da vettore di byte
; IN: A = indice 0..255
; HL = addr vettore
; OUT: B = valore
;---------------------------------------
rdvect LD E,A
LD D,0
ADD HL,DE
LD B,(HL)
RET
Codice: Seleziona tutto
;---------------------------------------
; Area dati globali
;---------------------------------------
.org 33000
_a .byte 0, 1, 2, 4, 6, 8, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0
_b .byte 1, 3, 5, 6, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
_c .byte 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
_lena .byte 7
_lenb .byte 5
_i .byte 0
_j .byte 0
_k .byte 0
-
- 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
Incredibile. Pensato cosi', al momento. Non dico altro.
In python non sarei capace, visto che i cicli for si comportano un po' diversamente.
In python non sarei capace, visto che i cicli for si comportano un po' diversamente.
- Claudio_F
- Entusiasta Emergente
- Messaggi: 1463
- Iscrizione: lunedì 28 maggio 2012, 18:49
- Desktop: Mate/Gnome
- Distribuzione: Ubu22.04
Re: Efficienza algoritmo di ordinamento
Non serve il for, finché si traduce con while:
Codice: Seleziona tutto
a = [0, 1, 2, 4, 6, 8, 9]
b = [1, 3, 5, 6, 7]
i = 0
j = 0
c = []
while i<len(a) or j<len(b):
if i == len(a):
c.append(b[j])
j += 1
elif j == len(b):
c.append(a[i])
i += 1
elif a[i] < b[j]:
c.append(a[i])
i += 1
else:
c.append(b[j])
j += 1
print(c)
-
- 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
si si Claudio, con while si risolve. Dicevo solo che il for in python si comporta in modo un po' differente dal c.
Ne avevamo già parlato, ma pian piano ci arrivo sto andando avanti (un po' a rilento ) col manuale.
Comunque non ho notato grandi differenze:
versione ordinamento+merge su 100k cicli e 2 array da 1000 elementi:
output:
versione fusione+ordinamento:
output:
pensavo ci fosse una sostanziale differenza. Sempre non abbia frainteso qualcosa
Ne avevamo già parlato, ma pian piano ci arrivo sto andando avanti (un po' a rilento ) col manuale.
Comunque non ho notato grandi differenze:
versione ordinamento+merge su 100k cicli e 2 array da 1000 elementi:
Codice: Seleziona tutto
//****************************************************
// genera 2 array random, li ordina poi fa il merge
//****************************************************
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N1 1000
#define N2 1000
#define N3 N2+N1
#define CICLI 100000
int cmp (const void * a, const void * b);
void init_array(int array[],int n);
void merge(int array1[],int array2[],int array3[],int n1,int n2);
void init_array(int array[],int n)
{
int rnd,i;
int k=0;
for (i=0; i<n; i++)
{
rnd=rand()%1000;
array[k]=rnd;
k++;
}
}
void merge(int array1[],int array2[],int array3[],int n1,int n2)
{
int k=0;
int j,i;
for (i=0,j=0; i<N1 || j<N2; )
{
if (i==N1)
{
array3[k]=array2[j];
j++;
}
else if (j==N2)
{
array3[k]=array1[i];
i++;
}
else if (array1[i]<array2[j])
{
array3[k]=array1[i];
i++;
}
else
{
array3[k]=array2[j];
j++;
}
k++;
}
}
int cmp (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
int main (void)
{
int v1[N1];
int v2[N2];
int v3[N3];
int x;
srand((unsigned) time(NULL));
for (x=0; x<CICLI; x++)
{
init_array(v1,N1);
init_array(v2,N2);
qsort(v1, N1, sizeof(int),cmp);
qsort(v2, N2, sizeof(int),cmp);
merge (v1,v2,v3,N1,N2);
//for (i=0; i<N3; i++)
//printf ("%d ", v3[i]);
//puts("xxxxxxxxxxxxxxxxxx");
}
return 0;
}
Codice: Seleziona tutto
gila@gila-pc:~/Scrivania$ time ./xx
real 0m24.906s
user 0m24.887s
sys 0m0.013s
gila@gila-pc:~/Scrivania$
Codice: Seleziona tutto
//****************************************************
// genera 2 array random, li fonde e ordina
//*****************************************************
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N1 1000
#define N2 1000
#define N3 N2+N1
#define CICLI 100000
int cmp (const void * a, const void * b);
void init_array(int array[],int n);
void fusione (int array1[],int array2[],int array3[],int n1,int n2);
void init_array(int array[],int n)
{
int rnd,i;
int k=0;
for (i=0; i<n; i++)
{
rnd=rand()%1000;
array[k]=rnd;
k++;
}
}
void fusione (int array1[],int array2[],int array3[],int n1,int n2)
{
int i;
int k=0;
for (i=0; i<n1; i++)
{
array3[k]=array1[i];
k++;
}
for (i=0; i<n2; i++)
{
array3[k]=array2[i];
k++;
}
}
int cmp (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
int main (void)
{
int v1[N1];
int v2[N2];
int v3[N3];
int x;
srand((unsigned) time(NULL));
for (x=0; x<CICLI; x++)
{
init_array(v1,N1);
init_array(v2,N2);
fusione(v1,v2,v3,N1,N2);
qsort(v3, N3, sizeof(int),cmp);
//for (i=0; i<N3; i++)
//printf ("%d ", v3[i]);
//puts("xxxxxxxxxxxxxxxxxx");
}
return 0;
}
Codice: Seleziona tutto
gila@gila-pc:~/Scrivania$ time ./xx
real 0m24.077s
user 0m24.066s
sys 0m0.005s
gila@gila-pc:~/Scrivania$
-
- 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
Qualcuno mi sa spiegare? Mi pareva di capire che con il merge ci sarebbe stato un netto miglioramente. Dalle prove sembrerebbe di no.
Io ho scritto le routines in C sarei curioso di vedere in python, ma credo cambi poco.
Non so, aspetto vostri pareri che ne sapete piu' di me
Io ho scritto le routines in C sarei curioso di vedere in python, ma credo cambi poco.
Non so, aspetto vostri pareri che ne sapete piu' di me
Chi c’è in linea
Visualizzano questa sezione: 0 utenti iscritti e 8 ospiti