Thread: How do I make a *HUGE* array in C++?

  1. #1
    Registered User
    Join Date
    Feb 2006
    Posts
    4

    How do I make a *HUGE* array in C++?

    Hi, I'm trying to work out the permutations of 6 numbers in 3 columns, long story short it works out to 720*720*720 permutations, or 373248000 columns by 18 rows. Is there some way to declare an array of this size or is there another way I should be looking at this problem? Any help will be much appreciated.

  2. #2
    Registered User
    Join Date
    Feb 2006
    Posts
    4
    I know that but I don't need to store one number of 373248000, i need to store 373248000 values in an array. Which makes an array of around 38 megabytes, which makes your value of 1844674407360955161, which is 6 bytes, look puny by comparison.

  3. #3
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    You should probably try to look at it another way. 6 billion values, even if they were only a byte each, is still more memory than people have on their machines. Each row is over 300 megabytes.

    Do you really need all values to be available at once? Can you use lazy evaluation to only compute and store the values you need? Perhaps you only ever need one chunk of columns at a time. If you need all the values available because it is expensive to recompute them, perhaps you can store the computed data in a file or files for lookup later. What types of values are your storing? If the range of numbers is small, you could use bit manipulation to combine the values to reduce the amount of memory you need.

    There are plenty of options, depending on the details of your circumstances.

  4. #4
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    I know that but I don't need to store one number of 373248000, i need to store 373248000 values in an array.
    Yes, I know. I thought an array subscript could be an unsigned long, but when I tried it on my computer I got an error about the subscript being too big. I got the same error for an int which is only roughly 2 billion--even though the first time I tried it, it worked.

  5. #5
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    Are you sure about the figures? 6 numbers taken 3 at a time gives me 120(6*5*4) permutations and if I allow reuse of numbers at most 216 (6*6*6)..maybe you stated something wrong or left out a detail

    Do you actually need to store the values or just use them? You can use std::next_permutation() to generate them as needed.

    You can also generate them to a file.
    Last edited by Darryl; 02-27-2006 at 01:18 PM.

  6. #6
    Registered User
    Join Date
    Feb 2006
    Posts
    4
    Quote Originally Posted by Daved
    You should probably try to look at it another way. 6 billion values, even if they were only a byte each, is still more memory than people have on their machines. Each row is over 300 megabytes.

    Do you really need all values to be available at once? Can you use lazy evaluation to only compute and store the values you need? Perhaps you only ever need one chunk of columns at a time. If you need all the values available because it is expensive to recompute them, perhaps you can store the computed data in a file or files for lookup later. What types of values are your storing? If the range of numbers is small, you could use bit manipulation to combine the values to reduce the amount of memory you need.

    There are plenty of options, depending on the details of your circumstances.
    Speed is essential for this program, but I could store the data to the drive, and since no value will be higher than 6, I'd only need one bit per value. I'm not to familiar with bit manipulation (Its been a while since assembly language where I learned that stuff) but I feel it may reduce the speed and I need a maximum look up time of 25 seconds. The reason I want to use an array is because of the enormous amount of data I need, which makes pointers impossible, otherwise I'd just do a sequential set of numbers but that would run the risk of writing over something important. I have enough RAM that I should have no problems running this, but I just need to find a way to store it all. I might be just pipe dreaming thinking this will work at all, but I was hoping a more experienced programmer would have heard of something like this and be able to help.

  7. #7
    Registered User
    Join Date
    Feb 2006
    Posts
    4
    Quote Originally Posted by Darryl
    Are you sure about the figures? 6 numbers taken 3 at a time gives me 120(6*5*4) permutations and if I allow reuse of numbers at most 216 (6*6*6)..maybe you stated something wrong or left out a detail

    Do you actually need to store the values or just use them? You can use std::next_permutation() to generate them as needed.

    You can also generate them to a file. Though it will end up being about 6 gig I imagine
    Its 3 sets of 6 numbers, 1 to 6, or 720 permutations per set, or 720 cubed possible permutations. I will have to look into that std::next_permutation() , I've never heard of it and it may be exactly what I need. I'm really just worried that with this many values a look up table might be necessary for the speeds I need it to run at, but I'll give it a go. Thanks.

  8. #8
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    for a value of 6 you'd need 3 bits 110=6

    Think we could see some code used to generate this list?

  9. #9
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    You only need one int to store a value from 1 to 720 that represents one of the 720 possible permutations. You need only 3 ints to indicate the values to be held in the columns for each row, and only 54 ints to indicate which permutations are held in the entire structure. You don't need to hold all possibilities, just the ones you are using. You could put the 720 permutations into an array, then have your 18 x 3 structure hold an index into that array for each location.

  10. #10
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    Code:
    #include <iostream>
    #include <deque>
    #include <string>
    #include <algorithm>
    
    std::deque<std::string> aset;
    unsigned lookup(std::string in)
    {
    	for (unsigned i = 0; i < 720; i++)
    		if (aset[i] == in) return i;
    }
    
    void printPermutation(int x, int y, int z)
    {
    	std::cout << aset[x] << "," << aset[y] << ","<< aset[z] << std::endl;
    }
    void printPermutation(unsigned ordinal)
    {
    	int x,y,z;
    	x= ordinal/518400;
    	ordinal-=(x*518400);
    	y = ordinal/720;
    	ordinal-=(y*720);
    	z = ordinal;
    	printPermutation(x,y,ordinal);
    }
    void printXYZ(std::string a, std::string b, std::string c)
    {	
    	std::cout << lookup(a) << "," << lookup(b) << ","<< lookup(c) << std::endl;
    }
    
    void printOrdinal(std::string a, std::string b, std::string c)
    {	
    	std::cout << lookup(a)*518400+ lookup(b)*720+lookup(c) << std::endl;
    }
    int main()
    {
    	std::string val = "123456";
    	aset.push_back(val);
    	while(std::next_permutation(val.begin(),val.end()))	aset.push_back(val);
    	std::cout << aset.size() << std::endl ; //just to show it create 720 permutations
    	printPermutation(3, 10, 650);
    	printPermutation(3057652);
    	printXYZ("156423","354216","615342");
    	printOrdinal("156423","354216","615342");
    }
    Last edited by Darryl; 02-27-2006 at 03:11 PM.

  11. #11
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    My version:
    Code:
    #include <iostream>
    #include <istream>
    #include <ostream>
    #include <algorithm>
    #include <iterator>
    #include <vector>
    #include <limits>
    #include <cstdlib>
    #include <ctime>
    
    typedef std::vector<int> data_set;
    typedef std::vector<data_set> data_row;
    typedef std::vector<data_row> data_table;
    
    void output_set(const data_set& out_set)
    {
        std::copy(out_set.begin(), out_set.end(), std::ostream_iterator<int>(std::cout, ","));
    }
    
    void output_row(const data_row& out_row)
    {
        std::cout << "|  ";
        for (data_row::const_iterator iter = out_row.begin(),
            end = out_row.end(); iter != end; ++iter)
        {
            output_set(*iter);
            std::cout << "  |  ";
        }
    }
    
    void output_table(const data_table& out_table)
    {
        for (data_table::const_iterator iter = out_table.begin(),
            end = out_table.end(); iter != end; ++iter)
        {
            output_row(*iter);
            std::cout << std::endl;
        }
    }
    
    int get_next_index(unsigned int num_choices)
    {
        static bool use_rand = false;
        if (!use_rand)
        {
            unsigned int index = num_choices;
            std::cout << "Pick a permutation (0-" << num_choices-1;
            std::cout << "), enter " << num_choices << " to pick randomly: ";
            while ((!(std::cin >> index)) || std::cin.peek() != '\n' || index > num_choices)
            {
                std::cin.clear();
                std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
                std::cout << "Invalid permutation index. Pick a permutation (0-";
                std::cout << num_choices-1 << ") or " << num_choices << ": ";
            }
            std::cin.ignore();
    
            if (index == num_choices)
            {
                use_rand = true;
                srand(static_cast<unsigned>(time(0)));
            }
            else
            {
                return index;
            }
        }
        return rand() % num_choices;
    }
    
    int main()
    {
        int base_set[] = { 1, 2, 3, 4, 5, 6 };
        const int num_n = (sizeof(base_set)/sizeof(base_set[0]));
        const int num_cols = 3;
        const int num_rows = 18;
    
        std::vector<data_set> permutations(1, std::vector<int>(base_set, base_set+num_n));
        while (std::next_permutation(base_set, base_set+num_n))
            permutations.push_back(std::vector<int>(base_set, base_set+num_n));
    
        const std::vector<data_set>::size_type num_permutations = permutations.size();
    
        data_table data(num_rows, data_row(num_cols, data_set(num_n)));
        for (int row_index = 0; row_index < num_rows; ++row_index)
            for (int col_index = 0; col_index < num_cols; ++col_index)
                data[row_index][col_index] = permutations.at(get_next_index(num_permutations));
    
        output_table(data);
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 05-29-2009, 07:25 PM
  2. Replies: 2
    Last Post: 07-11-2008, 07:39 AM
  3. Replies: 11
    Last Post: 09-22-2006, 05:21 PM
  4. Quick question about SIGSEGV
    By Cikotic in forum C Programming
    Replies: 30
    Last Post: 07-01-2004, 07:48 PM
  5. how to make a poiner array
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 12-03-2001, 09:12 PM