Velocity Reviews - Computer Hardware Reviews

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

Thread Tools

Re: multi-dimensional search algorithm blues...

Stuart Golodetz
Posts: n/a
"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

> 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

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.



> 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

Reply With Quote
Yu Cao
Posts: n/a
      07-02-2003 Removed) (John Everett) writes:


> 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.

Reply With Quote

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off

Similar Threads
Thread Thread Starter Forum Replies Last Post
Filtered Back Projection Algorithm (FBP Algorithm) Bapaiah Katepalli VHDL 1 06-23-2006 04:50 PM
search within a search within a search - looking for better script times out Abby Lee ASP General 5 08-02-2004 04:01 PM
Article: An Analysis of the Google Search Engine Algorithm Johann Blake ASP .Net 0 01-21-2004 03:21 PM
Key generation algorithm and Cipher algorithm Ahmed Moustafa Java 0 11-15-2003 06:35 AM