count consecutive 1s

[Roger|Dyalog]

Interesting puzzle from Joe Bogner on the J Programming Forum:

This is probably easy but I can't figure it out. How can I count the number of consecutive 1s?

Another way to think about it is a running sum that resets upon hitting a zero

Code: Select all

input=:    1 0 1 1 1 1 0 1
expected=: 1 0 1 2 3 4 0 1


[DanB|Dyalog]

Isn't this a "partitioned plus scan"?
This fn in trad APL would do:

Code: Select all

     ∇ z←a pPls b
[1]   ⍝ Partitioned PLus Scan
[2]    z←+\b-a\z-¯1↓0,z←a/+\¯1↓0,b
     ∇


but if you want this as a train this is different.

[Roger|Dyalog]

Indeed it can be a partitioned plus scan. However, to use the pPls function it's a hassle to figure out the partition vector (the left argument a). The following is what I came up with, translated from J to APL:

Code: Select all

      x
1 1 1 1 0 1 0 0 0 0 1 0 1 1 1
      ⎕←s←+\x
1 2 3 4 4 5 5 5 5 5 6 6 7 8 9
      (~x)×s
0 0 0 0 4 0 5 5 5 5 0 6 0 0 0
      ⌈\(~x)×s
0 0 0 0 4 4 5 5 5 5 5 6 6 6 6
      s - ⌈\(~x)×s
1 2 3 4 0 1 0 0 0 0 1 0 1 2 3
      x
1 1 1 1 0 1 0 0 0 0 1 0 1 1 1


Therefore, my answer is

Code: Select all

{s-⌈\(~⍵)×s←+\⍵}


[Phil Last]

      dfn ← {s-⌈\(~⍵)×s←+\⍵}
      train←(~(⊢-(⌈\⊣×⊢))+\)
      )copy dfns cmpx
C:\Program Files\Dyalog\Dyalog APL-64 14.0 Unicode\ws\dfns saved Sat Jun 28 08:57:24 2014
      arg← 1 1 1 1 0 1 0 0 0 0 1 0 1 1 1
      cmpx 'dfn arg' 'train arg'
  dfn arg   → 1.9E¯6 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  train arg → 1.4E¯6 | -24% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

[Roger|Dyalog]

I am curious why you wrote ... ⊣×⊢ instead of the equivalent ×.

Your timings are consistent with training experience from APL and from J. Until the compiler efforts of Jay Foad and others bear fruit, trains have lower interpretative overhead than ordinary expressions, including D-functions and D-operators. This lower interpretative overhead reveals itself in benchmarks on small arguments, because on such arguments interpretative overhead is relatively more important. Thus:

Code: Select all

      dfn    ← {s-⌈\(~⍵)×s←+\⍵}
      train  ← ~ (⊢-(⌈\⊣×⊢))+\
      train1 ← ~ (⊢-(⌈\×))+\

      x← 1 1 1 1 0 1 0 0 0 0 1 0 1 1 1  ⍝ small argument

      cmpx 'dfn x' 'train x' 'train1 x'
  dfn x    → 1.81E¯6 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  train x  → 1.50E¯6 | -18% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕       
  train1 x → 1.37E¯6 | -25% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕         

      x←0≠?1e6⍴4  ⍝ large argument

      cmpx 'dfn x' 'train x' 'train1 x'
  dfn x    → 4.01E¯3 |  0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  train x  → 3.99E¯3 | -1% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  train1 x → 4.01E¯3 | -1% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕


Another function:

Code: Select all

      avgdfn   ← {(+⌿⍵)÷≢⍵}
      avgtrain ← +⌿÷≢

      x←?10⍴0   ⍝ small argument
      cmpx 'avgdfn x' 'avgtrain x'
  avgdfn x   → 9.62E¯7 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  avgtrain x → 6.35E¯7 | -34% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕             

      x←?1e6⍴0  ⍝ large argument
      cmpx 'avgdfn x' 'avgtrain x'
  avgdfn x   → 1.06E¯3 |  0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  avgtrain x → 1.06E¯3 | -1% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕


There are various reasons for writing a computation as a train, or against writing it as such. Performance should not be one of these reasons. For the above two problems, I myself would write {s-⌈\(~⍵)×s←+\⍵} and +⌿÷≢.

[Phil Last]

In regard to

      train ← ~(⊢-(⌈\⊣×⊢))+\

I am curious why you wrote ... ⊣×⊢ instead of the equivalent ×.

I can only say that in my experience any algorithm is the result of a certain distillation of ideas over time. The dfn assigned and reused s. My normal mode of working with dfns would have been to look for a way to substitute the value with an argument as ⍺, ⍵, ⍺⍺ or ⍵⍵. Dan's comment spurred me into looking for a train instead.
An earlier version had

      (+\-(⌈\~×+\))

with two instances of +\. Fork affords the reuse of the arguments for both left and right tines. The left use of +\ remains as ⊢ even in your shorter version. I left it in both positions. Once it worked and wasn't longer than the dfn I felt I'd spent enough time on it.
I guess eventually I should have remembered the page in my notebook that has

      ⊣f⊢ ←→ f⍨⍨

squeezed in a corner between an unknown phone number and a shopping list. (Almost certainly while walking next to water but that's another story.)