Velocity Reviews > C++ > Re: multi-dimensional search algorithm blues...

# Re: multi-dimensional search algorithm blues...

Stuart Golodetz
Guest
Posts: n/a

 07-01-2003
"John Everett" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) om...
> 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

Yu Cao
Guest
Posts: n/a

 07-02-2003
http://www.velocityreviews.com/forums/(E-Mail Removed) (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