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

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

1. ### Yu CaoGuest

(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