# Counting sublists containing 0

Given a list: data = {{0, 2}, {0, 0}, {1, 0}, {1, 2}, {2, 3}}. I would like to count the number of sublists which contain zero.

Count[data, {0, _}] + Count[data, {_, 0}] - Count[data, {0, 0}]


Is there any better/efficient way to do this?

-
Cases[data, {0, _} | {_, 0}] // Length – Rorschach Oct 6 '13 at 15:17
Or Count[data, a : {__, __} /; MemberQ[a, 0]] – C. E. Oct 6 '13 at 15:19
Or Count[data, {___, 0, ___}] – jVincent Oct 6 '13 at 15:20
– Michael E2 Oct 6 '13 at 15:47
@MichaelE2 Pity that question never gained momentum, but a perfect example on why someone should ask a single, clear-cut question instead of four. – István Zachar Oct 6 '13 at 17:13

Using the behavior of Times in case of multiplication by (exact) zero:

Count[Times @@@ data, 0]


3

As proposed by MichaelE2, this can be considerably faster depending on the structure and size of the input:

Count[Times @@ Transpose[data], 0]


3

-
Somewhat faster, and much faster on packed arrays: Count[Times @@ Transpose[data], 0] – Michael E2 Oct 6 '13 at 15:42
@MichaelE2 wicked! – Yves Klett Oct 6 '13 at 15:51
@MichaelE2 added your version in to preserve it for posterity (and performance) - if you want to post separately, lemme know :-) – Yves Klett Oct 7 '13 at 11:09
It's fine as part of yours. It's basically the same idea, and the two belong together. – Michael E2 Oct 7 '13 at 12:14
@MichaelE2 totally. Uh, and it seems your solution wins the speed contest for long list of tuples hands down. – Yves Klett Oct 7 '13 at 12:54

Using a built in function called LengthWhile and Sort.

LengthWhile gives the length of all the continuous elements that meet a criteria. So in order to use it we have to first sort the list and sublists first.

LengthWhile[Sort@Map[Sort, data], #[[1]] == 0 &]


3

-
Sorting is an overkill for the problem and it most probably is disastrous for long sublists. – István Zachar Oct 7 '13 at 14:27
@IstvanZachar I thought so too, but it is actually not that bad. It is actually faster then the uncompiled Times@ and Leonid's Sparse Array one, in the case of your large data test. – lalmei Oct 7 '13 at 14:32

Here is a fast straight forward procedural implementation compiled to C, this requires all the sublists to have the same length but performs similar when interested in sublists containing an arbitrary integer, not just 0.

simpleC =
Compile[{{list, _Integer, 2}},
Block[{count = 0},
Do[If[MemberQ[sublist, 0], count++], {sublist, list}]; count],
Parallelization -> True, CompilationTarget -> "C",
RuntimeAttributes -> Listable, RuntimeOptions -> "Speed"];


and a faster parallel implementation

simpleCparallel =
Compile[{{sublist, _Integer, 1}}, Boole[MemberQ[sublist, 0]],
Parallelization -> True, CompilationTarget -> "C",
RuntimeAttributes -> Listable, RuntimeOptions -> "Speed"];

data = RandomInteger[{0, 9}, {100, 100000}];
simpleC[data] // AbsoluteTiming
Total@simpleCparallel[data] // AbsoluteTiming

{0.018001,100}
{0.010001,100}

data = RandomInteger[{0, 9}, {10000000, 10}];
simpleC[data] // AbsoluteTiming
Total@simpleCparallel[data] // AbsoluteTiming

{0.554032,6513970}
{0.346020,6513970}


This simple solution seems to be reasonably quick:

Count[Min /@ Abs[data],  0| 0.]


and a slightly faster compiled version

countMinC =
Compile[{{d, _Integer, 2}}, Count[Min /@ Abs[d], 0],
Parallelization -> True, CompilationTarget -> "C",
RuntimeAttributes -> Listable, RuntimeOptions -> "Speed"];


and another option that is slightly faster for short sublists with inspiration from @Leonid

countMinC2 =
Compile[{{d, _Integer, 2}},
Length@d - Total[Unitize[Min /@ Abs[d]]], Parallelization -> True,
CompilationTarget -> "C", RuntimeAttributes -> Listable,
RuntimeOptions -> "Speed"];

-
Count is based on patterns, so the fully robust version will probably Count[Min /@ Abs[data], 0| 0.]. This probably won't affect the compiled version though. – Leonid Shifrin Oct 6 '13 at 17:12
Abs[] (see edit) should fix that. – s0rce Oct 6 '13 at 17:14
@Leonid Be fair, almost everyone (even OP) omitted real 0. or PossibleZeroQ :) – István Zachar Oct 6 '13 at 17:16
@IstvánZachar Well, fair enough. I did not, however :) – Leonid Shifrin Oct 6 '13 at 17:18
@LeonidShifrin fixed now. Thanks. Compiled version doesn't matter as it needs to be specific to be either Intergers or Reals. @IstvánZachar, timings added to your answer. – s0rce Oct 6 '13 at 17:21

Here's another set of timings based on the data structure of the problem as originally proposed. The count of lists with at least one zero appears right after the timing.

 r := RandomInteger[{0, 9}]
data = Table[{r, r}, {i, 10^6}];
"Long list with short sublists"

{Count[Times @@ Transpose[data], 0] // AbsoluteTiming, "MichaelE2"}
{Fold[Boole@Not@FreeQ[#2, 0] + # &, 0, data] //
AbsoluteTiming, "rm-rf"}
{countzero[data] // AbsoluteTiming, "RunnyKine -compiled"}
{countC[data] // AbsoluteTiming, "István -compiled"}
{Count[data, {0, _} | {_, 0}] //
AbsoluteTiming, "Blackbird, using Count"}
{Length@Cases[data, {0, _} | {_, 0}] // AbsoluteTiming, "Blackbird"}
{LengthWhile[Map[Sort, data], #[[1]] == 0 &] //
AbsoluteTiming, "lalmei"}
{Count[Times @@@ data, 0] // AbsoluteTiming, "Yves Klett"}
{Count[data, {___, 0, ___}] // AbsoluteTiming, "jVincent"}
{Count[Sort /@ data, {0, _}] // AbsoluteTiming, "David Carraher"}
{countZ@data // AbsoluteTiming, "Leonid #1"}
{Select[data, MemberQ[#, 0] &] // Length //
AbsoluteTiming, "RunnyKine"}
{Select[data, Count[#, 0] != 0 &] // Length //
AbsoluteTiming, "RunnyKine"}
{Total[Map[Total,
data /. {0 -> 1, _Integer -> 0}] /. {0 -> 0, _Integer -> 1}] //
AbsoluteTiming, "Ymareth"}
{Count[Simplify[And @@@ data], False] // AbsoluteTiming, "István?"}
{Count[Position[#, 0, 1, 1] & /@ data, Except@{}] //
AbsoluteTiming, "István?"}
{Count[data, a : {__, __} /; MemberQ[a, 0]] //
AbsoluteTiming, "Anon"}
{countZAlt@data // AbsoluteTiming, "Leonid #2"}


Testing lists with sublists of varying lengths.

There were some anomalies when we tested sublists of varying lengths. Note that there are 2*10^6 random integers in each of the cases tested.

   Table[data[k] = RandomInteger[{0, 9}, {10^(6 - k), 2*10^k}], {k, 0,
6}];
"Long list with short sublists"
result = {
{"SublistLength", 2, 20, 2*10^2, 2*10^3, 2*10^4, 2*10^5, 2*10^6},
Prepend[
Table[Count[Times @@ Transpose[data[j]], 0] // AbsoluteTiming, {j,
0, 6}], "MichaelE2"],
Prepend[
Table[Fold[Boole@Not@FreeQ[#2, 0] + # &, 0, data[j]] //
AbsoluteTiming, {j, 0, 6}], "rm-rf"],
Prepend[Table[countzero[data[j]] // AbsoluteTiming, {j, 0, 6}],
"RunnyKine-compiled"],
Prepend[Table[countC[data[j]] // AbsoluteTiming, {j, 0, 6}],
"István-compiled"],
Prepend[
Table[Count[Times @@@ data[j], 0] // AbsoluteTiming, {j, 0, 6}],
"Yves Klett"],
Prepend[
Table[Count[data[j], {___, 0, ___}] // AbsoluteTiming, {j, 0, 6}],
"jVincent"],
Prepend[Table[countZ@data[j] // AbsoluteTiming, {j, 0, 6}],
"Leonid #1"],
Prepend[Table[countZAlt@data[j] // AbsoluteTiming, {j, 0, 6}],
"Leonid #2"],
Prepend[
Table[Count[Simplify[And @@@ data[j]], False] //
AbsoluteTiming, {j, 0, 6}], "István"],
Prepend[
Table[Count[Position[#, 0, 1, 1] & /@ data[j], Except@{}] //
AbsoluteTiming, {j, 0, 6}], "István"],
Prepend[
Table[Total[
Map[Total,
data[j] /. {0 -> 1, _Integer -> 0}] /. {0 -> 0, _Integer ->
1}] // AbsoluteTiming, {j, 0, 6}], "Ymareth"]}
Grid[result, Dividers -> {{1, 2}, {1, 2}}]


-
Did you by chance omit a definition for r? – Yves Klett Oct 7 '13 at 12:49
Could you kindly include my method countzero, I'm curious to see how well Select performs here. – RunnyKine Oct 7 '13 at 13:22
Yves. Yes, I did. Thanks for catching it. – DavidC Oct 7 '13 at 18:36
RunnyKine, I don't know how to run the compiled version. Simply running your code is clearly not enough. – DavidC Oct 7 '13 at 18:47
Just do countzero[data] after evaluating countzero – RunnyKine Oct 7 '13 at 19:08

If the sublists are always of length 2 then this is fast:

Length[data] - Dot @@ Transpose[Unitize @ data]

-

Here's my late entry using Select

Select[data, MemberQ[#, 0] &] // Length


OR

Select[data, Count[#, 0] != 0 &] // Length


With compiled version:

countzero = Compile[{{data, _Integer, 2}},
Select[data, MemberQ[#, 0] &] // Length, Parallelization -> True,
CompilationTarget -> "C", RuntimeAttributes -> Listable, RuntimeOptions -> "Speed"]

-

For long sublists it might be reasonable to immediately terminate element-checking after first 0 is encountered: logical operators and Position exhibit such shortcutting.

data = RandomInteger[{0, 9}, {100, 100000}];

AbsoluteTiming@Count[Times @@ Transpose[data], 0]
AbsoluteTiming@Count[Min /@ Abs@data, 0 | 0.]
AbsoluteTiming@countMinC[data]
AbsoluteTiming@Count[Times @@@ data, 0]
AbsoluteTiming@Fold[Boole@Not@FreeQ[#2, 0] + # &, 0, data]
AbsoluteTiming@countZ@data
AbsoluteTiming@countZAlt@data
AbsoluteTiming@Count[Position[#, 0, 1, 1] & /@ data, Except@{}]
AbsoluteTiming@Count[Simplify[And @@@ data], False]
AbsoluteTiming@Total[Map[Total, data /. {0 -> 1, _Integer -> 0}] /. {0 -> 0, _Integer -> 1}]

{1.244071, 100} (* MichaelE2 *)
{0.048003, 100} (* s0rce *)
{0.043002, 100} (* s0rce compiled *)
{0.924053, 100} (* Yves *)
{0.067004, 100} (* rm -rf *)
{0.844048, 100} (* Leonid countZ *)
{0.049003, 100} (* Leonid countZalt *)
{0.207012, 100} (* Position *)
{2.551146, 100} (* And *)
{2.282131, 100} (* Ymareth *)


Simplify of course could be problematic if data is longer or elements are more complex than integers... Let's check it on many more shorter sublists:

data = RandomInteger[{0, 9}, {100000, 10}];
(* ... *)

{0.018001,65083} (* MichaelE2 *)
{0.022001,65083} (* s0rce *)
{0.004000,65083} (* s0rce compiled *)
{0.125007,65083} (* Yves *)
{0.040002,65083} (* rm -rf *)
{0.025001,65083} (* Leonid countZ *)
{0.007000,65083} (* Leonid countZalt *)
{0.286016,65083} (* Position *)
{30.547747,65083 (* And *)
{0.323018,65083} (* Ymareth *)


Of course, compiling Times (I guess the only one that is directly compilable) wins over all the others:

countC = Compile[{{d, _Integer, 2}}, Count[Times @@@ d, 0],
Parallelization -> True , CompilationTarget -> "C",  RuntimeAttributes -> Listable,
RuntimeOptions -> "Speed"];

-
There is also the second solution in my post, countZAlt, which performs much better than my first one on your first test. Mind including it in your benchmarks? – Leonid Shifrin Oct 6 '13 at 16:41
Oh wow... I didn't mine was that fast! BTW, 0. for Leonid's doesn't seem right... I don't get that (it seems slower than mine). However, his countZAlt is faster. – R. M. Oct 6 '13 at 16:43
@Leonid Sure, sorry for the delay, I had to test some of my own solutions as well :) – István Zachar Oct 6 '13 at 16:54
Would you mind including @MichaelE2´s version Count[Times @@ Transpose[data], 0] in the timings? – Yves Klett Oct 6 '13 at 18:38
@Yves s0rce kindly did that, it definitely deserved the inclusion! Next time please feel free to edit in! – István Zachar Oct 7 '13 at 9:14

By substitution...

Total[Map[Total, data /. {0 -> 1, _Integer -> 0}] /. {0 -> 0, _Integer -> 1}]

-

Another solution:

Fold[Boole@Not@FreeQ[#2, 0] + # &, 0, list]
(* 3 *)

-
There shall be a Microtutorial badge! BTW I like this frog better than the last one. – Yves Klett Oct 6 '13 at 16:22
@YvesKlett Me too! – R. M. Oct 6 '13 at 16:30

Here is a reasonably fast one:

countZ =
Length[Union @@ Map[SparseArray[#]["NonzeroPositions"] &, Transpose[1 - Unitize[#]]]] &


you use it as

countZ[data]


If you don't want to use SparseArrays, this will give roughly similar performance:

countZAlt = Total @ Unitize[Last@Dimensions@# - Total[Unitize[#], {2}]] &

-
Great, this is a oneliner tutorial :-) – Yves Klett Oct 6 '13 at 15:54
@YvesKlett All right, point taken - I added another version which does not use SparseArray :) – Leonid Shifrin Oct 6 '13 at 16:02