如何增加程序的输入大小

This program takes two input . first Array size(n) and choice ex:- if n is 100 than my program generate 100 random numbers and sort them using merge sort and quick sort.

该程序需要两个输入。第一个数组大小(n)和选择例如: - 如果n为100,则我的程序生成100个随机数,并使用合并排序和快速排序对它们进行排序。

Now if you enter choice==2 than it display time taken by both sorting algorithm

现在,如果输入choice == 2,则显示两个排序算法所花费的时间

My program works upto input size 10^8 but I want it to work upto 10"10 .If i enter input size 10^9 it gives segmentation fault . there is problem in allocation that much amount of memory .malloc returns null if input size exceeds 10^9

我的程序工作到输入大小10 ^ 8,但我希望它工作到10“10。如果我输入输入大小10 ^ 9它给出了分段错误。分配有问题,大量内存.malloc如果输入大小返回null超过10 ^ 9

Can anyone please tell me how can I improve my program's input size...........

任何人都可以告诉我如何改善我的程序的输入大小...........

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

long long merge(int *A,long long i,long long mid,long long j)                   

{   

int *C;
C=(int *)malloc(sizeof(int)*(j-i+1));                           
long long  r,start,k;
r=0;
start=i;
k=mid+1;
while((i<=mid)&&(k<=j))
{
    if(A[i]>A[k])
    {
        C[r]=A[k];
        r++;k++;
    }
    else
    {
        C[r]=A[i];
        r++;i++;
    }
}
while(i<=mid)
{
    C[r]=A[i];
    r++;i++;
}
while(k<=j)
{
    C[r]=A[k];
    r++;k++;
}
for(i=0;i<r;i++,start++)
    A[start]=C[i];
free(C);
  }
   long long partition(int *A,long long i,long long j)                           
   {

long long mid;
mid=(i+j)/2;                                    
if(i<j)
{
    partition(A,i,mid);                         
    partition(A,mid+1,j);
    merge(A,i,mid,j);                       
}
    }

    long long find_position(int A[],long long i,long long j)                        

    {

long long pivot,temp,end;
end=j;
pivot=i;
while(i<j)
{
    while(A[i]<=A[pivot]&&i<end)
        i++;
    while(A[j]>A[pivot])
        j--;
    if(i<j)
    {
        temp=A[i];
        A[i]=A[j];
        A[j]=temp;
    }
}
temp=A[pivot];
A[pivot]=A[j];
A[j]=temp;
return j;
  } 
  long long quicksort(int A[],long long  i,long long  j)                                
  {
long long position;
if(j>i)
{
    position = find_position(A,i,j);
    quicksort(A,i,position-1);
    quicksort(A,position+1,j);
  }
    }
   int main()
  {
clock_t start,end,quick_sort,merge_sort;
long long input_size,i;
int choice,x;
srand(time(NULL));
printf("Enter input Size\n");
scanf("%lld",&input_size);
int *A,*B;
printf("input your choice\n");
scanf("%d",&choice);
A=(int *)malloc(input_size*sizeof(int));
B=(int *)malloc(input_size*sizeof(int));
if(A==NULL||B==NULL)
{
    printf("sorry that much memory can't be allocated\n");
    return 0;
}
for(i=0;i<input_size;i++)
{
    x=rand();
    A[i]=x;
    B[i]=x;
}
if(choice==1)
{
    printf("Array entered by user\n");
    for(i=0;i<input_size;i++)
        printf("%d  ",A[i]);
}
start=clock();
partition(A,0,input_size-1);
end=clock();
merge_sort=end-start;
if(choice==2)
    printf("\n time taked by merge sort is %6.6f",((double)(merge_sort)/CLOCKS_PER_SEC));
if(choice==1)
{
    printf("\nmerge sorted array\n");
    for(i=0;i<input_size;i++)
        printf("%d  ",A[i]);
}
start=clock();
quicksort(B,0,input_size-1);
end=clock();
quick_sort=end-start;
if(choice==2)
    printf("\n time taked by quick sort is %6.6f",((double)(quick_sort)/CLOCKS_PER_SEC));
if(choice==1)
{
    printf("\nquick sorted array\n");
    for(i=0;i<input_size;i++)
        printf("%d  ",B[i]);
}
printf("\n");
return 0;

}

2 个解决方案

#1

The max allocatable size is 2GB for malloc(which takes size_t). Hence your program crashes. I am assuming you're on a 32 bit machine.

malloc的最大可分配大小为2GB(需要size_t)。因此你的程序崩溃了。我假设你是32位机器。

Please see below link to learn more about it and test if you can actually allocate that much memory.

请参阅以下链接以了解有关它的更多信息并测试您是否可以实际分配那么多内存。

How Big can a malloc be in C

一个malloc在C中有多大

To get around this, you will need to write your own VIRTUAL MEMORY MANAGER and MEMORY ALLOCATOR using binary files and write your own free() and malloc() routines.

要解决这个问题,您需要使用二进制文件编写自己的VIRTUAL MEMORY MANAGER和MEMORY ALLOCATOR,并编写自己的free()和malloc()例程。

See here for an example(this is for iPhones only): Create your own VMM

请参阅此处获取示例(仅适用于iPhone):创建自己的VMM

#2

You need to take into account that the address range can be 32bit or 64 bit and some of that is required for the stack, other variables, housekeeping etc. In addition many (all?) OS have soft and hard limits to prevent a process soaking up all the physical and swap memory.

您需要考虑到地址范围可以是32位或64位,其中一些是堆栈,其他变量,内务管理等所需的。此外,许多(所有?)操作系统都有软限制和硬限制以防止进程浸泡所有物理和交换内存。

Anyway why are you doing this?

无论如何你为什么要这样做?

#1