Threshold 1D Array search

[Gary Rubin]

I'm not sure if I'm posting this in the appropriate forum or not...

I use the Threshold 1D Array function quite often. According to the Labview Help description of this function, and based on my experience, it only works for sorted data.

I just did a timing test, comparing the speed of this function to that of the standard sequential array search, and found it to be slower for array lengths of 500, 1000, 2000, and 10000. This tells me that, although the function only works for sorted data, it is using a sequential search, rather than a binary search. Why is this? Can anyone (from NI?) explain why the Threshold 1D Array function was implemented this way?

I guess I'll be spending some time modifying my binary search vi and going back to my code and doing some replacing...

Gary

[peteski]

I'm not sure if I'm posting this in the appropriate forum or not...

I use the Threshold 1D Array function quite often. According to the Labview Help description of this function, and based on my experience, it only works for sorted data.

I just did a timing test, comparing the speed of this function to that of the standard sequential array search, and found it to be slower for array lengths of 500, 1000, 2000, and 10000. This tells me that, although the function only works for sorted data, it is using a sequential search, rather than a binary search. Why is this? Can anyone (from NI?) explain why the Threshold 1D Array function was implemented this way?

I guess I'll be spending some time modifying my binary search vi and going back to my code and doing some replacing...

Gary

Gary,

I've always interpreted the Threshold 1D Array function as more akin to a "Trigger Level", and I think that a binary search would be dangerous as such. In a traditional "signal processing" context, you would want to know the first time the "signal" crossed the threshold, and the only way to be sure of that would be do a sequential search for the "crossing of the threshold".

Now, that having been said, I am somewhat surprised that a basic binary sort isn't a part of the standard labview tools in the array functions. Not that it would be a hard thing to do, at least for any given data type. It could be more "interesting" to do it as a "polymorphic" vi (something I've personally haven't had a need to play with... yet...). Perhaps the Open G guys have produced such a tool?

-Pete Liiva

[Gary Rubin]

I've always interpreted the Threshold 1D Array function as more akin to a "Trigger Level", and I think that a binary search would be dangerous as such. In a traditional "signal processing" context, you would want to know the first time the "signal" crossed the threshold, and the only way to be sure of that would be do a sequential search for the "crossing of the threshold".

I typically use this Threshold 1D Array along with the Interpolate 1D Array to line up data based on asynchronous time stamps. Because I'm using time as my reference array, it's always ascending.

In fact, there's a comment in Labview's help for the Threshold 1D Array function that says:

Note Use this function only with arrays sorted in non-descending order.

This function does not recognize the index of a negative slope crossing, and it might return incorrect data if threshold y is less than the value at start index. Use the Threshold Peak Detector VI for more advanced analysis of arrays.

Is that more along the lines of the usage that you were thinking of?

Gary

[crelf]

...it is using a sequential search, rather than a binary search.

Hmmmm - with large sorted arrays, maybe the best search method would be a dichotomy of some sort? That wouldn't be difficult to implement...

[peteski]

Is that more along the lines of the usage that you were thinking of?

Gary

Gary,

Well, I would agree with you that in your application, a binary search would be far more efficient, especially since your timetag data already comes "pre-sorted" so to speak. In fact your application would be the "poster child" application for exactly a binary search! (especially since they are asynchronous timetags!)

The usage I've applied the 1-d threshold on has been "unsorted" arrays of voltage waveforms from an oscilloscope. In such a case, there is no guarantee that the threshold might be crossed at any particular point in the array, and quite possibly crossed several times. A binary search would trip at the first occurrence it got to, which would not necessarily be the first occurrence in the waveform sequence.

I've actually used this function to get a Full Width, Half Max Pulse Width, by putting a pulse waveform through, having it find the first threshold crossing, then "reversing" the array and finding the negative going threshold, which has now become a "positive" slope via the array reversal.

-Pete Liiva

[Gary Rubin]

In fact your application would be the "poster child" application for exactly a binary search! (especially since they are asynchronous timetags!)

The reason I would use the Threshold function, or a modified binary search, is precisely because the timetags are asynchronous. Say I've got position measurements at 1:30:00 and 1:30:01, and I've got measurement data collected at 1:30:00.2. The binary search would give me either the position at either 1:30:00 or 1:30:01, but what I really want is the interpolated location at 1:30:00.2. Granted, this is a piecewise linear interpolation, and I could do better with higher-order curve fitting, but if I want one unique position point per measurement point, then a standard binary search would not be sufficient.

Am I missing something in your thinking?

Gary

[peteski]

The reason I would use the Threshold function, or a modified binary search, is precisely because the timetags are asynchronous. Say I've got position measurements at 1:30:00 and 1:30:01, and I've got measurement data collected at 1:30:00.2. The binary search would give me either the position at either 1:30:00 or 1:30:01, but what I really want is the interpolated location at 1:30:00.2. Granted, this is a piecewise linear interpolation, and I could do better with higher-order curve fitting, but if I want one unique position point per measurement point, then a standard binary search would not be sufficient.

Am I missing something in your thinking?

Gary

Gary,

No, you are not missing my thinking, I "think" I was missing your thinking. But thats fine, probably about par for the course. I suspect that "piecewise linear interpolation" after a binary search would be as good as anything, and I suspect that a higher order curve fit wouldn't do you much good unless the exact nature of the "asyncronous" timestamping somehow conformed to the higher order curve you decided to use.

Have you checked the Open G stuff to see if they have a binary search? Or the NI website knowledge base?

-Pete Liiva

[Gary Rubin]

Have you checked the Open G stuff to see if they have a binary search? Or the NI website knowledge base?

I think the one I'm using came from NI.

[peteski]

I think the one I'm using came from NI.

I meant a binary search, I know that the 1-D Threshold Array is a NI vi, its been a part of labview for a while. I thought you were looking for a binary search vi.

[Gary Rubin]

I meant a binary search, I know that the 1-D Threshold Array is a NI vi, its been a part of labview for a while. I thought you were looking for a binary search vi.

I've got a binary search VI. I had to modify it to do the interpolation between the two nearest points if the search key is not found.

What I was wondering in the original post was if there was a reason that this the Threshold Array function is not a binary search, given that caveat in Labview Help that the function only works correctly on a sorted array.

Maybe this post would have been appropriate for the Wish List forum, as a suggestion that in future releases, the function could use a binary search.

[peteski]

I've got a binary search VI. I had to modify it to do the interpolation between the two nearest points if the search key is not found.

What I was wondering in the original post was if there was a reason that this the Threshold Array function is not a binary search, given that caveat in Labview Help that the function only works correctly on a sorted array.

Maybe this post would have been appropriate for the Wish List forum, as a suggestion that in future releases, the function could use a binary search.

Gary,

I think that the real problem is that the following wording in the help file is misleading:

Note Use this function only with arrays sorted in non-descending order.

This note seems to imply that the array is supposed to be sorted, which I don't think was the original intension of the vi. The initial description seems to describe the behavior somewhat reasonably:

Compares threshold y to the values in array of numbers or points starting at start index until it finds a pair of consecutive elements such that threshold y is greater than the value of the first element and less than or equal to the value of the second element.

I do agree that a binary search function would be a nice simple addition to labview, especially if they could make it faster by making it native. When you need to do a binary search, you are doing it for speed, and every CPU cycle counts in such a case.

However, I would not agree that the threshold 1-D array should be changed from sequential to binary, unless a choice of search algorthims is added.

-Pete Liiva

[Gary Rubin]

[quote name='peteski' date='Apr 4 2006, 09:10 AM' post='11294'

I think that the real problem is that the following wording in the help file is misleading:

Pete, I would certainly agree. I think that that's where our disconnect has been.

BTW, you mentioned something in one of your other posts about playing ultimate. Do you play in the DC area?

Gary

[peteski]

Gary,

Now we veer way off topic! But who needs those lines anyway!

I play with the Goddard Ultimate Frisbee Club, who play Tuesdays and Thursdays 5:30 to sundown. Its strictly pickup, informal, and the numbers showing up vary between being able to play 3's to just having enough to have 7 on each side. I can only make it out on Tuesdays, at least until June when the kids get out of school, at which point I might have to see what arrangements I can make.

Tuesdays they play at Greenbelt Middle School, and Thursdays at the Goddard Space Flight Center. Its possible for someone to let you on Thursdays, but it requires some coordination to get you in.

Some of the same group play with these people who play pick up on Sundays at Greenbelt Middle School. I would like to get out there more often, but the "Honey Do" list combined with the family obligations list tends to be too long to allow me to get out much on weekends.

-Pete Liiva

[Gary Rubin]

I used to play in WAFC, then in an informal pickup game around the Mall on Sundays. I haven't played for a couple years now -- family obligations, like you said...

Gary

[peteski]

I used to play in WAFC, then in an informal pickup game around the Mall on Sundays. I haven't played for a couple years now -- family obligations, like you said...

Gary

Yeah, I have to fight negotiate the times I get out. Sign of growing old, I suppose.

-Pete Liiva

[torekp]

QUOTE(Gary Rubin @ Apr 4 2006, 02:18 AM)

I've got a binary search VI. I had to modify it to do the interpolation between the two nearest points if the search key is not found.

Gary, could you please post this binary search VI?

[Gary Rubin]

QUOTE(torekp @ Jul 13 2007, 08:18 AM)

Gary, could you please post this binary search VI?

Paul, Are you asking for the plain binary search, or my modified one with the interpolation at the end?

EDIT: I've not been able to find my modified one, so here's the standard binary search. The modification was pretty simple - if the key is not found, lookup the array values associated with the upper and lower indices (upper will be smaller than lower), and interpolate between them.

[torekp]

QUOTE(Gary Rubin @ Jul 13 2007, 01:24 PM)

here's the standard binary search. The modification was pretty simple -

Beautiful, thanks. Just what I wanted. :thumbup: This goes straight into my re-use code folder.