large array declaration

general
, ,
1

i need some container to store data for dynamic programming. In simple terms i need

long long int array[100000][100000];
but it is not possible in c++. Please tell me some alternative way to store data values.

2

@sharru05…

  • size of long long int : 8 bytes(64 bits)

  • total contiguous memory u need

  • 64X100000X100000 bits=640000 MB(approx)=640 GB (approx)

    • 74.5058059692383 gigabytes(Exactly)

  • how can any1 provide you so big chunk of memory at contiguous allocation??
    I don’t think there is a way to do so…if any please tell me too…***

1 Like
3

What is the problem at hand? For most problems in a competition, the constrains will usually be such that you possibly won’t need this big a matrix at any time. And you can always request memory from the heap (until the heap grows into the stack) depending on dimensions required for current state of the problem.

4

74.5058059692383 gigabytes(Exactly)

can any compiler or OS can provide so much memory (640 GB )to user to run his/her program…??
can u explain or give me some link for reference??

5

I had same doubt earlier see here

Notice the down-votes and read comments.(It was asked by me :D)

6

In Dynamic programming problems, you need space storage to hold the previous calculated data.

In Bottom up approach, You unnecessarily allocate large memory for previous calculations. Even most of the memory allocated do not required in the actual problems. So In those cases where large memory allocated does not used by the program, you can follow top down approach. You can read more about those approaches here.

So instead of declaring a large array, you can use map<int,int> where first element will be used as an index and second element actual will store the data value. You can use map instead of arrays in top down approach which will make your program time as well as space optimised.

You can read more about the maps on this page.