Re: multi-dimensional search algorithm blues...

Discussion in 'C++' started by Stuart Golodetz, Jul 2, 2003.

  1. "John Everett" <> wrote in message
    news:...
    > 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:


    Assuming the dots in each of the two arrays are unique (i.e. a dot in A_dots
    might be duplicated in B_dots, but not in A_dots), you could simply do the
    following:

    1) Concatenate the two arrays (O(n))
    2) Sort them (using an algorithm with worst case O(n lg n) complexity)
    3) Run through looking for any element which is not duplicated (O(n))

    For an overall complexity of O(n lg n), I think.

    HTH,

    Stuart.

    > 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.
    >
    > ~ John
    > ____________________________
    > John K. Everett
    > Rutgers University / UMDNJ
    > Graduate program in Biochemistry
     
    Stuart Golodetz, Jul 2, 2003
    #1
    1. Advertising

  2. Stuart Golodetz

    Yu Cao Guest

    (John Everett) writes:

    >Stuart...


    > The concatentation idead knocked the process down
    >to 5 minutes. Great idea. Thanks!


    That is still way too long -- you only had 2x speedup, so it appears
    your algorithm is still O(N^2). Does the sorting algorithm you used
    have "bubble" in its name? If so, change it. It really should be less
    than a few seconds, if that.

    And yes ... this is getting off-topic.

    --Yu
     
    Yu Cao, Jul 2, 2003
    #2
    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. Yu Cao
    Replies:
    0
    Views:
    475
    Yu Cao
    Jul 1, 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:
    392
    John Everett
    Jul 4, 2003
  3. Alf P. Steinbach
    Replies:
    0
    Views:
    455
    Alf P. Steinbach
    Aug 18, 2003
  4. Angus
    Replies:
    14
    Views:
    508
    James Kanze
    Mar 10, 2011
  5. Wirianto Djunaidi
    Replies:
    2
    Views:
    229
    Wirianto Djunaidi
    Apr 29, 2008
Loading...

Share This Page