LabVIEW
Search Sorted Array Incorrect Output
Solved!
So I'm trying to optimize some of my code and I'm digging into some of the sorted Array functions introduced in recent LabVIEW versions. But it seems I have either a bug, or I don't understand what "Nearest Index" is supposed to mean. Attached is a VI where I search for the letter "q" in an array.
So why when I search for this does it return the index associated with the second match? How can I have it return the first found index matching the search element? Do I need to use a while loop, searching backwards from the nearest index value, until a match isn't found? This makes this search function much less useful if that is the case.
Because it triggers this case:
It does a quick check near the start to see if the searched item is the last item and if so just returns that immediately.
I see. Well then I'm just going to have to make this function useful for something other then being a glorified Set finding function. Attached is my improvements which now return the first Index, as well as the Length of the found element. This will likely make it into my Array VIMs package eventually.
I think you would need to significantly improve the efficiency to keep the O(logN) performance. Your code can easily turn into a O(N). For example if you have an array consisting of hundreds of millions identical elements and you are searching for that same value, it would need to inspect every single element to come up with the solution.
Your code is OK if we can assume that typical stretches of identical elements are short. But can we, really?
I think it would be easily to do some binary bracketing in each direction instead. We know the boundaries from the binary search and can half the interval with each comparison.
You would also want to retain and implement the "less" function input of the stock VIM.
@altenbach wrote:
For example if you have an array consisting of hundreds of millions identical elements and you are searching for that same value, it would need to inspect every single element to come up with the solution.
The types of data you deal with, and the types of data I deal with are clearly very different. I'm typically dealing with an array of a hundred elements or so, maybe a thousand. The amount of duplicates are very small. But I do see your point that there are optimizations that can take place. As far as I see it this is a huge improvement over the old method of dealing with the Search 1D primitive, in a while loop, on an unsorted array. I don't intend on improving performance of this more then it is at the moment.
I'm working on improving my Array VIMs package performance, and I'll be posting an update on LAVA for others to comment on before posting it on VIPM.IO. I just need a little more time to finish updating the other functions.
One minor suggestion would be to use FOR loops (with conditional terminals) , eliminating the need to constantly compare loop counts. Instead of all the fancy final math, I think you could get the final results easier using the output of the blue shift registers.
Great suggestion, and one I can implement quickly. Attached is v2 with this change, along with an icon that is at least unique from the default binary search.
Can't do the performance testing because I don't use any VIPM tools 😄
This particular VI would probably deserves to eliminate the use of the stock VI and implement it's own binary search. Some of the intermediary outputs from the binary can be used to further bracket the results.
I'll have a look, but it's a bit of a hairball with plenty of "off by one" landmines if we are not careful. 😄
I also wonder if it would be more reasonable to output the "nearest index" (from the stock VIM) if the element is not found (instead of -1), but then still set the length to zero and "not found" to true. "nearest index" is more informative because it e.g. tells if we are at least in-range or low/high. Also, for e.g. DBLs the nearest result might still be pretty good if if we are e.g. only off by epsilon.
