Mini Coding Challenge - Binary Search (sort of)

[altenbach]

Yes, both work fine in 2015 and are about the same speed (~too fast to measure reliably!) Times are heavily quantized to a few values (e.g. 400, 800, 1200ns) and if the input is incorrect (e.g. if the first element is zero), it is still not really faster, meaning the loops are about the same speed as an empty case structure. 😄

I changed the array to a cluster containing a single U8 element to be able to test 100M size arrays, and it is still <2us (generating the data however takes 20s! :D) (this is on my old Laptop).

(Mine was actually slightly slower initially, mostly because of using a loop for the 1,4 pre-test. Apparently the compiler does not unroll that simple 2-iteration loop and thus adds some overhead. I tweaked a few other things, but we seem to be near the speed of light. :D)

(Of course to test the GregS code I had to open the vim in 2018 and down-convert to 2015 (where the rest of the code was open). Dumb question: When down-converting (save for previous) a "vim" from 2018 to 2015, why doesn't it rename the extension to "vi"?? A vim extension is not recognized in LabVIEW 2015 and trying to open it by browsing to the folder from within LabVIEW, it only showed an empty folder :()

[Darren]

---

@altenbach wrote:

Dumb question: When down-converting (save for previous) a "vim" from 2018 to 2015, why doesn't it rename the extension to "vi"?? 

---

Not a dumb question, that's a perfectly reasonable thing to expect. I'm guessing SFP doesn't currently have the facility to rename files. On the bright side, if you change the browse options to *.*, you should be able to open the .vim in 2015, since the file format of .vim and .vi are identical.

[altenbach]

---

@Darren wrote:

---

On the bright side, if you change the browse options to *.*, you should be able to open the .vim in 2015, since the file format of .vim and .vi are identical.

---

Thanks. Yes, I worked around it. Was initially baffled by the (apparently) empty folder and thought that no output was created at all 😄

As you probably noticed, I spend 90% of my efforts creating a reliable test harness to make sure it works under pathological inputs (2 or 3 missing, mostly 4s, etc.). Since I have it, why not share it. Here's my latest version, directly comparing GregS and my code (I also fixed some mislabeling and got rid of that ugly orange. :D) I also clear indicators when called to avoid staring at stale results. (LV 2018 now)

On my AMD Ryzen 1700x, I get submicrosecond times for 100M inputs. Seems fast enough 😄

[Darren]

I talked to Stephen about the SFP and .vim thing. He said he would look into it, but pointed out that currently there is 0% chance of name collisions when using SFP. That would not be the case here, as it is conceivable that your SFP operation may be handling both abc.vim and abc.vi, in which case we would *not* want to save abc.vim as abc.vi. So it's not a "slam dunk" change, as he put it. 

[altenbach]

---

@Darren wrote:

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.

---

Here's my slow (very, very slow!) solution using "search array" in a relatively efficient way. Takes about 450ms for 100M, or about 500000x (!!!) slower than the binary search as expected. 😄 (O(N) vs. O(logN) hurts as N gets large. :D)

[GregSands]

---

@Darren wrote:

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.

---

Yes I did the same to test it as well.  It was interesting to see it selected the "right" element of the cluster even though the name was different - I presume that is just because both were the first element.

---

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.

---

Would love to, unfortunately the trip from New Zealand is a bit far, and working at a university means it's hard to make a good case to go.

[GregSands]

---

@altenbach wrote:
Here's my latest version, directly comparing GregS and my code

---

Nice to see you even took the time to suggest code improvements - thanks.  It shows in one snapshot the difference between a CLA and a lowly pleb programmer...

[altenbach]

---

@GregSands wrote:
t shows in one snapshot the difference between a CLA and a lowly pleb programmer...

---

There were just minor notes mostly for myself. Did not actually make changes in order not to accidentally break or change anything (and out of respect). 😉

OTOH, I am not even pretending to be a CLA, though. 😄