Storing large number of values in 2D array

Discussion in 'C Programming' started by rajus, Oct 20, 2006.

  1. rajus

    rajus Guest

    I want to store the (x,y) coordinates of about 10,000 points in a 2D
    array.How can I store them and retrieve them later?
     
    rajus, Oct 20, 2006
    #1
    1. Advertising

  2. rajus

    Lew Pitcher Guest

    rajus wrote:
    > I want to store the (x,y) coordinates of about 10,000 points in a 2D
    > array.How can I store them and retrieve them later?


    I'm afraid that your question doesn't relate specifically to the use of
    the C langage, and is off topic in this forum. You might try one of the
    comp.programming groups where they discuss algorithms and data
    structures.

    But, before you go, why don't you think about a sparse matrix
    implementation?
    Something like
    struct { long x; long y; } coord[10000];

    HTH
    --
    Lew Pitcher
     
    Lew Pitcher, Oct 20, 2006
    #2
    1. Advertising

  3. rajus

    jacob navia Guest

    rajus wrote:
    > I want to store the (x,y) coordinates of about 10,000 points in a 2D
    > array.How can I store them and retrieve them later?
    >

    You have 10 000 x 2 points i.e. 20 000 points to store.
    To minimize space you could use 12 bits (coordinates up
    to 4096x4096) and store 5 points per 64 bits, making it
    around 32 000 bytes for the 2D array.

    Using only 10 bits (1024x1024 coordinates) you would store
    6 points per 64 bits unit, around 26 666 bytes for the array.

    You would need to develop a small package that reads any sequence of
    10 or 12 bits in the array, making a function like

    uint32 GetPointsCoords(int x,int y)
    {
    // Here you calculate the offset in the array
    // of your point, and return a 32 bit result
    // containing in the upper 16 bits the y coordinate
    // and in the lower 16 bits the x coordinate
    // for instance.
    }

    You can save yourself development time of course if you
    just make

    unsigned short array[10000][2];

    This would take 40 000 bytes, an increase of 14 000
    but no development effort, you just index the array:

    x = array[2357][0];
    y = array[2357][1];

    With short in 16 bits, you would get enough coordinate space to go
    to 65535 x 65535 screens. The largest screens today go to
    2500 x 2000 so your software will last (for a while...)

    jacob
     
    jacob navia, Oct 20, 2006
    #3
  4. rajus

    Al Balmer Guest

    On Fri, 20 Oct 2006 20:46:28 +0200, jacob navia
    <> wrote:

    >rajus wrote:
    >> I want to store the (x,y) coordinates of about 10,000 points in a 2D
    >> array.How can I store them and retrieve them later?
    >>

    >You have 10 000 x 2 points i.e. 20 000 points to store.
    >To minimize space you could use 12 bits (coordinates up
    >to 4096x4096) and store 5 points per 64 bits, making it
    >around 32 000 bytes for the 2D array.


    Of course, the extra code required to do this would probably make up
    for the saved space. I like Lew's suggestion, using whatever size
    integer is appropriate.

    --
    Al Balmer
    Sun City, AZ
     
    Al Balmer, Oct 20, 2006
    #4
  5. rajus

    Guest

    rajus wrote:
    > I want to store the (x,y) coordinates of about 10,000 points in a 2D
    > array.How can I store them and retrieve them later?


    #include <stdlib.h>
    #include <stdio.h>

    typedef struct point {
    double x;
    double y;
    } point, *pointAddr;

    static size_t dim = 10000u;

    int main(void)
    {
    size_t i;

    /* The use of calloc to zero array of floats is not portable. */
    /* Allocate array with malloc() */
    pointAddr array = malloc(dim * sizeof( point) );
    /* Check for success */
    if (array == NULL) {
    puts("FATAL ERROR: Out of memory.");
    exit(EXIT_FAILURE);
    }
    /* Initialize array to a known state. */
    for (i = 0; i < dim; i++) {
    array.x = 0;
    array.y = 0;
    }

    /* do whatever you like with the array here... */

    return 0;
    }
     
    , Oct 20, 2006
    #5
  6. rajus

    Guest

    Lew Pitcher wrote:
    > rajus wrote:
    > > I want to store the (x,y) coordinates of about 10,000 points in a 2D
    > > array.How can I store them and retrieve them later?

    >
    > I'm afraid that your question doesn't relate specifically to the use of
    > the C langage, and is off topic in this forum. You might try one of the
    > comp.programming groups where they discuss algorithms and data
    > structures.


    If this isn't a C question, then I don't know what one is.

    > But, before you go, why don't you think about a sparse matrix
    > implementation?
    > Something like
    > struct { long x; long y; } coord[10000];


    With 10,000 points, a sparse array implementation is a total waste of
    time and energy.

    Even with doubles that's {typically} 16*10,000 = 160,000 bytes.

    Considering 1 GB of PC3200 DDR2 ECC ram at $112:
    http://www.ramseeker.com/pc/index.php
    that's about 1/2 cent worth of memory. Hardly worth worrying about
    sparse implementations.

    IMO-YMMV.

    > HTH
    > --
    > Lew Pitcher
     
    , Oct 20, 2006
    #6
  7. rajus

    Guest

    rajus wrote:
    > I want to store the (x,y) coordinates of about 10,000 points in a 2D
    > array.How can I store them and retrieve them later?


    Something a bit ambiguous about your post is:
    "How can I store them and retrieve them later?"

    You can obviously poke them into an array and pull them out when you
    need them. The code I posted earlier is an example of how you might
    prepare an array of 2d points for use.

    But you might be talking about permanent storage. In such a case, the
    C answer is to use fwrite() to save them to disk and fread() to read
    them back into memory. This answer is not portable across different
    systems because different systems have different binary formats. In
    other words, if you write out binary data using fwrite() then you
    should only read the data back into memory using fread() on machines
    with similar architecture. So if you wrote the data out on a Windows
    machine, it probably won't read in correctly on a SPARC machine.

    Also, if you plan to have many sets of data (or need the binary
    compatibility referred to above), you might want to store them in a
    database.

    We do not have enough information for a very clear answer if you want
    to know about long term storage and retrieval.
     
    , Oct 20, 2006
    #7
  8. rajus

    Guest

    wrote:
    [snip]
    > With 10,000 points, a sparse array implementation is a total waste of
    > time and energy.
    >
    > Even with doubles that's {typically} 16*10,000 = 160,000 bytes.
    >
    > Considering 1 GB of PC3200 DDR2 ECC ram at $112:
    > http://www.ramseeker.com/pc/index.php
    > that's about 1/2 cent worth of memory. Hardly worth worrying about
    > sparse implementations.


    Time to temper my remark. I keep forgetting that much of (most?) C
    programming is actually embedded work. On an embedded system, you
    might have very limited resources. In such a circumstance, a skiplist
    might be a good way to store a sparse vector.

    There are advanced codes available for sparse matrices and vectors, but
    generally they are designed for huge data sets.
     
    , Oct 20, 2006
    #8
  9. wrote:
    > Lew Pitcher wrote:
    > > rajus wrote:
    > > > I want to store the (x,y) coordinates of about 10,000 points in a 2D
    > > > array.How can I store them and retrieve them later?

    > >
    > > I'm afraid that your question doesn't relate specifically to the use of
    > > the C langage, and is off topic in this forum. You might try one of the
    > > comp.programming groups where they discuss algorithms and data
    > > structures.

    >
    > If this isn't a C question, then I don't know what one is.


    You got that one right!

    - William Hughes
     
    William Hughes, Oct 20, 2006
    #9
  10. writes:
    > Lew Pitcher wrote:
    >> rajus wrote:
    >> > I want to store the (x,y) coordinates of about 10,000 points in a 2D
    >> > array.How can I store them and retrieve them later?

    >>
    >> I'm afraid that your question doesn't relate specifically to the use of
    >> the C langage, and is off topic in this forum. You might try one of the
    >> comp.programming groups where they discuss algorithms and data
    >> structures.

    >
    > If this isn't a C question, then I don't know what one is.
    >
    >> But, before you go, why don't you think about a sparse matrix
    >> implementation?
    >> Something like
    >> struct { long x; long y; } coord[10000];

    >
    > With 10,000 points, a sparse array implementation is a total waste of
    > time and energy.
    >
    > Even with doubles that's {typically} 16*10,000 = 160,000 bytes.


    Suppose each (x,y) coordinate consists of a pair of integers, each of
    which can be in the range 0..999999. If the OP wants to store
    information about each point in the corresponding element of a 2D
    array, the array would have to have one trillion (10**12) elements.
    Some sort of sparse array representation is just about mandatory.

    I think the OP wants to store information about a point, and use the
    coordinates of the point to retrieve it later. I might consider using
    a hash table, hashing the (x,y) coordinate pair to obtain the
    retrieval key.

    But we need more information from the OP. How are the (x,y)
    coordinates represented (int, double, whatever)? What are the
    possible ranges? What information to you need for each point? How
    important is fast access to each point?

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
     
    Keith Thompson, Oct 20, 2006
    #10
  11. rajus wrote:
    > I want to store the (x,y) coordinates of about 10,000 points in a 2D
    > array.How can I store them and retrieve them later?


    Well, declare a 2D array of points. Store points in the array. Retireve them
    later from the array. What exactly is the problem that makes you ask such a
    trivial question?

    --
    Best regards,
    Andrey Tarasevich
     
    Andrey Tarasevich, Oct 20, 2006
    #11
  12. rajus

    jacob navia Guest

    Al Balmer wrote:
    > On Fri, 20 Oct 2006 20:46:28 +0200, jacob navia
    > <> wrote:
    >
    >
    >>rajus wrote:
    >>
    >>>I want to store the (x,y) coordinates of about 10,000 points in a 2D
    >>>array.How can I store them and retrieve them later?
    >>>

    >>
    >>You have 10 000 x 2 points i.e. 20 000 points to store.
    >>To minimize space you could use 12 bits (coordinates up
    >>to 4096x4096) and store 5 points per 64 bits, making it
    >>around 32 000 bytes for the 2D array.

    >
    >
    > Of course, the extra code required to do this would probably make up
    > for the saved space. I like Lew's suggestion, using whatever size
    > integer is appropriate.
    >


    I do not think that a simple code for accessing a 2D 12 bit
    integer array would make 14 000 bytes of code in C.
    At most it would take 150-200 bytes of code, maybe more in RISC
    processors, but never 12 000 bytes.

    But that was a memory efficient solution, good for embedded
    systems where memory considerations are important.

    I proposed also a 16 bit solution, not knowing precisely the context.

    What is important to emphasize is that integers of bit-size other
    than 8-16-32 are possible, and can be a space saving in many situations.

    I have seen proposals to add to C
    int:12 a;

    meaning a is a 12 bit integer. This, with support for array notation of
    those integers would be interesting in systems where memory is important

    jacob
     
    jacob navia, Oct 20, 2006
    #12
  13. rajus

    Al Balmer Guest

    On Fri, 20 Oct 2006 14:04:48 -0700, Andrey Tarasevich
    <> wrote:

    >rajus wrote:
    >> I want to store the (x,y) coordinates of about 10,000 points in a 2D
    >> array.How can I store them and retrieve them later?

    >
    >Well, declare a 2D array of points. Store points in the array. Retireve them
    >later from the array. What exactly is the problem that makes you ask such a
    >trivial question?


    Trivial questions are not unwelcome here.

    However, your question, "What exactly is the problem", is certainly
    pertinent here, and the answer to that might make the original
    question less trivial :)

    --
    Al Balmer
    Sun City, AZ
     
    Al Balmer, Oct 21, 2006
    #13
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. toton
    Replies:
    11
    Views:
    721
    toton
    Oct 13, 2006
  2. Albert
    Replies:
    11
    Views:
    666
    CBFalconer
    Jan 31, 2009
  3. Hasit Mistry

    Storing a very large number

    Hasit Mistry, Jul 17, 2013, in forum: Python
    Replies:
    1
    Views:
    90
    Grant Edwards
    Jul 17, 2013
  4. Gary Herron

    Re: Storing a very large number

    Gary Herron, Jul 17, 2013, in forum: Python
    Replies:
    0
    Views:
    112
    Gary Herron
    Jul 17, 2013
  5. Ian Kelly

    Re: Storing a very large number

    Ian Kelly, Jul 17, 2013, in forum: Python
    Replies:
    0
    Views:
    114
    Ian Kelly
    Jul 17, 2013
Loading...

Share This Page