Максимальное количество вхождений любого элемента в объекте/списке счетчика

У меня есть сетка, заполненная разными цветами (представленными разными целыми числами). Я хотел бы быстро (в одну строку и с наименьшим временем обработки) подсчитать количество вхождений всех цветов и вернуть наибольшее количество вхождений. Кроме того, я хочу игнорировать нули.

Вот мое решение (вы можете придумать лучшее?):

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

Если вы хотите игнорировать 0, почему вы их считаете в первую очередь...

Zircoz 18.03.2022 18:27
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
4
1
62
3
Перейти к ответу Данный вопрос помечен как решенный

Ответы 3

Вместо того, чтобы добавлять счетчики для каждой строки в счетчик в цикле, вы можете сгладить список списков при создании счетчика!.

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 (т. е. однострочник не обязательно более эффективен).

Да уж, один лайнер точно не гарантирует скорости. Так как это было сравнимо с оптимизированным многострочным и специально запрошенным аскером для красивого вида однострочным, я добавил его.

Zircoz 18.03.2022 19:06

Хм, на tio.run я постоянно получаю ~ 0,33 ~ 0,21 ~ 0,21. С их «Python 3.8 (предварительная версия)». Какую версию ты используешь?

Kelly Bundy 19.03.2022 01:08

Вы можете сделать это в одной строке, используя 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 18.03.2022 23:05

Да, @bittahProfessional мы также можем обрабатывать это динамически, просто отредактировав для того же!

Zircoz 19.03.2022 11:10

Другие вопросы по теме