Re: multi-dimensional search algorithm blues...

Discussion in 'C++' started by Yu Cao, Jul 1, 2003.

  1. Yu Cao

    Yu Cao Guest

    (John Everett) writes:

    >News group,


    > I am relatively new to C++ and I have a question regarding searching arrays.
    >I need to search two rather large arrays 'quickly'.


    >Here is the setup:


    >There are two arrays ( A_dots and B_dots ).
    >each array is set up like this:
    > float A_dots[100000][3];
    > float B_dots[100000][3];


    >each array holds the x,y,z coordinates of a point in space.


    >Here is the problem:


    >There are ~1000 points in A_dots that are NOT in B_dots and
    >I need to find them. The only method I currently have is a
    >beat it over the head approach:


    >int found;


    >for (int x=0; x<=100000; x++)
    > {
    > found = 0;


    > for (int y=0; y<=100000; y++)
    > {
    > if ( A_dots[x][0] == B_dots[y][0] &&
    > A_dots[x][1] == B_dots[y][1] &&
    > A_dots[x][2] == B_dots[y][2] )
    > {
    > found = 1;
    > continue;
    > }
    > }
    >
    > if ( ! found ) { // record the dot }
    > }



    > This approach takes ~10 minutes to run even when I try to
    >optimize my complier ( g++ -O3 ). If anyone knows a faster
    >way to search the data... I would truly appreciate it.


    Here's one way. First define a data structure for dot with a suitable
    function for comparison:

    struct Dot
    {
    float x, y, z;

    friend operator< (const Dot& dot1, const Dot& dot2)
    {
    // establish order in R^3
    if (dot1.z < dot2.z)
    return true;
    else if (dot1.z > dot2.z)
    return false;
    else if (dot1.y < dot2.y)
    return true;
    else if (dot1.y > dot2.y)
    return false;
    else if (dot1.x < dot2.x)
    return true;
    else
    return false;
    }
    };

    Then hold your B_dots with an std::set container:

    #include <set>
    std::set<Dot> B_dots;
    // insert coordinates into B_dots

    Then loop over A_dots, and call B_dots.find() with each dot in A_dots.

    Certainly not the most efficient implementation, but enough to cut the
    time from O(N^2) to O(N logN).

    --Yu
     
    Yu Cao, Jul 1, 2003
    #1
    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. Stuart Golodetz
    Replies:
    1
    Views:
    483
    Yu Cao
    Jul 2, 2003
  2. =?iso-8859-1?Q?Juli=E1n?= Albo

    Re: multi-dimensional search algorithm blues...

    =?iso-8859-1?Q?Juli=E1n?= Albo, Jul 2, 2003, in forum: C++
    Replies:
    1
    Views:
    385
    John Everett
    Jul 4, 2003
  3. Alf P. Steinbach
    Replies:
    0
    Views:
    439
    Alf P. Steinbach
    Aug 18, 2003
  4. Angus
    Replies:
    14
    Views:
    496
    James Kanze
    Mar 10, 2011
  5. Wirianto Djunaidi
    Replies:
    2
    Views:
    204
    Wirianto Djunaidi
    Apr 29, 2008
Loading...

Share This Page