[C] 5000 elementi sono troppi per ordinare col mergesort?

[australopiteci]

Salve a tutti, mi si blocca questo programma quando lo mando in esecuzione.. un mio amico mi ha detto che dipende dalle dimensioni delle liste perchè con liste di 5000 elementi come in questo caso occupano troppo spazio per gli algoritmi ricorsivi....
Si blocca il mergesort, gli altri vanno bene.. a me mi pare veramente strano voi che ne pensate??

[code]
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#ifdef _WIN32
#include <windows.h>
#define MAX_CIFRE 4 // numeri compresi tra 0 e 999
#define RADICE_SIZE 10
#define IS_FULL(ptr) (!ptr)
#define IS_EMPY(ptr) (!ptr)
#define MAX 5000
#define ITERAZIONI 7
#define DIMENSIONE_MAX_LISTA 5000


static LARGE_INTEGER _tstart, _tend;
static LARGE_INTEGER freq;

void tstart(void)
{
static int first = 1;
if(first){
QueryPerformanceFrequency(&freq);
first = 0;
}
QueryPerformanceCounter(&_tstart);
}

void tend(void)
{
QueryPerformanceCounter(&_tend);
}

double tval()
{
return ((double)_tend.QuadPart - (double)_tstart.QuadPart)/((double)freq.QuadPart);
}
#else
#include <sys/time.h>

static struct timeval _tstart, _tend;
static struct timezone tz;

void tstart(void)
{
gettimeofday(&_tstart, &tz);
}

void tend(void)
{
gettimeofday(&_tend,&tz);
}

double tval()
{
typedef signed long s;
s t1, t2;
t1 = (s)_tstart.tv_sec + (s)_tstart.tv_usec/(1000*1000);
t2 = (s)_tend.tv_sec + (s)_tend.tv_usec/(1000*1000);
return t2-t1;
}
#endif


typedef struct list_node *list_pointer;
typedef struct list_node {
int chiave[MAX_CIFRE];
list_pointer link;
}lista;

int dimensioni[]= {50,100,200,500,1000,2000,5000};

void creazione_dati (int testa[][ITERAZIONI][DIMENSIONE_MAX_LISTA]);

void scambia(int *x,int *y);

void sort_inserzione(int lista[][ITERAZIONI][DIMENSIONE_MAX_LISTA],int m,int n);

void sort_selezione (int lista[][ITERAZIONI][DIMENSIONE_MAX_LISTA],int m,int n);

void quicksort(int A[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int u, int v,int z,int r);
int perno(int A[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int primo, int ultimo, int z, int r);

void mergesort(int lista[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int n, int z, int r);
void passo_merge(int lista[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int ordinata[][ITERAZIONI][DIMENSIONE_MAX_LISTA], int n, int lungh,int z, int r);
void merge(int lista[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int ordinata[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int i, int m, int n, int z, int r);

void heapsort(int lista[ ], int n);
void adatta(int lista[ ], int radice, int n);

list_pointer radice_sort(list_pointer ptr);

void visualizza(list_pointer ptr);

main(){
randomize();
printf("\nEsercitazione numero 23\n");
int i,j,k,h;

int testa[4][7][DIMENSIONE_MAX_LISTA];
int tempo[4][7][6];
int confronti[4][7][6];
int scambi[4][7][6];

for(i=0;i<4;i++)
for(j=0;j<7;j++)
for(k=0;k<6;k++)
confronti[i][j][k] = 0;

for(i=0;i<4;i++)
for(j=0;j<7;j++)
for(k=0;k<6;k++)
scambi[i][j][k] = 0;



//****************************************************************************
//****************************************************************************
//*************************ORDINAMENTO PER SELEZIONE**************************
//****************************************************************************
//****************************************************************************

//creazione dei dati di input
creazione_dati (testa);

for(i=0;i<4;i++)
for(j=0;j<7;j++)
{
tstart();
sort_selezione(testa,i,j);
tend();
tempo[i][j][0]=tval();
}



//****************************************************************************
//****************************************************************************
//*************************ORDINAMENTO PER INSERZIONE*************************
//****************************************************************************
//****************************************************************************

//creazione dei dati di input
creazione_dati (testa);


for(i=0;i<4;i++)
for(j=0;j<7;j++)
{
tstart();
sort_inserzione(testa,i,j);
tend();
tempo[i][j][1]=tval();
}


//****************************************************************************
//****************************************************************************
//***********************ORDINAMENTO VELOCE (QuickSort)***********************
//****************************************************************************
//****************************************************************************

//creazione dei dati di input
creazione_dati (testa);

for(i=0;i<4;i++)
for(j=0;j<7;j++)
{
h = dimensioni[j] - 1;
tstart();
quicksort(testa,0,h,i,j);
tend();
tempo[i][j][2]=tval();
}
printf("\n");
for(i=0;i<50;i++)printf(" %d ",testa[3][0][i]);


//****************************************************************************
//****************************************************************************
//*********************ORDINAMENTO PER FUSIONE (MergeSort)********************
//****************************************************************************
//****************************************************************************

//creazione dei dati di input
creazione_dati (testa);

for(i=0;i<4;i++)
for(j=0;j<7;j++)
{
h = dimensioni[j];
tstart();
mergesort(testa,h,i,j);
tend();
tempo[i][j][2]=tval();
}
printf("\n");
for(i=0;i<50;i++)printf(" %d ",testa[3][0][i]);

getchar();
fflush(stdin);
}

void sort_inserzione(int lista[][ITERAZIONI][DIMENSIONE_MAX_LISTA],int m,int n)
{
int i,j,h;
int prossimo;
h = dimensioni[n];
for(i=1;i<h;i++)
{
prossimo=lista[m][n][i];
for(j=i-1;j>=0 && prossimo<lista[m][n][j];j--)
lista[m][n][j+1] = lista[m][n][j];

lista[m][n][j+1] = prossimo;
}

}


void sort_selezione (int lista[][ITERAZIONI][DIMENSIONE_MAX_LISTA],int m,int n)
{
int i,j,h,min;
h = dimensioni[n];
for(i=0;i<h-1;i++)
{
min =i;
for(j=i+1;j<h;j++)
if(lista[m][n][j]<lista[m][n][min])min=j;
scambia(&lista[m][n][i],&lista[m][n][min]);
}
}



void quicksort(int A[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int u, int v,int z,int r)
{
int q;
if(u == v) return;
q = perno(A, u, v, z, r);
if( u < q ) quicksort(A, u, q-1, z, r);
if( q < v ) quicksort(A, q+1, v, z, r);
}

int perno(int A[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int primo, int ultimo, int z, int r)
{
int i = primo;
int j =ultimo+1;
int pivot=A[z][r][primo];

do{
do i++; while(A[z][r][i]<pivot && i<j);
do j--; while(A[z][r][j]>pivot && j>primo);
if(i<j) scambia(&A[z][r][i],&A[z][r][j]);
}while(i<j);

scambia(&A[z][r][primo], &A[z][r][j]) ;

return j;

}

void merge(int lista[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int ordinata[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int i, int m, int n, int z, int r)
{
/* fonde due file ordinati: lista[i],...,lista[m]
e lista[m+1],...,lista[n], per ottenere una sola lista ordinata
ordinata[i],...,ordinata[n]
*/ printf(" 1 ");
int j, k, t;
j = m+1;
// indice per la seconda lista
k = i;
printf(" 2 ");
// indice per la lista ordinata
while(i<=m && j<=n)
{ printf(" 3 ");
if(lista[z][r][i]<=lista[z][r][j]) ordinata[z][r][k++] = lista[z][r][i++];
else
ordinata[z][r][k++] = lista[z][r][j++];
}
printf(" 4 ");
if(i>m) for(t=j; t<=n; t++) ordinata[z][r][k+t-j] = lista[z][r][t];
// ordinata[k],...,ordinata[n] = lista[j],...,lista[n]
else for(t=i; t<=m; t++) ordinata[z][r][k+t-i] = lista[z][r][t];
// ordinata[k],...,ordinata[n] = lista[i],...,lista[m]
printf(" 5 ");
}

void passo_merge(int lista[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int ordinata[][ITERAZIONI][DIMENSIONE_MAX_LISTA], int n, int lungh,int z, int r)
{
/*
Svolge un passo dell'ordinamento per fusione.
Fonde una coppia di sottofile adiacenti da lista a ordinata;
n è il numero di elementi nella lista;
lungh è la lunghezza del sottofile */
int i, j;
printf(" A ");
for(i = 0; i <= n-2*lungh; i += 2*lungh)
merge(lista, ordinata, i, i+lungh-1, i+2*lungh-1, z, r);
printf(" B ");
if(i+lungh < n)
merge(lista, ordinata, i, i+lungh-1, n-1, z, r);
else for(j = i; j < n; j++)
ordinata[z][r][j] = lista[z][r][j];
printf(" C ");
}

void mergesort(int lista[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int n, int z, int r)
{
printf(" a ");
/* ordina la lista lista[0],...,lista[n-1] per fusione */
int lungh = 1;
printf(" b ");
// lunghezza corrente delle liste da fondere
printf(" c ");
int extra[MAX][ITERAZIONI][DIMENSIONE_MAX_LISTA];
printf(" d ");
while(lungh < n)
{
printf(" e ");
passo_merge(lista, extra, n, lungh, z, r);
printf(" f ");
lungh *= 2;
printf(" g ");

passo_merge(extra, lista, n, lungh, z, r);
printf(" h ");
lungh *= 2;
printf(" a ");
}
}

void heapsort(int lista[ ], int n)
{

int i;
for(i = n/2; i > 0; i--)
adatta(lista, i, n);
for(i = n-1; i > 0; i--) {
scambia(&lista[1], &lista[i+1]); //Scambia lista[1] con lista[i]
adatta(lista, 1, i);
}
}


void adatta(int lista[ ], int radice, int n)
// adatta l'albero binario per ottenere l'heap
{
int figlio, chiaveradice;
int temp;
temp = lista[radice];
chiaveradice = lista[radice];
figlio = 2*radice;
// figlio a sinistra
while(figlio <= n) {
if((figlio < n) && (lista[figlio]<lista[figlio+1]))
figlio ++;
if(chiaveradice > lista[figlio])
// confronta la radice e figlio max
break;
else {
lista[figlio/2] = lista[figlio];
// si sposta verso il padre
figlio *= 2;
}
}
lista[figlio/2] = temp;
}

list_pointer radice_sort(list_pointer ptr)
{
list_pointer davanti[RADICE_SIZE], dietro[RADICE_SIZE];
int i, j, cifra;
for(i = MAX_CIFRE-1; i >=0; i--) {
for(j = 0; j < RADICE_SIZE; j++)
davanti[j] = dietro[j] = NULL;
while(ptr) {
cifra = ptr->chiave[i];
if (!davanti[cifra])
davanti[cifra] = ptr;
else
dietro[cifra]->link = ptr;
dietro[cifra] = ptr;
ptr = ptr->link;
}
// ristabilisce la lista concatenata per il passo succ
ptr = NULL;
for (j = RADICE_SIZE-1; j>=0; j--)
if(davanti[j]) {
dietro[j]->link = ptr;
ptr = davanti[j];
}
}
return ptr;
}

void scambia(int *x,int *y)
{
int temp= *x;
*x = *y;
*y = temp;
}

void visualizza (list_pointer ptr)
{
int x;
if(IS_EMPY(ptr)){printf("\nla lista e' vuota"); return;}
printf("\nI record presenti nella lista sono:");
for(;ptr;ptr=ptr->link) {
for(x=0;x<MAX_CIFRE;x++)
printf("%d",ptr->chiave[x]);
printf(" ");
}
}


void creazione_dati (int testa[][ITERAZIONI][DIMENSIONE_MAX_LISTA])
{
int i,j;

//liste ordinate
for(i=0;i<ITERAZIONI;i++)
for(j=0;j<dimensioni[i];j++) testa[0][i][j]=j;

//liste inversamente ordinate
for(i=0;i<ITERAZIONI;i++)
for(j=dimensioni[i];j>0;j--) testa[1][i][dimensioni[i]-j]=j;

//liste con numeri casuali
for(i=0;i<ITERAZIONI;i++)
for(j=0;j<dimensioni[i];j++) testa[3][i][j]=rand();

//liste quasi ordinate (il 10% non e ordinato)
for(i=0;i<ITERAZIONI;i++)
for(j=0;j<(dimensioni[i]/10);j++) testa[2][i][j]=j + dimensioni[ITERAZIONI - 1] ;

for(i=0;i<ITERAZIONI;i++)
for(j=(dimensioni[i]/10);j<dimensioni[i];j++) testa[2][i][j]=j;

}

[code]

[anx721]

Lo ritengo estremamente improbabile...in genere se c'è un problema di chiamate ricorsive il programma termina con un messaggio d'errore. Su una lista di 5000 elementi il numero di chiamate ricorsive contemporaneamente presenti nello stack non supera mai log(5000) <= 13, quindi se c'è un blocco molto probabilmente hai inmplementato male il codice; se introduci delle istruzioni di stampa puoi individuare dov'è che la funzione resta bloccata, magari richiamandosi continuamente

[australopiteci]

Ciao anx721,
la lista ha 5000 * 7 * 4 elementi, 7 sono le dimensioni delle liste, 4 i tipi di input.
Ho usato le printf, la funzione si blocca quando chiama il mergesort.
Quel mio amico mi ha detto che nel prologo della funzione succede questo:

void mergesort(int lista[ ][ITERAZIONI][DIMENSIONE_MAX_LISTA], int n, int z, int r)
{
00412E10 push ebp
00412E11 mov ebp,esp
00412E13 mov eax,88C54h
00412E18 call @ILT+295(__chkstk) (41112Ch)

dentro la __chkstk
che è una funzione della crt di vs che controlla lo stack della funziona chiamata in eax si aspetta la dimensione dello stack da controllare 88C54h = 560212 K (560K).

Poi ha aumentato la dimensione dello stack a 170000 da linea di comando e così ha funzionato.. io ho provato col mio borland c++ ad aumentarla a 300000 ma non fa lo stesso.

L'algoritmo è giusto, il fatto è che non viene implementato neanche una volta. E' come se quando gli passi la lista si spaventasse della dimensione della lista e poi andasse in crash

[australopiteci]

il problema è proprio quello, ho diminuto la dimensione delle liste e ora fa.. ma non capisco perchè il pc non riesce a ordinare un array cosi grande...

[anx721]

probabilmente sbagli a implementare l'algoritmo...ma non l'ho proprio guardato..se lo riscrivi indentato e commentato magari ci do uno sguardo

[australopiteci]

non è l'algoritmo, ho appena provato a dichiarare una nuova lista dalle stesse dimensioni è il programma si blocca subito...
E' proprio questione di memoria.... lascia perdere il codice...

[Fenomeno85]

quando si hanno liste grandi usare metodi ricorsivi è sbagliato.

~§~ Sempre E Solo Lei ~§~

[australopiteci]

"quando si hanno liste grandi usare metodi ricorsivi è sbagliato."

...vai e dillo alla prof...

[Fenomeno85]

Originariamente inviato da australopiteci
"quando si hanno liste grandi usare metodi ricorsivi è sbagliato."

...vai e dillo alla prof...

va be ma loro te lo fanno per imparare la ricorsione non ti metteranno mai una lista da 5000 elementi da ordinare in modo ricorsivo se no le dici scusi mi regala un pò di stack??

~§~ Sempre E Solo Lei ~§~

[australopiteci]

lol

Non è per imparare la ricorsione.... è l'esercitazione finale, la più difficile... questo programma beve più di una macchina di formula 1 ...

[Fenomeno85]

stavo spulciando un pò il codice ... lasciando perdere l'indentazione ... non usi molto le funzioni standard ... ho visto un randomize che è solo per borland ... è un bel casino metti [/code] nell'ultimo che hai messo al posto di [code]

~§~ Sempre E Solo Lei ~§~

[australopiteci]

Si ho il borland, il fatto è che x ora conosco solo randomize ()
che fa quel lavoro.... si il codice è un pò messo male (un pò molto..)
x [code] si.. ho visto

[anx721]

Originariamente inviato da Fenomeno85
quando si hanno liste grandi usare metodi ricorsivi è sbagliato.

~§~ Sempre E Solo Lei ~§~

Il problema non è dato dalla ricorsione, ma dall'allocazione statica di un array troppo grosso da essere inserito nello stack; anche se la lista è di 5000 elementi, col mergesort non si accumulano mai piu di log(5000)= 13 chiamate ricorsive nello stack

[australopiteci]

Ciao Anx...
Anch io alla fine stavo pensando a quello perchè praticamente il programma neanche viene eseguito.

E questa funzione:
void creazione_dati (int testa[][ITERAZIONI][DIMENSIONE_MAX_LISTA])
io sto passando testa per copia vero?
Magari se riuscissi a passarla proprio per indirizzo questo problema verrebbe eliminato ma non so proprio come fare perchè ho sempre saputo che è neccessario sempre scrivere la dimensione per array multidimensionali altrimenti il compilatore non riesce ad allocare la memoria

[anx721]

gli array non sono passati per copia tranquillo...un array infatti è un puntatore (costante); un asoluzione puo essere quella di allocare dinamicamente la matrice.

[australopiteci]

Ok
Dinamicamente intendi con delle malloc? ora provo a cercare qualche esempio in rete.. comunque sto avendo paura che non faccia neanche in perchè ho dato un occhiata nel compilatore e ho visto che la dimensione dell'heap, che se non sbaglio dovrebbe essere la memoria che si può allocare con malloc ecc. è uguale a quella dello stack. Entrambe sono fissate a quota 100000