From: Joel VanderWerf <vjoel@...>
Date: 2002-09-20T05:43:27+09:00
Subject: Re: How to Efficiently Calculate the Pattern of Zeros and Ones?

Johan Holmberg wrote:
> William Djaja Tjokroaminata <billtj@z.glue.umd.edu> writes:
> 
>>For example, with m = 2:
>>
>>    [1 0 0 1 0 0 5 1]   --> 2
>>    [0 0 1 0 0 1 0 2]   --> 1
>>    [1 0 1 0 1 0 1 0]   --> 0
>>    [1 0 0 0 0 0 1 0]   --> 2
>>
> 
> 
> I don't know if the following is efficient in terms of CPU-cylces
> but it is at least rather short and easy to read (once you know
> the cool enum-package).
> 

I had to go back and check whether each_with_neighbors generated lots of 
arrays or not. It turns out that it doesn't. Instead, it keeps a single 
array, shifts data through it, and yields the array. So it should be 
fairly efficient as pure ruby code goes.

However, this may surprise users who modify the array in the iterator 
block, so I'll slip a warning into the docs.

If your rows are short, each_with_neighbors is not very efficient 
because of the "warm up" and "cool down" to deal with the cases near the 
edge.

> /Johan Holmberg
> 
> #----------------------------------------------------------------------
> require "enum/cluster"
> 
> lists = [
>     [1, 0, 0, 1, 0, 0, 5, 1],
>     [0, 0, 1, 0, 0, 1, 0, 2],
>     [1, 0, 1, 0, 1, 0, 1, 0],
>     [1, 0, 0, 0, 0, 0, 1, 0],
> ]
> 
> facit = [0, 0, 1, 0, 0]
> m = 2
> 
> for list in lists
>     count = 0
>     list.each_with_neighbors(m, 0) do |part|
>         count += 1 if part == facit
>     end
>     puts "# in #{list.inspect} = #{count}"
> end
> #----------------------------------------------------------------------

Nice!

If the requrements were different, and 1's near the edge were not to be 
counted because there are not enough zeros, you could replace

 >     list.each_with_neighbors(m, 0) do |part|

with
       list.each_cluster(m*2+1) do |part|