9
$\begingroup$

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.

Improve this question
$\endgroup$
1

8 Answers 8

Reset to default
9
$\begingroup$ 
LengthWhile[#, Positive] & /@ binarym

{3, 4, 2, 4, 6}

Or

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

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

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Very nice. You might want to Quiet Part::partw. Also While[Positive @ #[[++i]]] is arguably a little cleaner and seems to be as fast. $\endgroup$
    – Mr.Wizard
    Jul 14, 2017 at 1:59
  • $\begingroup$ 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. $\endgroup$
    – Mr.Wizard
    Jul 14, 2017 at 14:39
  • $\begingroup$ Thank you @Mr.Wizard. Updated with the change needed for versions 10+. $\endgroup$
    – kglr
    Jul 14, 2017 at 15:12
  • $\begingroup$ (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. $\endgroup$
    – Mr.Wizard
    Jul 14, 2017 at 15:20
  • $\begingroup$ Thank you @Mr.Wizard. Not sure i understand (2), could you please edit my post to fix it? Re (3) amazing but expected:) $\endgroup$
    – kglr
    Jul 14, 2017 at 15:36
7
$\begingroup$ 
First /@ SparseArray[1 - binarym]["MatrixColumns"] - 1

{3, 4, 2, 4, 6}

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Pretty! But you have to deal with the case where there are only 1s in one row. $\endgroup$
    – JEM_Mosig
    Jul 14, 2017 at 0:19
  • $\begingroup$ @JEM_Mosig Pretty reminder.Thanks.. $\endgroup$
    – yode
    Jul 14, 2017 at 0:27
6
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$ 
 Total@FoldList[Times, #] & /@ binarym

{3, 4, 2, 4, 6}

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Great use of Fold $\endgroup$
    – Jack LaVigne
    Jul 18, 2017 at 23:18
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$ 
Length /@ Map[First, Split /@ binarym, 1]

(*

{3, 4, 2, 4, 6}

*)

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you! It's nice to see other variations. $\endgroup$
    – Astroturf
    Jul 13, 2017 at 22:46
2
$\begingroup$

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]
Improve this answer
$\endgroup$
2
  • $\begingroup$ It would be interesting comparing the different methods on sparse arrays. $\endgroup$
    – Carl Woll
    Jul 14, 2017 at 17:01
  • 1
    $\begingroup$ @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? $\endgroup$
    – Mr.Wizard
    Jul 14, 2017 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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