1,000,000,000 variables c++


Results 1 to 14 of 14

Thread: 1,000,000,000 variables c++

  1. #1
    Join Date
    Nov 2000
    Location
    ontario canada
    Posts
    189

    Question 1,000,000,000 variables c++

    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.:
    When your dreaming you are a pointer

  2. #2
    Join Date
    Dec 1999
    Location
    Fargo, ND
    Posts
    1,817
    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?
    Knute

    You live, you die, enjoy the interval!

  3. #3
    Join Date
    Sep 2002
    Posts
    974
    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.

  4. #4
    Join Date
    Jul 2003
    Posts
    28
    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.
    Last edited by grady; 08-22-2004 at 08:54 PM.

  5. #5
    Join Date
    Nov 2000
    Location
    ontario canada
    Posts
    189
    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.
    When your dreaming you are a pointer

  6. #6
    Join Date
    Dec 1999
    Location
    Fargo, ND
    Posts
    1,817
    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.
    Knute

    You live, you die, enjoy the interval!

  7. #7
    Join Date
    Nov 2000
    Location
    ontario canada
    Posts
    189
    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.
    When your dreaming you are a pointer

  8. #8
    Join Date
    May 2004
    Posts
    128
    "Never ask the barber if you need a haircut."

    Things could be worse...

    YnJldHRfYnVydG9uXzgyQHlhaG9vLmNvbQ== (hidemyemail.net)

    Use the MUTT Mailreader!

  9. #9
    Join Date
    Oct 2003
    Location
    Finland
    Posts
    231

    Post

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

  10. #10
    Join Date
    Mar 2003
    Location
    Hampton, VA
    Posts
    714
    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

  11. #11
    Join Date
    Nov 2000
    Location
    ontario canada
    Posts
    189
    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.
    When your dreaming you are a pointer

  12. #12
    Join Date
    Nov 2000
    Location
    ontario canada
    Posts
    189
    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.
    When your dreaming you are a pointer

  13. #13
    Join Date
    Dec 2003
    Location
    COLORADO
    Posts
    439
    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.
    Be AWARE: gramaticle/spelling errors will happen
    ReX Productions
    Current Web Project
    Join Project Honey Pot

  14. #14
    Join Date
    Nov 2003
    Posts
    90
    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.
    Last edited by jim mcnamara; 08-24-2004 at 12:22 PM.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •