LabVIEW

cancel
Showing results for 
Search instead for 
Did you mean: 

Design challenge: find biggest block of true in boolean array


@altenbach wrote:

@smercurio_fc wrote:

Gerd's solution has a very slight error in calculating the size of the block. Missing a +1.

 

Here's another variation. Runs about the same as the others in terms of speed.


I would probably only keep the largest size and it's index in a shift register. building large arrays at the loop boundary just to later throw away everything except one element each seems expensive.


Then you have, essentially, Gerd's solution. However, keep in mind that the variant I showed is not creating a large array. The question lacked certain operating parameters, so certain assumptions were made. The key underlying assumption that I made, based on the general premise of the question, is that the number of contiguous "blocks" would be small compared the number of elements in the array. In the example provided, there's only 3 blocks (if I remember correctly), so the array that is created is 3 elements. 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.

0 Kudos
Message 11 of 37
(916 Views)

I wasn't clear on the operating parameters.

It's true that I'm expecting all arrays to only have a small number of true blocks compared to the total number of elements, hence the example array with four blocks.

Actually I'm also expecting the blocks to be in rather close vicinity to each other with the majority of the array filled with "false". I can't predict where in the array (beginning, middle, end) the blocks will be.

I do however guess that does not allow for any optimizations.

 

Thanks for keeping it coming.

 

Regards Florian

0 Kudos
Message 12 of 37
(907 Views)

Sorry i was posting by phone. I only saw "thousands of arrays with millions of elements each". I did not really look at the other solutions.

0 Kudos
Message 13 of 37
(906 Views)

Florian.Ludwig wrote:

you are of cause right smercurio. That's exactly the reason why I expected my second approach and JW-L3CE's to be slower.

 

Regards Florian



Yeah, I didn't think I would beat LabVIEW's greatest. I went for simple and outside-the-box (and ended with a CPU memory hog)

 

Funny note: Mine is faster on my machine when you replace the array with:

Alternating array.png

... but changing the parameters of the competition to purposefully hinder someone elses design is cheating. Hehe, I conceed.

Josh
Software is never really finished, it's just an acceptable level of broken
0 Kudos
Message 14 of 37
(896 Views)

@Florian.Ludwig wrote:

I was hoping for some "trick" though Smiley Wink

altenbach? Smiley Happy


Using your benchmark, this seems to be about 15-20x faster than the rest. 😄

 

Please verify for correct operation.

 

 

 

Message 15 of 37
(881 Views)

You might want to double check your benchmark setup, I think you forget to repeat the test "Numerisch" times. On my computer it's about 5 times slower then the next best. But if I only run your only once it appears about 20 times faster (Numerisch is equal to 100).

0 Kudos
Message 16 of 37
(858 Views)

.Yes, I did not notice the outer loop. 😞

0 Kudos
Message 17 of 37
(857 Views)

Here it is



Mark Yedinak
Certified LabVIEW Architect
LabVIEW Champion

"Does anyone know where the love of God goes when the waves turn the minutes to hours?"
Wreck of the Edmund Fitzgerald - Gordon Lightfoot
0 Kudos
Message 18 of 37
(826 Views)

Mark, I think you posted in the wrong thread. (Right place)

0 Kudos
Message 19 of 37
(821 Views)

Oops. Yes I did. The downside of switching displays between different computers.



Mark Yedinak
Certified LabVIEW Architect
LabVIEW Champion

"Does anyone know where the love of God goes when the waves turn the minutes to hours?"
Wreck of the Edmund Fitzgerald - Gordon Lightfoot
0 Kudos
Message 20 of 37
(816 Views)