Выделение памяти для больших массивов

[Maria9]

Здравствуйте!

Помогите, пожалуйста, с решением такого вопроса...
Мне нужно выделить память под матрицу целых чисел размера N*N, где N~500 000 000.

Просто объявить int matrix[N][N]; - при больших N не годится.
Также не годится

int **matrix;
matrix=(int **)malloc(sizeof(int)*N);
for (i=0;i<N;i++)
	matrix[i]=(int *)malloc(sizeof(int)*N);

Приводит к ошибке сегментации...
Как же выделять память для таких больших матриц?


2.
Также в моей программе используется массив строк:

char names[N][8];

При N=500 000 000 тоже его нужно объявить как-то по-особенному... Подскажите, пожалуйста, как именно?

3. Затем нужно освободить память (что будет, если не сделать это?). Если я не ошибаюсь, для матрицы N*N обычно это делается так?

for (i=0;i<N;i++)
	free(matrix[i]);
free(matrix);

==========================================================
//Код программы и данные (для тестовых данных N=20, но для реальной задачи  N очень большое)
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <strings.h>
//#include <cstring.h>
int line=18;
int N=20;
int main()
{
	FILE * mydata, * myresult, * myresult2;
	mydata = fopen("go_pfam_test.txt","r+");
	myresult = fopen("matrix_pfam_go.txt","w+");
	myresult2 = fopen("matrix_names.txt","w+");
	char mystring[18]="";	
	char pfam[8]="";
	char cgo[11]="";
	int i,j,l,m,n, I,J;
	char namespfam[N][8];
	///char **namespfam=(char**)malloc(sizeof(char**)*N);
	///for (i=0;i<N;i++)
		///namespfam[i]=(char*)malloc(sizeof(char*)*8);
	/*char **namespfam=new char *[N];
	for (i=0;i<N;i++)
		namespfam[i]=new char[8];
	for (i=0; i<N; i++)
		namespfam[i][8]="";*/
	
	char namesgo[N][11];
	char *p;
	
	int check;
	int first=1;
	int count_pf=1;
	int count_go=1;
	int countgo, countpf;

	/*int **matrix;
	matrix=(int **)malloc(N);
	for (i=0;i<N;i++)
		matrix[i]=(int *)malloc(N);
	*/
	//int matrix[N][N];
	typedef INT *int;
	INT *matrix;
	matrix=(INT *)malloc(N*sizeof(INT));
	for(i=0;i<N;i++)
		matrix=(INT)malloc(N*sizeof(int));
	for (i=0;i<N;i++)
		for (j=0;j<N;j++)
			matrix[i][j]=0;

	
	///////////////////////    Readint File   ////////////////////////////
	while (fgets(mystring,line+1,mydata)) {
	if(strcmp(mystring,"\n")) 
	{
		
		if (first==1)
		{
			memcpy(pfam, mystring, 7*sizeof(char));
			memcpy(cgo, mystring+8, 10*sizeof(char));
			strcpy(namespfam[0],pfam);
			strcpy(namesgo[0],cgo);
			matrix[0][0]++;
			first=0;
		}
		else 
		{	
			memcpy(pfam, mystring, 7*sizeof(char));
			memcpy(cgo, mystring+8, 10*sizeof(char));
			
			
			//если новый pfam, добавляем новую строку
			countpf=count_pf;
			for(i=0;i<countpf;i++)
			{
				if(!strcmp(namespfam[i],pfam)) //if equal strings
					break; //!!!выходим из for, счетчик количества строк не меняется
				else 
				{
					if(i==count_pf-1) //если не экв. ни одной из предш.строк
					{
						strcpy(namespfam[count_pf],pfam);
						count_pf++;						
					}
				}				
			}		
			
		
			countgo=count_go; //т.к. есть count_go++;
			for (j=0;j<countgo;j++)
			{
				//если такой GO уже встречался
				if(!strcmp(namesgo[j],cgo)) //if equal strings
				{	
					//J=j;
					//Если PF, рассматриваемый в этой строке, уже встречался
					for (i=0;i<count_pf;i++)
					{
						if(!strcmp(pfam,namespfam[i])) 
							I=i; //встречался в I-й строке
						
					}
					matrix[I][j]++;					
					break; //выходим из for?
				}
				//если такой GO не встречался, то в последней строке последнем столбце ++1
				else
				{	
					if(j==count_go-1)
					{
						strcpy(namesgo[count_go],cgo);
						matrix[count_pf-1][count_go]++;
						count_go++;
					}
					
				}
			}
		}		
	
	}	
	}
	///////////////////////////////////////////////



	
	printf("\n\ncount_pf=%d",count_pf);
	printf("\n\ncount_go=%d",count_go);
	for(i=0;i<count_pf;i++)
	{
		printf("\n"); 
		for(j=0;j<count_go;j++) 
			printf("%d ",matrix[i][j]);
	}
	

	for(j=0;j<count_pf;j++) 
		fprintf(myresult2,"%s\n",namespfam[j]);


	for(i=0;i<count_pf;i++)
	{
		//fprintf(myresult,"%s\t",namespfam[i]);
		for(j=0;j<count_go;j++) 
			fprintf(myresult,"%d ",matrix[i][j]);
		fprintf(myresult,"\n");
	}
	
	fclose(mydata); fclose(myresult);  fclose(myresult2); 
	for (i=0;i<N;i++)
		free(matrix[i]);
	free(matrix);
	//for (i=0;i<N;i++)
	//	free(namespfam[i]);
	//free(namespfam);
	getch();
	return 0;
}

=================================== =======================
//содержимое файла go_pfam_test.txt
PF04947 GO:0006355
PF04947 GO:0046782
PF04947 GO:0006351
PF03003 GO:0033644
PF03003 GO:0016021
PF00271 GO:0005524
PF00271 GO:0003677
PF00271 GO:0004386
PF00176 GO:0005524
PF00176 GO:0003677
PF00069 GO:0005524
PF00176 GO:0004386
PF08793 GO:0005524
PF08793 GO:0004674
PF00069 GO:0005524
PF00069 GO:0004674
PF05686 GO:0016301
PF07498 GO:0006353
PF03031 GO:0016787
PF00069 GO:0005524
PF00069 GO:0004674
PF00069 GO:0005524

[Пепел Феникса]

1)у вас банально не хватает памяти процесса для этого, там или через файл или переходить на 64 бита надо.
2)на стеке такое не выделять, ток динамически через malloc/new.
3)да так.
если не освобождать, то рано или поздно память кончится.

[Maria9]

1. Извините, я не совсем поняла Вас. На 64-битной машине возникают точно такие же проблемы, если выделять память также, как обычно:
int **matrix;
matrix=(int **)malloc(sizeof(int)*N);
for (i=0;i<N;i++)
matrix[i]=(int *)malloc(sizeof(int)*N);

2. Подскажите, пожалуйста, как именно. Пыталась по-разному - никак не получается...

3. Правильно ли я освобождаю память для 2-мерного массива? В случае, если это - массив строк, освобождение памяти также происходит в два этапа?

Спасибо.

[Rififi]

Пепел Феникса

или переходить на 64 бита надо.

для этого ей нужно будет еще подзакупить 1.8млн. терабайт памяти :D

[f.hump]

подзакупить 1.8млн. терабайт

ха-ха. это при том, что сегодня в x64 можно адресовать максимум 8 терабайт.

по теме, большие матрицы сначала рабиваются на блоки (матрицы, которые влазят в зарезервированный буффер), а потом работа с матрицей поисходит поблочно.

[Shad0wF1rst]

Просто комментарий при ваших запросах выделить двумерный массив по 500 000 000 строк и столбцов у вас получается 25*10^16 байт и то это без учета накладных расходов на систему. По этому правильно сказана было разбивать на блоки и промежуточные результаты хранить например на винчестере, хотя винт понадобится не маленький и не один.

[evg_m]

вероятно идет речь о разреженной матрице. (много-много нулей, и мало ~5 000 000 ненулевых).

учитывая "наличие" массива строк того же размера N, можно предположить что речь идет о какой-то "сложной" обработке данного набора строк, причем в формулировке задачи звучит слово матрица (смежности?) . Будет лучше озвучить исходную задачу, возможно есть алгоритм (или реализация) где никаких матриц (таких размеров) и не потребуется.

[Maria9]

Извините, оказалось, что матрица нужна гораздо меньшего размера. Поэтому переформулирую вопрос - как выделить память для 2-мерного массива, если неизвестно, сколько в нем будет элементов (но будет много)?
Или как, все-таки, выделить память для 2-мерного массива N*N, где N~100 000? Я что-то припоминаю про указатели far, huge...
Хм, возможно, в матрице будет много нулей, но не настолько (по крайней мере, в каждой строчке и каждом столбце как минимум один ненулевой элемент)...

[rrrFer]

. Поэтому переформулирую вопрос - как выделить память для 2-мерного массива, если неизвестно, сколько в нем будет элементов (но будет много)?

никак. Каждый раз когда ты говоришь менеджеру памяти, что тебе нужно выделить память - ты должна указывать сколько памяти тебе надо. Потому что менеджер памяти - не Ванга.

Используй связные списки, тогда память сможешь выделять по мере необходимости.

[Igor95]

Вот-вот, согласен с rrrFer, лучше использовать динамические структуры данных. Выделите или освободите память, когда необходимо, в любой момент времени.