LabVIEW

cancel
Showing results for 
Search instead for 
Did you mean: 

Design challenge: find biggest block of true in boolean array

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.

0 Kudos
Message 21 of 37
(688 Views)

@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.

0 Kudos
Message 22 of 37
(674 Views)

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

 

Ben64

 

Biggest block of TRUE.png

0 Kudos
Message 23 of 37
(669 Views)

@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.

0 Kudos
Message 24 of 37
(652 Views)

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.

 

tester results.PNG

0 Kudos
Message 25 of 37
(648 Views)

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

0 Kudos
Message 26 of 37
(648 Views)

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)

Message 27 of 37
(642 Views)

@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)?

0 Kudos
Message 28 of 37
(623 Views)

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..... 😉

 

 

0 Kudos
Message 29 of 37
(618 Views)

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 Smiley Wink)

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

 

Regards Florian

0 Kudos
Message 30 of 37
(597 Views)