У меня есть сетка, заполненная разными цветами (представленными разными целыми числами). Я хотел бы быстро (в одну строку и с наименьшим временем обработки) подсчитать количество вхождений всех цветов и вернуть наибольшее количество вхождений. Кроме того, я хочу игнорировать нули.
Вот мое решение (вы можете придумать лучшее?):
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())
Вместо того, чтобы добавлять счетчики для каждой строки в счетчик в цикле, вы можете сгладить список списков при создании счетчика!.
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
занимают ~34% времени, затрачиваемого m1
. Нет существенной разницы во времени выполнения между подсчетом нулей и отсутствием подсчета нулей, поскольку вам все равно нужно проверить, является ли это нулем, чтобы принять решение не подсчитывать его.m3_oneline
на чуть-чуть медленнее, чем m2
и m3
(т. е. однострочник не обязательно более эффективен).Да уж, один лайнер точно не гарантирует скорости. Так как это было сравнимо с оптимизированным многострочным и специально запрошенным аскером для красивого вида однострочным, я добавил его.
Хм, на tio.run я постоянно получаю ~ 0,33 ~ 0,21 ~ 0,21. С их «Python 3.8 (предварительная версия)». Какую версию ты используешь?
Вы можете сделать это в одной строке, используя 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)
Поскольку Пранав печатает быстрее меня, вот еще один потенциальный ответ на вашу проблему:
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())
Итак, любой n-мерный массив можно сгладить с помощью x for item_nminus1 in narray for item_nminus2 in item_nminus1 ... for x in item_nis2
. Это мило.
Да, @bittahProfessional мы также можем обрабатывать это динамически, просто отредактировав для того же!
Если вы хотите игнорировать 0, почему вы их считаете в первую очередь...