Counting elements matching a pattern in a tuple of tuples

Question

I have a matrix m where I would like to calculate the number of zeros.

m=((2,0,2,2),(4,4,5,4),(0,9,4,8),(2,2,0,0))

My current code is as follows:

def zeroCount(M):
    return [item for row in M for item in row].count(0)
    # list of lists is flattened to form single list, and number of 0 are counted

Is there any way to do this quicker? Currently, I'm taking 0.4s to execute the function 20,000 times on 4 by 4 matrices, where the matrices are equally likely to contain zeros as they are not.

Some possible places to start (but which I could not make to work faster than my code) are these other questions: counting non-zero elements in numpy array, finding the indices of non-zero elements, and counting non-zero elements in iterable.

Answer 1

The fastest so far:

def count_zeros(matrix):
    total = 0
    for row in matrix:
        total += row.count(0)
    return total

---

For 2D tuple you could use a generator expression:

def count_zeros_gen(matrix):
    return sum(row.count(0) for row in matrix)

Time comparison:

%timeit [item for row in m for item in row].count(0) # OP
1000000 loops, best of 3: 1.15 µs per loop

%timeit len([item for row in m for item in row if item == 0]) # @thefourtheye
1000000 loops, best of 3: 913 ns per loop

%timeit sum(row.count(0) for row in m) 
1000000 loops, best of 3: 1 µs per loop

%timeit count_zeros(m)
1000000 loops, best of 3: 775 ns per loop

For the baseline:

def f(m): pass
%timeit f(m)
10000000 loops, best of 3: 110 ns per loop

Answer 2

Here is my answer.

reduce(lambda a, b: a + b, m).count(0)

Time:

%timeit count_zeros(m)                                        #@J.F. Sebastian
1000000 loops, best of 3: 813 ns per loop

%timeit len([item for row in m for item in row if item == 0]) #@thefourtheye
1000000 loops, best of 3: 974 ns per loop

%timeit reduce(lambda a, b: a + b, m).count(0)                #Mine
1000000 loops, best of 3: 1.02 us per loop

%timeit countzeros(m)                                         #@frostnational
1000000 loops, best of 3: 1.07 us per loop

%timeit sum(row.count(0) for row in m)                        #@J.F. Sebastian
1000000 loops, best of 3: 1.28 us per loop

%timeit [item for row in m for item in row].count(0)          #OP
1000000 loops, best of 3: 1.53 us per loop

@thefourtheye's is the fastest. This is because of few function call.

@J.F. Sebastian's is the fastest in my environment. I don't know why...

Answer 3

The problem with your solution is that, you have to iterate the list again to get the count O(N). But the len function can get the count in O(1).

You can make this a lot quicker with this

def zeroCount(M):
    return len([item for row in M for item in row if item == 0])

Answer 4

Check this out:

from itertools import chain, filterfalse # ifilterfalse for Python 2
def zeroCount(m):
    total = 0
    for x in filterfalse(bool, chain(*m)): 
        total += 1
    return total

Perfomance tests on Python 3.3.3:

from timeit import timeit
from itertools import chain, filterfalse
import functools

m = ((2,0,2,2),(4,4,5,4),(0,9,4,8),(2,2,0,0))

def zeroCountOP():
    return [item for row in m for item in row].count(0)

def zeroCountTFE():
    return len([item for row in m for item in row if item == 0])

def zeroCountJFS():
    return sum(row.count(0) for row in m)

def zeroCountuser2931409():
    # `reduce` is in `functools` in Py3k
    return functools.reduce(lambda a, b: a + b, m).count(0)

def zeroCount():
    total = 0
    for x in filterfalse(bool, chain(*m)): 
        total += 1
    return total

print('Original code     ', timeit(zeroCountOP, number=100000))
print('@J.F.Sebastian    ', timeit(zeroCountJFS, number=100000))
print('@thefourtheye     ', timeit(zeroCountTFE, number=100000))
print('@user2931409      ', timeit(zeroCountuser2931409, number=100000))
print('@frostnational    ', timeit(zeroCount, number=100000))

The above give me these results:

Original code      0.244224319984056
@thefourtheye      0.22169152169497108
@user2931409       0.19247795242092186
@frostnational     0.18846473728790825
@J.F.Sebastian     0.1439318853410907

@J.F.Sebastian's solution is a winner, mine is a runner-up (about 20% slower).

Comprehensive solution for both Python 2 and Python 3:

import sys
import itertools

if sys.version_info < (3, 0, 0):
    filterfalse = getattr(itertools, 'ifilterfalse')
else:
    filterfalse = getattr(itertools, 'filterfalse')


def countzeros(matrix):
    ''' Make a good use of `itertools.filterfalse`
        (`itertools.ifilterfalse` in case of Python 2) to count 
        all 0s in `matrix`. '''
    counter = 0
    for _ in filterfalse(bool, itertools.chain(*matrix)):
        counter += 1
    return counter


if __name__ == '__main__':
    # Benchmark
    from timeit import repeat
    print(repeat('countzeros(((2,0,2,2),(4,4,5,4),(0,9,4,8),(2,2,0,0)))',
                 'from __main__ import countzeros',
                 repeat=10,
                 number=100000))

Answer 5

Use numpy:

import numpy

m=((2,0,2,2),(4,4,5,4),(0,9,4,8),(2,2,0,0))
numpy_m = numpy.array(m)
print numpy.sum(numpy_m == 0)

How does the above work? First, your "matrix" is converted to a numpy array (numpy.array(m)). Then, each entry is checked for equality with zero (numpy_m == 0). This yields a binary array. Summing over this binary array gives the number of zero elements in the original array.

Note that numpy will be clearly efficient for larger matrices. 4x4 might be too small to see a large performance difference vs. ordinary python code, esp. if you are initializing a python "matrix" like above.

Answer 6

One numpy solution is:

import numpy as np

m = ((2,0,2,2),(4,4,5,4),(0,9,4,8),(2,2,0,0))
mm = np.array(m)

def zeroCountSmci():
    return (mm==0).sum() # sums across all axes, by default