Design challenge: find biggest block of true in boolean array

[Matt_W1]

Since I can't bypass the cost of range checking in LabVIEW I couldn't make the skipping algorithm always faster than the basic one. So I had it switch from basic to switching when it performed better on my computer.

With the example data mine is 175ms ms vs 304 ms of the next best. It should be about equal the current best posted algorithm in the worst case, and much (10x+) faster in better cases. I didn't test it really thoroughly so there could be errors in it.

[smercurio_fc]

---

@matt W wrote:

Since I can't bypass the cost of range checking in LabVIEW I couldn't make the skipping algorithm always faster than the basic one. So I had it switch from basic to switching when it performed better on my computer.

With the example data mine is 175ms ms vs 304 ms of the next best. It should be about equal the current best posted algorithm in the worst case, and much (10x+) faster in better cases. I didn't test it really thoroughly so there could be errors in it.

---

I was unable to replicate these times. I did note that you made some explicit run-time changes to the VI:

• You made the VI reentrant.
• You disallowed debugging

These are going to skew the results, not allowing you to compare apples to apples.

[ben64]

Surely not the most efficient, just having fun discovering the PtByPt functions!

Ben64

[altenbach]

---

@smercurio_fc wrote:

At the worst case the input array has an alternating pattern of ones and zeros. I suspect, though, that the likelyhood of this is extremely remote.

---

Your VI does not correctly handle edge cases, for example if the array only contains FALSE, Your size will be 1, which should be zero.

You are also doing the "<0" twice on the same value, but I suspect that the compiler will eliminate one of these comparisons.

[Matt_W1]

While mine slows down if you turn those options off (since mine's speed is dependent on being inline). The other two I'm comparing against do not gain anything even though they have been placed into similiar functions (so it is apples to apples).

I attached the testing code I used and a screenshot of my results. It's possible I'm missing something so let me know if you have an idea on the source of our performance discrepency. I'm running on 2011sp1.

[altenbach]

Matt, you code gets stuck forever in the first loop if there is a single TRUE surrounded by FALSE somewhere. Needs some tweaks. 😉

[Matt_W1]

Opps kinda of hacked together the first part. Looks like my sloppyness caught up to me.

I attached a hopefully working version, now I get 160ms with the sample data so it's faster too.

Edit (Adjusted the mode switching length to 5 since that's now the better time)

[smercurio_fc]

---

@altenbach wrote:

---

@smercurio_fc wrote:

At the worst case the input array has an alternating pattern of ones and zeros. I suspect, though, that the likelyhood of this is extremely remote.

---

Your VI does not correctly handle edge cases, for example if the array only contains FALSE, Your size will be 1, which should be zero.

---

Yeah, I knew about that but I didn't really care too much since I believe the other output would be -1, providing an indication if something was actually found. Obviously, this could be embedded inside if the code is made into a subVI.

---

You are also doing the "<0" twice on the same value, but I suspect that the compiler will eliminate one of these comparisons.

---

I'm not sure I understand. It's comparing the two different index outputs. How can they be the same (unless they both come out to be -1)?

[altenbach]

---

smercurio_fc wrote:

I'm not sure I understand. It's comparing the two different index outputs. How can they be the same (unless they both come out to be -1)?

---

Look for the red text..... 😉

 

[Florian.Ludwig]

Good morning from Germany,

you sure were busy while I was sleeping!

As I was looking for a better implementation than mine, I just tested code against code.

I am aware that in my final application disabling debugging and inlining the sub vi are going to get rid of some sub vi overhead - in my use case that's valuable (lots of sub vi calls).

It is good things like that are mentioned here - I learned a lot from threads like this one.

I just copy/pasted Matt's code into my benchmark (still comparing only code, no sub vis - the diagram is getting really ugly, kids don't do this at home )

2,63 ms vs. 2,08 ms (from both GerdW and smercurio)

Regards Florian