topic Re: Mini Coding Challenge - Binary Search (sort of) in BreakPoint

Mini Coding Challenge - Binary Search (sort of)

Darren — Tue, 13 Nov 2018 04:22:40 GMT

I have a large cluster array. Many millions of elements. There is a field in the cluster that is a number. That number could be 0, 1, 2, 3, or 4. This value is guaranteed to be in ascending order throughout the entire cluster array. So here are some possible values for that field for the entire array:

0, 0, 0, ... 0

4, 4, 4, ... 4

1, 1, ... 1, 2, 2, 4, 4, ... 4

0, 1, 2, 3, 4 ... 4

0, 0, 0, ... 1, 1, 1... 2, 2, 2... 3, 3, 3... 4, 4, 4

1, 1, 1, ... 2, 2, 2, ... 3, 3, 3, ... 4, 4, 4

I am trying to look for the scenario that is bolded above...in other words, I want to know if the values for that numeric field in that array start at 1, at some point transition to 2, at some point transition to 3, then at some point transition to 4. The number of times each value occurs between those transitions does not matter. Some restrictions I have:

No brute forcing the array...I need to iterate as few times as possible.
No parallel For Loop.

It's easy to check if the first cluster element is '1' and the last one is '4', but once I get that far, I'm getting wrapped around the axle with a binary search that goes in two directions looking for two values. I've got something that sorta works but I bet y'all can come up with something better. Best solution wins a high five from me and a shout-out in whatever NIWeek presentation(s) I give in 2019.

Re: Mini Coding Challenge - Binary Search (sort of)

JB — Tue, 13 Nov 2018 08:15:22 GMT

Would this be too slow ?

Re: Mini Coding Challenge - Binary Search (sort of)

altenbach — Tue, 13 Nov 2018 09:13:21 GMT

It would help if you could define the problem in LabVIEW terms, e.g. by attaching a simplified VI that contains the correct datatype.

If I understand this correctly, the array element of a 1D array is a cluster of many completely uninteresting elements of any datatype, but one cluster element is a numeric (U8? I32?) that is guaranteed to only contain one of five values (0..4) AND is guaranteed to be in nondescending order and that's the only one we are looking at. (You say "guaranteed to be ascending" but your examples claim otherwise)

The result for any given input array is a boolean, either PASS (containing only 1, 2, 3, 4) of FAIL (otherwise). You already suggested an algorithm that checks the first and last for the correct values (1, 3, resp) and then only needs to prove that 2 and 3 also exist. I think you can do a single binary search for "2" OR "3" and once you find one (stop now and return FAIL if none are found, of course!), do a second binary search for the other (= not yet found) value on the remaining range above or below it, depending on what you found (i.e. if you found a 2, search above for 3, if you found a 3, search below for 2, re-using and readjusting the bounds already established). If the second value is not found, return FAIL, else it's a PASS as soon as you find one of them.

(Just thinking out loud, need to go to sleep now :D)

Re: Mini Coding Challenge - Binary Search (sort of)

JB — Tue, 13 Nov 2018 10:40:45 GMT

According to Altenbach's post, I didn't fullly understand the task. I thought that it is needed to know the indexes of the transitions. Furthemore the code is really not optimized and does nothing more than this :

Result is OK if all values (1 to 4) exist in the array. Is this correct ?

If so, because the values are ordered :

- first element must be 1 and last 4

- check if 2 and 3 exist by the use of Search 1D Array

Would this be an acceptable solution ? This is so simple that I'm afraid to miss something obvious.

Re: Mini Coding Challenge - Binary Search (sort of)

Darren — Tue, 13 Nov 2018 16:27:08 GMT

@altenbach wrote:

It would help if you could define the problem in LabVIEW terms...

I thought I did. 😉 Big array of clusters, one field is a number, values are in ascending order, tell me if those values transition between 1, 2, 3, and 4.

@altenbach wrote:

(You say "guaranteed to be ascending" but your examples claim otherwise)

Which example is an exception? All of them have values in ascending order. Some only have one value. Some have values ascending but skip something.

@altenbach wrote:

The result for any given input array is a boolean, either PASS (containing only 1, 2, 3, 4) of FAIL (otherwise). You already suggested an algorithm that checks the first and last for the correct values (1, 3, resp) and then only needs to prove that 2 and 3 also exist. I think you can do a single binary search for "2" OR "3" and once you find one (stop now and return FAIL if none are found, of course!), do a second binary search for the other (= not yet found) value on the remaining range above or below it, depending on what you found (i.e. if you found a 2, search above for 3, if you found a 3, search below for 2, re-using and readjusting the bounds already established). If the second value is not found, return FAIL, else it's a PASS as soon as you find one of them.

Yup, that's what I need to do. And that's pretty much what I have right now. But this approach requires two passes. I was hoping somebody more clever than me could figure out a way to do it in one pass.

Re: Mini Coding Challenge - Binary Search (sort of)

altenbach — Tue, 13 Nov 2018 16:54:02 GMT

@Darren wrote:

Which example is an exception? All of them have values in ascending order. Some only have one value. Some have values ascending but skip something.

In all your example the value sometimes stays the same between adjacent elements, i.e. is not ascending but still nondescending. 😄 The "ascending" condition is not met. (see also). Your sentence probably would have worked better after including one word as in "... these values are guaranteed to be sorted in ascending order ...".

@Darren wrote:

Yup, that's what I need to do. And that's pretty much what I have right now. But this approach requires two passes. I was hoping somebody more clever than me could figure out a way to do it in one pass.

It really is only one pass, because the ranges are not overlapping. The second search is entirely in a region that has not been looked at before. We just need to slightly switch logic as a function of what has been found so far. The quickly shrinking search boundaries continue to shrink, only the logic is swapped. At most, we need to inspect log2(N) elements, .i.e. about 24 for an array with 16M elements. That's peanuts. 😄

Re: Mini Coding Challenge - Binary Search (sort of)

JB — Tue, 13 Nov 2018 17:13:22 GMT

Doesn't this meet your requirements ? Is it not efficient enough ?

I didn't make a benchmark to check if it would be faster to start the search of 3 at the index of 2.

Re: Mini Coding Challenge - Binary Search (sort of)

JB — Tue, 13 Nov 2018 17:26:04 GMT

On my quite old machine, check if sorted disabled : 5ms for an array with 10M values and 47ms with 100M.

Re: Mini Coding Challenge - Binary Search (sort of)

Hooovahh — Tue, 13 Nov 2018 17:52:49 GMT

@JB I like it. You could use the delete from array to get the last element, at one point that was more efficient. Also I think an improvement could be to start the 2 Search at index 1, and start the 3 search at the index 2 was found +1, but only if 1 and 2 were found properly. If they aren't then we don't need to search for 3.

Re: Mini Coding Challenge - Binary Search (sort of)

Darren — Tue, 13 Nov 2018 18:00:12 GMT

@JB wrote:

Doesn't this meet your requirements ?

I'm dealing with an array of clusters, not an array of numbers. So the array primitives (including Search) won't help.

Re: Mini Coding Challenge - Binary Search (sort of)

altenbach — Tue, 13 Nov 2018 18:14:49 GMT

You can't use search array or sort array, because you are only interested in one particular cluster element. If this is just an integer array, you are still far from optimal. Search is linear and needs to inspect millions of values. If the 1-4 check fails, there is no need for any search. If 2 is not found, there is no need to search for 3.

If 2 is found, that would be used as the start index for the 3 search. I am sure my suggestion is many orders of magnitude faster. (Currently on the bus. Will try something later ... You never need to inspect more than a few dozen elements to solve)

Re: Mini Coding Challenge - Binary Search (sort of)

altenbach — Tue, 13 Nov 2018 18:33:24 GMT

I would suggest a more generic formulation of the problem to make it more reusable.

"Given a array of clusters containing an integer element that is non-descending, determine if all possible integer values between the values of the first and last array element are present."

Maybe for another time... 🙂

Re: Mini Coding Challenge - Binary Search (sort of)

Hooovahh — Tue, 13 Nov 2018 19:54:52 GMT

Alright array of cluster. 1 and 4 still checked the same, 2 and 3 checking each element. Is it possible to pull the cluster elements out efficiently and then use search 1D array? I get that looking at each element when there are millions can be slow, and this is brute forcing the array.

Re: Mini Coding Challenge - Binary Search (sort of)

Darren — Tue, 13 Nov 2018 19:58:22 GMT

This approach would work, but if the numeric values look like this:

1, 1, 1, .... 1, 2, 3, 4

...then we have to go through the entire array to find out it's legit. I need a solution that looks like a binary search, that goes through the array as efficiently as possible.

Re: Mini Coding Challenge - Binary Search (sort of)

Hooovahh — Tue, 13 Nov 2018 20:24:58 GMT

Sorry it took two pages of replies to finally show me what you are trying to do. Yeah I think an intelligent binary search could be performed.

Do we have some real world data to try the normal approach with first? Is the non binary search fast enough with real world data? I just tested with 10M values and worst case (like you showed) took around 70ms, 100M took around 700ms. Maybe cluster complexity increases the time needed?

Re: Mini Coding Challenge - Binary Search (sort of)

Darren — Tue, 13 Nov 2018 20:28:51 GMT

Sorry I keep moving the goalposts. The array of clusters is the easiest way conceptually to present the coding challenge. In reality, it's not exactly an array of clusters. Suffice to say that the binary search will definitely result in time savings much greater than an order of milliseconds. But whatever "binary search with logic to handle looking for two things" answer y'all come up with should be translatable to the situation I'm dealing with. 🙂

Re: Mini Coding Challenge - Binary Search (sort of)

altenbach — Tue, 13 Nov 2018 22:17:07 GMT

Here's a quick draft (LabVIEW 2015). A few microseconds (1-3us) for 10M million elements of an array containing a cluster with the "interesting number", three other random DBLs and a short string.

(Sorry, the data generator ran out of memory for 100M but the analysis should still be in the low microseconds. We need to simplify the cluster for larger sizes...)

(Some things could be tweaked and there might be edge cases that need to be addressed. No failure for Size=1k and >1M trials: looks promising....:) The innermost case could also be wired directly to the number with one case "2" and the other "default"))

(Note that the data generation is significantly slower that the validity check. It takes about 10s to generate the 10M array ... 🐵

Re: Mini Coding Challenge - Binary Search (sort of)

GregSands — Tue, 13 Nov 2018 23:33:27 GMT

My implementation (LV2018) is very similar to CA's except I used an enum to track progress.

Re: Mini Coding Challenge - Binary Search (sort of)

altenbach — Wed, 14 Nov 2018 00:39:41 GMT

@GregSands wrote:

My implementation (LV2018) is very similar to CA's except I used an enum to track progress.

I haven't tested yours because my data input structures are different, but one thing to remember is that any case structure with more than two cases is measurably slower than a case structures with only two cases. Your stack of case structures has 15 possible paths while mine only has four possible paths. (Yes, my outer case has 3 cases, but the code is so fast it does not really matter).

I am curious what the performance would be.

Re: Mini Coding Challenge - Binary Search (sort of)

Darren — Wed, 14 Nov 2018 04:41:25 GMT

Christian and GregS, y'all rock! Your algorithms both work well for my situation. Y'all brought my processing time down from ~1 sec to 0.003 sec. GregS, since you conveniently posted a .vim, I just dropped it into Christian's benchmark VI to test its speed and functionality.

Y'all both get shout-outs at NIWeek 2019. Christian gets a high five too since I know he'll be there. Greg gets one too if he shows up.