Comparing two 1-D waves

Share icon

Wed, 08/07/2013 - 01:01 pm

Whats the most efficient way to search if any of the points on Wave A are on Wave B.
A tolerance of +/-5 needs to be applied.
For instance if wave A has the point 100 and Wave B has the point 105, we consider it as an equality.
To find all of the pairs matching-within-tolerance, it is probably most efficient to sort both waves, then walk through one of the waves while "keeping tabs" on where that value occurs in (the sorted copy of) the other one. Depending on how the tolerance compares to the density of points you may want to
A) keep tabs separately on the first and last points in the second wave within tolerance of the current point in the first wave, or
B) keep tabs on the first point in the second wave that was already too small for the previous point in the first wave, and in a nested loop check the next few points (just one unless there is a match) in the second wave until you find one that is too large.

To just find one match, or if all you need to know is whether there are any, you can swap the roles of the first and second waves every time you find an element that exceeds the lower threshold and avoid some of the comparisons with the upper threshold, but I doubt that's worth it. Similarly, if it is highly likely that there is at least one match, the typical performance might be better if you just sort one of the two waves and then do a binary search for individual points from the second wave until you found one or tried them all. The worst-case performance of this method, however, where you have to try all of the elements of the second wave, is bad enough that you should probably stick with sorting both of them. The big gains if you need just one match or a binary outcome are that you can terminate the loop as soon as you found a match, and you don't need the added complexity of handling multiple matches.

Whether you need multiple matches or one, if one of the waves is much denser than the other, you might benefit from a divide and conquer approach where you do a binary search in the denser wave for the middle value of the less dense wave, and recursively do this with progressively shorter parts of the two waves until the less dense wave is just a point.

August 7, 2013 at 04:40 pm - Permalink

Assuming the waves are of equal number of points, of course:

wave_delta = abs(waveA-waveB)

then run a simple for loop that counts anything below your tolerance level (it could also build a list of point numbers as well if the position is important) on wave_delta.

that will find your points provided you meant their positions were of importance. if you want _any_ point that matches, then sort and findlevel as mentioned already are your friends.

August 8, 2013 at 02:19 am - Permalink

Oh matrixOP, is there anything you cannot do? (literally just started reading that section yesterday)

August 8, 2013 at 11:55 am - Permalink