I have a 150 by 300 binary matrix. I would like to sum the 1's for each individual row (from left to right) until the first zero is encountered. For example, if a given row is 1 1 1 1 1 1 0 0 0 1 0 0 1 1 1, the sum should be 6 (the sum should stop at the first zero and not continue to count the other ones). This operation needs to take place for all 150 rows.

For the sake of argument, we can consider a smaller, simpler matrix to work with (5 by 10).

binarym = ({
{1, 1, 1, 0, 0, 0, 0, 0, 1, 1},
{1, 1, 1, 1, 0, 0, 0, 1, 1, 1},
{1, 1, 0, 0, 0, 0, 1, 1, 1, 1},
{1, 1, 1, 1, 0, 0, 0, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 0, 0, 1, 1}})

Row 1's sum should be 3, row 2's 4, row 3's 2...et.

Thanks in advance for your time.

LengthWhile[#, Positive] & /@ binarym

{3, 4, 2, 4, 6}

Or

binarym /. {x : Longest[1 ..], __} :> Length[{x}]
  • Thank you, works beautifully! – Astrotiff Jul 13 '17 at 22:46
  • 1
    I couldn't believe the efficiency about LengthWhile – yode Jul 13 '17 at 22:50
  • You should specify Length[#] as a third argument to FirstPostion, so it works if there is no 0 in the row. – JEM_Mosig Jul 14 '17 at 0:17
  • Thanks for the hint - even with Length it wouldn't work. I deleted it. – eldo Jul 14 '17 at 0:37
  • 1
    @eldo: Strange. It seems to work with Flatten[FirstPosition[#, 0, Length[#] + 1] & /@ binarym2 - 1] in MMA 11.0.1. – JEM_Mosig Jul 14 '17 at 1:26

Update: ff works as is in version 9. For versions 10+, as commented by @Mr.Wizard, it needs to be modified to prevent the index i from exceeding the length of the input list:

ffX[m_] := With[{n = Length@First@m}, Module[{i = 1}, 
  While[i <= n && Positive[#[[i]]], ++i]; i - 1] & /@ m] (* thanks: @Mr.Wizard *)

Original answer:

ClearAll[f1]
f1 = Module[{i = 1}, While[Positive[#[[i]]], ++i]; i - 1] &;

f1 /@ binarym

{3, 4, 2, 4, 6}

Timings for methods posted so far:

ClearAll[fa, fb, fc, fd, fe, ff]
fa[m_] := First /@ SparseArray[1 - m]["MatrixColumns"] - 1
fb[m_] := LengthWhile[#, Positive] & /@ m
fc[m_] := FirstPosition[#, 0] & /@ m - 1 // Flatten
fd[m_] := Length /@ Map[First, Split /@ m, 1]
fe[m_] := Total@FoldList[Times, #] & /@ m
ff[m_] := Module[{i = 1}, While[Positive[#[[i]]], ++i]; i - 1] & /@ m

data = RandomInteger[1, {150, 300}];
{#, First[RepeatedTiming[#@data;]]}&/@ {fa, fb, fc, fd, fe, ff} // Grid[#, Alignment->"."]&

enter image description here

Except fd all functions produce the same result

Equal@@( # @ data & /@ {fa, fb, fc, fe, ff})

True

and

Equal[fa@data, fd@data]

False

For a larger data set:

data = RandomInteger[1, {10000, 300}];
{#, First[RepeatedTiming[#@data;]]}&/@ {fa, fb, fc, fd, fe, ff} // Grid[#, Alignment->"."]&

enter image description here

Equal@@( # @ data & /@ {fa, fb, fc, fe, ff})

True

  • 1
    Very nice. You might want to Quiet Part::partw. Also While[Positive @ #[[++i]]] is arguably a little cleaner and seems to be as fast. – Mr.Wizard Jul 14 '17 at 1:59
  • Quiet was not such a good idea. The error slows this method by an order of magnitude. I think you should add explicit testing to prevent i exceeding the length of the list. – Mr.Wizard Jul 14 '17 at 14:39
  • Thank you @Mr.Wizard. Updated with the change needed for versions 10+. – kglr Jul 14 '17 at 15:12
  • (1) I believe ff2 has an error; you forgot to map it across m. (2) I think you should move Length outside the loop. (3) Please see my answer below. – Mr.Wizard Jul 14 '17 at 15:20
  • Thank you @Mr.Wizard. Not sure i understand (2), could you please edit my post to fix it? Re (3) amazing but expected:) – kglr Jul 14 '17 at 15:36
First /@ SparseArray[1 - binarym]["MatrixColumns"] - 1

{3, 4, 2, 4, 6}

  • 1
    Pretty! But you have to deal with the case where there are only 1s in one row. – JEM_Mosig Jul 14 '17 at 0:19
  • @JEM_Mosig Pretty reminder.Thanks.. – yode Jul 14 '17 at 0:27

So far the following methods have been proposed:

Leading1sByKglr[m_] := Module[{i = 1}, While[Positive[#[[i]]], ++i]; i - 1] & /@ m

Leading1sByEldoA[m_] := LengthWhile[#, Positive] & /@ m

Leading1sByEldoB[m_] := Flatten[FirstPosition[#, 0] & /@ m - 1]

Leading1sByTomd[m_] := Total@FoldList[Times, #] & /@ m

Leading1sByYode[m_] := First /@ SparseArray[1 - m]["MatrixColumns"] - 1

Leading1sByDavidGStork[m_] := Length /@ Map[First, Split /@ m, 1]

With the test matrix given in the question they all agree.

Equal @@ Through[{
    Leading1sByKglr,
    Leading1sByEldoA,
    Leading1sByEldoB,
    Leading1sByTomd,
    Leading1sByYode,
    Leading1sByDavidGStork
    }[binarym]
  ]
(* True *)

However, when given a full list of only 1s or only 0s, Leading1sByEldoB and Leading1sByYode run into trouble:

binarym2 = {ConstantArray[1, 10], ConstantArray[0, 10]};

Leading1sByEldoB[binarym2]
(* {-1 + Missing["NotFound"], 0} *)

Leading1sByYode[binarym2]
(* {-1 + First[{}], 0} *)

Performance of the remaining methods:

SeedRandom[42];
bigbinarym = RandomInteger[1, {150, 300}];

Through[{
   First@*RepeatedTiming@*Leading1sByKglr,
   First@*RepeatedTiming@*Leading1sByEldoA,
   First@*RepeatedTiming@*Leading1sByTomd,
   First@*RepeatedTiming@*Leading1sByDavidGStork
   }[bigbinarym]
 ] // ScientificForm
(* {8.9*10^(-5), 4.4*10^(-2), 2.1*10^(-3), 9.0*10^(-3)} *)

kglr's method seems to be the best.

 Total@FoldList[Times, #] & /@ binarym

{3, 4, 2, 4, 6}

Just for fun, a pattern-based approach that is very readable

Replace[binarym, {{0, ___} -> 0, {x : (1 ..), 0, ___} :> Length[{x}]}, 1]

Surprisingly, on my machine only kglr's method is faster than this among the ones presented here so far :)

Length /@ Map[First, Split /@ binarym, 1]

(*

{3, 4, 2, 4, 6}

*)

(This assumes the first element is a $1$ in each row.)

  • Thank you! It's nice to see other variations. – Astrotiff Jul 13 '17 at 22:46

It is hard to beat kglr's code but I think I succeeded using IntegerExponent.

len1[m_] := IntegerExponent[FromDigits[Reverse@#, 2] & /@ BitXor[m, 1], 2]

len1[binarym]
{3, 4, 2, 4, 6}

Performance check:

m = RandomChoice[{1, 50} -> Range[0, 1], {150, 300}];
m = ArrayPad[m, {0, {0, 1}}];  (* explained below *)

r1 = ff[m];   // RepeatedTiming   (* kglr's function *)
r2 = len1[m]; // RepeatedTiming
r1 === r2
{0.000914, Null}

{0.000425, Null}

True

Notes:

  • I used ArrayPad to make sure that there is always a zero in each row, as your title implies. If there is not kglr's function as presently written slows down by an order of magnitude due to Part errors, and mine returns for those rows. ArrayPad therefore both keeps the output in agreement and gives kglr's code equal footing.

  • I would like to eliminate Reverse by clever application of binary operations.

  • My function is optimized to work on a packed array, so please make sure input is packed in any performance tests.


Alternate version for additional testing:

len2[m_] := IntegerExponent[BitNot[FromDigits[Reverse@#, 2] & /@ m], 2]
  • It would be interesting comparing the different methods on sparse arrays. – Carl Woll Jul 14 '17 at 17:01
  • 1
    @Carl If the array in SparseArray form to start with I suspect yode's answer or a refinement of it will be fastest as the position information already exists within the data, right? – Mr.Wizard Jul 14 '17 at 22:22

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.