I have a grid filled with different colors (represented by differing integers). I would like to quickly (in one line and least amount of processing time) count the number of occurrences of all the colors and return the highest number of occurrences. Also, I want to ignore zeroes.

Here is my solution (can you think of a better one?):

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

CodePudding user response：

Since Pranav types faster than me, here is another potential answer to your problem:

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

CodePudding user response：

Instead of adding the counts for each row to the counter in a loop, you can flatten the list-of-lists while creating the counter!

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

Then, delete the 0 key, and find the max:

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

Counting the zeros and deleting the key later is not significantly faster or slower than not counting them at all (On my computer, timeit returned similar times for both approaches)

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 (predictably) takes the longest time since you're creating all those counters only to add their values together.
• m2 and m3 take ~34% of the time taken by m1. There is not a significant difference in runtime between counting zeros and not counting zeros, since you need to check if it is a zero anyway in order to decide not to count it.
• m3_oneline is ever so slightly slower than m2 and m3 (i.e. a one-liner is not necessarily more efficient.)

CodePudding user response：

You can do this in one line, using reduce() to build a Counter that contains the frequencies for the elements across all the rows, then passing a key to max() that eliminates 0 from consideration when finding the most frequent element:

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)

You can also add all the Counters together using sum():

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

With the above grid, both of these print:

(50, 6)