Really large array

ever tried to make a huge array?

  • (2 Pages)
  • +
  • 1
  • 2

17 Replies - 5104 Views - Last Post: 03 December 2008 - 08:55 AM Rate Topic: -----

#1 badjava  Icon User is offline

  • Lux Ex Tenebris
  • member icon

Reputation: 14
  • View blog
  • Posts: 540
  • Joined: 30-October 08

Really large array

Post icon  Posted 03 December 2008 - 01:18 AM

I'm working one of the Fibonacci problems on project Euler and as one way to brute force it I attempted to make an array with 4,000,000 elements. I was able to compile without error but at run time the program fails out with no error message and dies.

If I make an array with 400,000 elements it works fine but one more decimal place and BAM. Now I have a machine with 4 GB of ram that I could try to run this on and see if it is just running out of memory but I suspect there is something else going on.

Does anyone know what the limits are in C++ or windows or what not when making some big nasty ugly array like this?

I just learned about dynamic arrays so I'm going to take another shot at the project Euler problem and see if I can get it to work if I don't try to hit the full array right at run time.

I'm also probably not solving the problem correctly as I don't understand exactly what they are asking for. It sure is easier to solve a problem if you are trying to solve the right one!

Post a note up here if you've done the first few Euler problems, we can get a thread going for people running through their riddles and help each other out eh?

Oh and make sure to give a ty to gabehabe and anyone else who also recommended the site for developing logic design skills!

Is This A Good Question/Topic? 0
  • +

Replies To: Really large array

#2 janotte  Icon User is offline

  • code > sword
  • member icon

Reputation: 990
  • View blog
  • Posts: 5,141
  • Joined: 28-September 06

Re: Really large array

Posted 03 December 2008 - 02:32 AM

What data type are you using in your array?

The maximum value range for int is:
signed: -2147483648 to 2147483647
unsigned: 0 to 4294967295

Is it possible you are exceeding the max size of int?

Your solution may be no more difficult than making the data type long instead of int.

More info:
http://www.cplusplus.../variables.html
Was This Post Helpful? 0
  • +
  • -

#3 badjava  Icon User is offline

  • Lux Ex Tenebris
  • member icon

Reputation: 14
  • View blog
  • Posts: 540
  • Joined: 30-October 08

Re: Really large array

Posted 03 December 2008 - 03:16 AM

View Postjanotte, on 3 Dec, 2008 - 01:32 AM, said:

What data type are you using in your array?

The maximum value range for int is:
signed: -2147483648 to 2147483647
unsigned: 0 to 4294967295

Is it possible you are exceeding the max size of int?

Your solution may be no more difficult than making the data type long instead of int.

More info:
http://www.cplusplus.../variables.html


My data type is int and I'm only creating the array with 4million elements so that should fit well within bounds. Even more curious I don't assign any values to the elements, it doesnt get that far. So it dies before it hits any bounds of the type restriction, all I do is create the array and the program dies.

This is all that it takes to bomb out the program:
int int_array [4000000];

I don't load anything in the array or initialize it in any way. If I take out one zero it appears to works fine.

Should I just try it on my 4Gb RAM work station and see what happens? Do you think it could work on a different computer?
Was This Post Helpful? 0
  • +
  • -

#4 janotte  Icon User is offline

  • code > sword
  • member icon

Reputation: 990
  • View blog
  • Posts: 5,141
  • Joined: 28-September 06

Re: Really large array

Posted 03 December 2008 - 03:28 AM

I'm intrigued.

Do you feel like posting your code so I can try and run it?

Only if you want to.
Was This Post Helpful? 0
  • +
  • -

#5 badjava  Icon User is offline

  • Lux Ex Tenebris
  • member icon

Reputation: 14
  • View blog
  • Posts: 540
  • Joined: 30-October 08

Re: Really large array

Posted 03 December 2008 - 03:34 AM

View Postjanotte, on 3 Dec, 2008 - 02:28 AM, said:

I'm intrigued.

Do you feel like posting your code so I can try and run it?

Only if you want to.


Absolutely, this is it - no kidding:
#include <cstdlib>
#include <iostream>
#include <string>

using namespace std;

int main()
{
	int int_array [4000000];
	system("PAUSE");
	return EXIT_SUCCESS;
}


The includes that aren't used are just left over from the previous file I gutted to slap this together for a test. This is being run on a bit of an overworked p4 2ghz laptop with 500 mb of ram and azureus, firefox (what a ram whore), dev c++, yahoo messenger and various yahoo widgets running. So I wouldnt be surprised if it runs somewhere else, I just thought someone else might have run in to a max array size before windows pukes u know?

This post has been edited by badjava: 03 December 2008 - 03:38 AM

Was This Post Helpful? 0
  • +
  • -

#6 janotte  Icon User is offline

  • code > sword
  • member icon

Reputation: 990
  • View blog
  • Posts: 5,141
  • Joined: 28-September 06

Re: Really large array

Posted 03 December 2008 - 03:46 AM

Ah ha - when you running you are getting a "Segmentation Fault" and I am guessing it is because you are exceeding the stack size as discussed here.
http://stackoverflow...ngth-limit-in-c

I think I used to know this and forgot it.

I think you will avoid this problem by using vectors instead of arrays.

You might also be able to get yourself a bigger stack via malloc() but I am so rusty on all that I'd need to re-read.

This post has been edited by janotte: 03 December 2008 - 03:48 AM

Was This Post Helpful? 0
  • +
  • -

#7 badjava  Icon User is offline

  • Lux Ex Tenebris
  • member icon

Reputation: 14
  • View blog
  • Posts: 540
  • Joined: 30-October 08

Re: Really large array

Posted 03 December 2008 - 03:56 AM

View Postjanotte, on 3 Dec, 2008 - 02:46 AM, said:

Ah ha - when you running you are getting a "Segmentation Fault" and I am guessing it is because you are exceeding the stack size as discussed here.
http://stackoverflow...ngth-limit-in-c

I think I used to know this and forgot it.

I think you will avoid this problem by using vectors instead of arrays.

You might also be able to get yourself a bigger stack via malloc() but I am so rusty on all that I'd need to re-read.


Ah awesome, ty :) I will be doing some reading also and some experimenting as well, muahaha... (evil dr frankenstein laugh) :)

This post has been edited by badjava: 03 December 2008 - 03:57 AM

Was This Post Helpful? 0
  • +
  • -

#8 janotte  Icon User is offline

  • code > sword
  • member icon

Reputation: 990
  • View blog
  • Posts: 5,141
  • Joined: 28-September 06

Re: Really large array

Posted 03 December 2008 - 04:03 AM

View Postbadjava, on 3 Dec, 2008 - 02:56 AM, said:

muahaha... (evil dr frankenstein laugh) :)


Well earned evil laugh!

Great question! :^:
Was This Post Helpful? 1
  • +
  • -

#9 badjava  Icon User is offline

  • Lux Ex Tenebris
  • member icon

Reputation: 14
  • View blog
  • Posts: 540
  • Joined: 30-October 08

Re: Really large array

Posted 03 December 2008 - 04:13 AM

View Postjanotte, on 3 Dec, 2008 - 03:03 AM, said:

View Postbadjava, on 3 Dec, 2008 - 02:56 AM, said:

muahaha... (evil dr frankenstein laugh) :)


Well earned evil laugh!

Great question! :^:


Check out my new code:
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
	vector <char> CA;
	CA.assign (4000000, 'a');

for(int i = 0; i <= CA.size(); i++)
{
   cout << "the count is: " << i << " for element " << CA[i] << endl;
   
}

	system("PAUSE");
	return EXIT_SUCCESS;
}



This is running without crashing and is currently printing element 500000 or so out of the 4 million.

Great response ty!
Was This Post Helpful? 1
  • +
  • -

#10 badjava  Icon User is offline

  • Lux Ex Tenebris
  • member icon

Reputation: 14
  • View blog
  • Posts: 540
  • Joined: 30-October 08

Re: Really large array

Posted 03 December 2008 - 04:31 AM

To Moderators:

Would it be possible to merge this thread in with my project Euler thread here.

This is relevant to the 2nd or 3rd in the Euler series of problems and would be great to have in the thread.
Was This Post Helpful? 0
  • +
  • -

#11 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5801
  • View blog
  • Posts: 12,636
  • Joined: 16-October 07

Re: Really large array

Posted 03 December 2008 - 05:17 AM

When arrays give seg faults, you generally do linked lists...

I'm curious. A really large array for the Fibonacci sequence? You generally don't need any array for that, you can produce it with three variables. Could you link to the puzzle you're trying?
Was This Post Helpful? 0
  • +
  • -

#12 badjava  Icon User is offline

  • Lux Ex Tenebris
  • member icon

Reputation: 14
  • View blog
  • Posts: 540
  • Joined: 30-October 08

Re: Really large array

Posted 03 December 2008 - 05:32 AM

View Postbaavgai, on 3 Dec, 2008 - 04:17 AM, said:

When arrays give seg faults, you generally do linked lists...

I'm curious. A really large array for the Fibonacci sequence? You generally don't need any array for that, you can produce it with three variables. Could you link to the puzzle you're trying?


Sure, I would love to hear feedback on my more than likely erroneous approach to the problem. At the time I wasn't sure if we needed to add up 4000000 variables or the variables added up can't exceed 4000000. I wasn't sure what the question was asking for so I tried to store the variables in the big nasty array while I was testing out different solution methods and ran across the 'big crash'.

I think it actually is asking for the individual numbers each respectively under 4000000 in size to be added up and then post the sum.

Here is the link . If you have a suggestion on the logic required I would like to see what you think.
Was This Post Helpful? 0
  • +
  • -

#13 gabehabe  Icon User is offline

  • GabehabeSwamp
  • member icon




Reputation: 1382
  • View blog
  • Posts: 10,962
  • Joined: 06-February 08

Re: Really large array

Posted 03 December 2008 - 05:51 AM

Hint: b2c has a snippet for it.
Was This Post Helpful? 0
  • +
  • -

#14 janotte  Icon User is offline

  • code > sword
  • member icon

Reputation: 990
  • View blog
  • Posts: 5,141
  • Joined: 28-September 06

Re: Really large array

Posted 03 December 2008 - 05:56 AM

View Postbaavgai, on 3 Dec, 2008 - 04:17 AM, said:

When arrays give seg faults, you generally do linked lists...


This a great thread. Forcing all sorts of stuff back into my brain that fell out some time ago.

From here:
http://www.cplusplus...nce/stl/vector/
"Compared to the other base standard sequence containers (deques and lists), vectors are generally the most efficient in time for accessing elements and to add or remove elements from the end of the sequence. For operations that involve inserting or removing elements at positions other than the end, they perform worse than deques and lists, and have less consistent iterators and references than lists."
Was This Post Helpful? 0
  • +
  • -

#15 badjava  Icon User is offline

  • Lux Ex Tenebris
  • member icon

Reputation: 14
  • View blog
  • Posts: 540
  • Joined: 30-October 08

Re: Really large array

Posted 03 December 2008 - 06:16 AM

View Postjanotte, on 3 Dec, 2008 - 04:56 AM, said:

they perform worse than deques and lists, and have less consistent iterators and references than lists."


I haven't been pushed out of the 'list nest' yet but it gets referred to enough it must be pretty handy, I think I'll read up on that next.

As for deques, I've never even heard of that in reference to a programming language! Whoa. I'll have to see if I can somehow squeeze it in to my next project and freak my professor out :lol:

View Postgabehabe, on 3 Dec, 2008 - 04:51 AM, said:

Hint: b2c has a snippet for it.


Hey I missed this one, I'll see if i can find da code, ty! Well I looked and I'm not sure which one you refer to, the recursive fib generator? I was hoping he had a snip on the Euler prob itself muahaha :) I haven't tried any recursion yet but maybe I can haxx up his snippet to detect and add up the right numbers as they grind through...

This post has been edited by badjava: 03 December 2008 - 06:20 AM

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2