Design challenge: find biggest block of true in boolean array

[smercurio_fc]

---

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

[Florian.Ludwig]

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

[altenbach]

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.

[JW-JnJ]

---

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:

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

[altenbach]

---

@Florian.Ludwig wrote:

I was hoping for some "trick" though

altenbach?

---

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

Please verify for correct operation.

 

[Matt_W1]

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

[altenbach]

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

[Mark_Yedinak]

Here it is

[altenbach]

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

[Mark_Yedinak]

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