计数器对象/列表中任何项目的最大出现次数

Question

我有一个用不同颜色填充的网格（由不同的整数表示）。我想快速（在一行中和最少的处理时间）计算所有颜色的出现次数和 return 出现的最高次数。另外，我想忽略零。

这是我的解决方案（你能想到更好的吗？）：

grid = [[0, 0, 5, 0, 0, 0, 0, 10, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 10, 10, 10, 0, 0, 0], [0, 30, 30, 0, 33, 0, 0, 0, 0, 0, 0, 0, 0], [0, 30, 0, 0, 33, 33, 0, 0, 50, 0, 50, 0, 0], [0, 30, 0, 0, 33, 33, 0, 0, 50, 50, 50, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 50, 0, 0], [0, 0, 0, 0, 0, 0, 0, 88, 88, 88, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 88, 88, 0, 0, 0, 0]]
rows,cols=len(grid),len(grid[0])
ctrSum=Counter()
for row in grid:
    ctrSum += Counter(row)
ctrSum -= Counter({0:(rows*cols)}) # subtract out a ridiculous amount of zeroes to eliminate them all from the counter
return max(ctrSum.values())

Answer 1

您可以在创建计数器时展平 list-of-lists ，而不是将每一行的计数添加到循环中的计数器！

ctr = Counter(x for row in grid for x in row)
# Counter({0: 79, 5: 1, 10: 4, 30: 4, 33: 5, 50: 6, 88: 5})

然后，删除0键，找到最大值：

del ctr[0]
max_key, max_count = max(ctr.items(), key=lambda item: item[1]) # 50, 6

计算零并稍后删除密钥并不比根本不计算它们快或慢（在我的计算机上，timeit 两种方法返回的时间相似）

grid = [[0, 0, 5, 0, 0, 0, 0, 10, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 10, 10, 10, 0, 0, 0], [0, 30, 30, 0, 33, 0, 0, 0, 0, 0, 0, 0, 0], [0, 30, 0, 0, 33, 33, 0, 0, 50, 0, 50, 0, 0], [0, 30, 0, 0, 33, 33, 0, 0, 50, 50, 50, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 50, 0, 0], [0, 0, 0, 0, 0, 0, 0, 88, 88, 88, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 88, 88, 0, 0, 0, 0]]

def m1(grid):
    rows,cols=len(grid),len(grid[0])
    ctrSum=Counter()
    for row in grid:
        ctrSum += Counter(row)
    ctrSum -= Counter({0:(rows*cols)}) # subtract out a ridiculous amount of zeroes to eliminate them all from the counter
    return max(ctrSum.items(), key=lambda x: x[1])

def m2(grid):
    ctr = Counter(x for row in grid for x in row)
    del ctr[0]
    return max(ctr.items(), key=lambda item: item[1])

def m3(grid):
    ctr = Counter(x for row in grid for x in row if x)
    return max(ctr.items(), key=lambda item: item[1])

def m3_oneline(grid):
    return max(Counter(x for row in grid for x in row if x).items(), key=lambda x: x[1])


t1 = timeit.timeit('func(grid)', setup='from __main__ import grid, m1 as func', number=10000)
t2 = timeit.timeit('func(grid)', setup='from __main__ import grid, m2 as func', number=10000)
t3 = timeit.timeit('func(grid)', setup='from __main__ import grid, m3 as func', number=10000)
t3_oneline = timeit.timeit('func(grid)', setup='from __main__ import grid, m3_oneline as func', number=10000)

print(t2/t1, t3/t1, t3_oneline/t1)
0.3436699657289107 0.3483052483876959 0.3614440352763763

m1（可以预见）花费的时间最长，因为您创建所有这些计数器只是为了将它们的值加在一起。
m2 和 m3 占用的时间约为 m1 的 34%。计算零和不计算零在运行时间上没有显着差异，因为您无论如何都需要检查它是否为零才能决定不计算它。
m3_oneline 稍微比 m2 和 m3 慢（即 one-liner 不一定更有效.)

Answer 2

您可以在一行中执行此操作，使用 reduce() 构建一个计数器，其中包含所有行中元素的频率，然后将 key 传递给 max()在找到最频繁的元素时从考虑中删除 0:

from collections import Counter
from functools import reduce
import math

result = max(reduce(lambda x, y: x + Counter(y), grid, Counter()).items(),
     key=lambda x: x[1] if x[0] else -math.inf)
print(result)

您还可以使用 sum():

将所有计数器加在一起

result = max(sum(map(Counter, grid), Counter()).items(),
     key=lambda x: x[1] if x[0] else -math.inf)
print(result)

使用上面的网格，这两个打印：

(50, 6)

Answer 3

由于 Pranav 的打字速度比我快，这里是您问题的另一个可能的答案：

ans = max(Counter(x for row in grid for x in row if x!=0).values())

我想到了不规则嵌套列表，这是可以做到的：

unfurl=lambda x: sum(map(unfurl,x),[]) if isinstance(x,list) or isinstance(x, tuple) else [x]
ans = max(Counter(unfurl(grid)).values())

计数器对象/列表中任何项目的最大出现次数

Maximum Number of Occurrences of Any Item in Counter object / list

python

python-3.x

performance

counter