Newsgroup: it.comp.lang.c
Titolo: Memoria e "buona programmazione"

Buona sera a tutto il NG.
Volevo chiedervi dei consigli... Ho la necessità di dover ordinare file 
di grosse dimensioni, contenenti coppie di numeri separati da una 
virgola per esempio un file costituito dalle coppie
5,6
7,9
2,1
7,3
deve essere scritto in un nuovo file nel seguente ordine
2,1
5,6
7,3
7,9
la prima versione che ho scritto è quella che riporterò nelle righe 
sottostanti...
printf("%s: Sto caricando il file in memoria...\n",name);	
file = fopen(argv[1], "r");
file = fopen("/scratch/locale/listadisordinata.txt", "r");
if (file == NULL) {
	printf("%s: Impossibile aprire il file: 
%s\n",name,"/scratch/locale/listadisordinata.txt");
	return(0);
}
while(fgets(buffer,BUFSIZ,file)!=NULL) {
	if(i!=0 && i%128000==0) {
	linee=(linea*) realloc(linee,(i+128000)*sizeof(linea));
	if(linee == NULL) {
		printf("%s: Memoria insufficiente !\n",name);return(0);}
	}
	pch = strtok (buffer,",");
	linee[i].str1=atoi(pch);
	pch = strtok (NULL, " \n");
	if (pch!=NULL)
	linee[i].str2=atoi(pch);						
	i++;
}
 
printf("Il file %s e\' stato caricato.\n", argv[1]);		
printf("%s: Il file %s e\' stato caricato.\n", 
name,"/scratch/locale/listadisordinata.txt");
In pratica apro il file e poi ogni mega circa (il tipo linea è una 
struct da 8 byte===>128000*8byte=1Mb) di ram ne alloco un nuovo mega fin 
tanto che il file non è terminato.
Successivamente applico una QuickSort sul primo intero della coppia ed 
un successivo QuickSort sul secondo intero...
primo problema:
[Sarebbe molto meglio poter fare un unico quicksort ma non ho trovato 
nessuna relazione fra i due interi di ogni coppia che mi porti a 
genereare una chiave univoca ed ordinabile, per esempio il semplice 
rapporto fra numeri non è sufficente perchè per esempio la coppia 5,6 
chiave 30 divverebbe uguale alla coppia 6,5 oppure alla 10,3 e tante ancora]
secondo problema:
uso della memoria troppo esoso vengono caricati tutti i dati in ram, 
l'elaborazione è rapidissima ovviamente ma lo sprego di memoria è troppo 
eccessivo, dall'altra parte ordinare il file su disco comporterebbe un 
numero di letture/scritture non contigue che porterebbe a far lavorare 
il disco nel modo meno performante possibile ma con continui salti di 
testina da un punto ad un altro.
domanda ?
Qualcuno conosce qualche algoritmo efficente che mi permetta di caricare 
in memoria porzioni di file alla volta ?? tipo che ne so i primi 50 mega 
e poi i secondi 50 mega e via dicendo per poi restituire un merge finale ??
grazie a tutti coloro che risponderanno, scusata per la lunghezza del post
Diego

Diego ha scritto:

intanto il sort devi applicarlo ad entrambi i valori
contemporaneamente.
Verifichi prima il primo valore e se sono uguali verifichi il secondo.
Poi puoi leggere un blocco di dati, li ordini e crei un file
temporaneo, uno per ciascun blocco fino a terminare il file sorgente.
Carichi in tanti array, quanti sono i blocchi, una porzione dei file
temporanei (o tutto il file se le dimensioni lo permettono).
Prendendo le teste degli array crei una struttura ad heap (albero
binario semi-ordinato) da cui estrai ogni volta la testa e la scrivi
sul file definitivo.
Quindi ad ogni estrazione fai salire (o sposti un eventuale indice)
dall'array corrispondente (al dato che risale nell'heap) i dati fino ad
esaurire l'array.
Se il file temporaneo a cui è abbinato l'array non è terminato
ricarichi il blocco.
Non è semplice da implementare ma è abbastanza efficiente.
Ciao

una cosa che riguarda l'ordinamento:
se i numeri possono essere al massimo di una cifra e la formattazione
delle linee è sempre la stessa, nel senso che virgola e spazi sono
sempre le stesse ti può bastare ordinare le linee in ordine
alfabetico...