1,000,000,000 variables c++

[knavely]

hi
im working on a project in c++
basically I need to work with 1,000,000,000 points (x,y)
where x,y are integers.

I am simply unsure of how to do this. One way or another, im going to need to access that much information, so i cant see a way around storring everything in memory.

just wonderring if anyone has any suggestions, is there a standard way of dealing with such huge numbers of things? Is this when you bring in a database? or is this when you start putting togethar something with 4 GB of ram?



thanks.:

[knute]

First off, is this homework?

Second off, Why do you need to deal with all 1 billion points at once? What states could any/all of these points be at any point in time?

[Fryguy8]

one billion ints isn't even the limit of 32-bit, so unless these are more complex data types than 4-bit ints, I don't really see a problem of just defining it as an array. Your program will be slow an inefficient as hell, and probably a candidate for something like a hash table, but that depends on implementation.

[grady]

You could store the data in a file, or multiple files, and write a class that acts like an array by overloading operator[]. The class could manage fetching chunks of data from disk when you query for something outside the ranges it already has stored in memory.

Depending on how you are going to access the data, the scheme you use for fetching chunks of data from disk could get complicated. And if you fetch over the whole range at random, it might be hard to come up with anything at all that is effecient.

What are you working on that needs this many points? Maybe the problem can be simplified.

[knavely]

thanks for the responses

the project is a cellular automaton simulator specifically designed to simulate the number preserving variety.

no, this is not homework...

the point of this is to provide a visual simulation of massive amounts of particles , in order to find some clues about their mathematical properties.
we have a grid, and on it are particals, which at each time click, look at the grid sites in their neighborhood, and decide based on a rule where to move to.

for example if the neighborhood is something simple(generally it is not simple) like right neighbor left neighbor

a partical at point 4,0 would look at sites (3,0) and (5,0)
and depending on what it sees decides what to do based on the rule.

the combinations are: partical, not partical
np , p
np,np
p, p
the rule provides a destination for the partical based on which of the combinatios is present.

the neighborhood, and the rule are both input by the user .

we can represent the grid as a lattice or a 2d array.
which i did like this
bool cells[2][num][num] though in reality i did this dynamically but...

its 3d because when we apply the rule and the particals move, we dont want to loose the inormation in the past.
so im playing games like cells[current][i][j] , cells[!current][i][j].

anyhow, this system works nicely up and untill when num gets to be around 1000. then its horrably slow .
if i try to set num to 2000 , the process gets killed before it starts.

my next idea was to forget representing the entire grid and just represent each partical with a small data structure:
current location : x,y
future location: x,y

once i get to around 10,000,000 particals the thing gets quite slow.


thanks alot for the help.

[knute]

Then all you really need to do is to keep a list of either the particle or not-particle. If it's in the list it's either one or the other, if it's not in the list it's the opposite. Then when it moves, it updates the list accordingly.

[knavely]

yea, iv done that, like i said.
it works fine, but when i add too many particals , i get the same problem.

im getting the impression that its not a memory problem after all.

on the other hand it seems like i just cant allocate beyond a certain amount.

[bburton]

http://www.mysql.com/

[lagitus]

Try storing your data in a file and mmap() it for convenient memory-like access.

[evac-q8r]

Could you provide an example of exactly how the rules are (not like the Mickey Mouse example provided)? Based off of the example provided can't really understand the dynamical process. I think I see the difficulty in this problem. It seems like you must start the process at one particle and watch the propagation of the system dynamics from that one particle. Otherwise, you'd need to set a probability distribution of how the particles can move based off of the rule and then Monte Carlo simulate somehow.

EVAC

[knavely]

actually its not much more complicated then the mickey mouse one. since we are only dealing with systems which preserve the number of particals, we are actually only looking at trajectory rules.

so lets say our neighborhood is
{(1,0), (-1,0), (0,1), (0,-1)}
this means that at each time click a particle looks
up, down , left, and right one spot on the lattice.

we define a configuration as a bit string of length 4 which corresponds to what the partical sees when it looks at the sites in neighborhood, togethar with a destination point in the neighborhood.

a rule in this case is a set of 2^4 configurations in which each possible bit string is present.
in this case a rule could be:
1111 1,0 1000 1,0
1110 1,0 0100 1,0
1101 1,0 0010 1,0
1011 1,0 0001 1,0
0111 1,0 1001 1,0
1100 1,0 0101 1,0
1010 1,0 0011 1,0
0110 1,0 0000 1,0

of course this is just a trivial shift rule

some rules like this one, preserve the number of particals because there are no collitions. this is the class of rules we are interested in.

thanks again for everyoens thoughts.
unfamiliar with mmap() it sounds interesting though, ill have to look it up.

[knavely]

sorry the way i wrote the rule looks confusing
its really more like this
Rule R = { 1111 1,0
1000 1,0
1110 1,0
0100 1,0
1101 1,0
0010 1,0
1011 1,0
0001 1,0
0111 1,0
1001 1,0
1100 1,0
0101 1,0
1010 1,0
0011 1,0
0110 1,0
0000 1,0 }

should have added commas or better notation to the other one.

[thaddaeus]

this sounds an awful lot like the marine biology case study we did for my high school ap comp sci, except with fishies, and sharks and mines that blow up all the fishies, i don't remember anything about it though so really this post is of no help.

[jim mcnamara]

Consider creating a file of your points - looks like you can represent things with either char or bitmaps - to save memory. The smaller the impact on virtual memory, the faster your code will run.

After you mmap() the file, call madvise() with MADV_RANDOM so that the kernel only swaps in/out small chunks of the file, which will speed things up as well. YMMV.

Since it seems you are coding in C, you may want to consider bit-fields to make your code a little more maintainable, if you opt for bitmap representations of data. Bitmapping gets your data memory storage requirement down to ~125MB.

Edit:
You may also want to call mmap() with MAP_SHARED so that the backing store is the file itself. This saves a lot of impact on other processes, and possibly yours as well.