Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

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
> Graduate program in Biochemistry



 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
 
 
Reply

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



Advertisments