在一个元组的元组中统计符合某种模式的元素数量

Question

我有一个矩阵m，我想计算其中0的数量。

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

我的当前代码如下：

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

有没有更快的方法来完成这个任务？目前，在4x4矩阵上执行20000次该函数需要0.4秒，其中矩阵可能包含0也可能不包含。

一些可能的起点（但我无法使它们比我的代码更快）是这些其他问题：在numpy数组中计算非零元素、查找非零元素的索引和计算可迭代对象中非零元素的数量。

- Vincent Tjeng

---

相关：Python 3：如何使用.count()检查列表中的列表 - jfs

Answer 1

迄今为止最快的：

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

对于2D元组，您可以使用生成器表达式： （参考链接）

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

时间比较：

%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

基线：

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

- jfs

---

@J.F.你的代码看起来将是最快的，但我会再开放一段时间这个问题，让其他人也试试。 - Vincent Tjeng

Answer 2

Here is my answer.

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

时间：

%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的速度最快。这是由于函数调用很少。

@J.F. Sebastian在我的环境中是最快的。我不知道为什么...

- Kei Minagawa

---

比我的还慢:P 看看测试结果 - vaultah

独立环境中的测试：Python3，Python2 - vaultah

我已经添加了使用显式循环而不是生成器表达式的更快解决方案。 - jfs

@J.F. Sebastian：已添加。普通代码非常快！！ - Kei Minagawa

Answer 3

你的解决方案存在问题，因为你需要遍历列表才能获取计数O(N)。但是len函数可以在O(1)内获取计数。

你可以使用以下方法使其更快：

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

- thefourtheye

---

在我的电脑上，结果相似：对于问题中的m元组，len([])为913，而[].count为1150。作为比较，在我的电脑上def f(m): pass为110。 - jfs

我本来会建议使用 **sum(item == 0 for row in m for item in row)**，但是结果证明它比较慢 :( - volcano

@volcano 在提出建议之前，我甚至计时了其他选项的时间 :) - thefourtheye

Answer 4

看这个：

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

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

上述操作给我带来了以下结果：

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

@J.F.Sebastian的解决方案是胜者，我的方案是亚军（速度慢约20%）。

关于Python 2和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))

- vaultah

---

对于你的方法，你不能只是采用 counter = len(itertools.filterfalse(...)) 吗？ - smci

我已经添加了使用显式循环的解决方案。目前为止，它是最快的。 - jfs

对于小的4x4矩阵，它可能会慢一些。 - smci

迭代器的长度的标准惯用语是 len(_ for _ in iter(...))。直接使用生成器表达式，无需增加计数器，可以节省一些循环次数。 - smci

@frostnational 感谢您编写代码，使每个人都能够对其代码进行基准测试。我当初提问时肯定应该包含这一点。 - Vincent Tjeng

Answer 5

使用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)

首先，你的“矩阵”将被转换为numpy数组(numpy.array(m))。然后，检查每个元素是否等于零(numpy_m == 0)。这会产生一个二进制数组。在这个二进制数组上求和可以得到原始数组中零元素的数量。

请注意，对于较大的矩阵，numpy将明显更有效率。4x4可能太小，无法看到与普通python代码的大量性能差异，特别是如果你像上面初始化一个python“矩阵”。

- jrennie

---

对于4x4矩阵来说速度非常慢。 - jfs

@jrennie —也许你只能在处理非常大的矩阵时看到性能上的提升，但在我的情况下并不会有太多作用，因为我正在处理小矩阵。我认为使用 numpy 的开销相当高。 - Vincent Tjeng

Answer 6

一个numpy的解决方案是：

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

- smci

---

即使输入是numpy数组，对于给定的m来说速度也会慢几倍。 - jfs