Подсчет вхождений без использования collections.Counter

Я пытаюсь получить наиболее частые и менее частые элементы в списке.

frequency([13,12,11,13,14,13,7,11,13,14,12,14,14])

Мой вывод:

([7], [13, 14])

Я пробовал это с:

import collections
s = [13,12,11,13,14,13,7,11,13,14,12,14,14]
count = collections.Counter(s)
mins = [a for a, b in count.items() if b == min(count.values())]
maxes = [a for a, b in count.items() if b == max(count.values())]
final_vals = [mins, maxes]

Но я не хочу использовать модуль collections и попробую более логичное решение.
Не могли бы вы помочь мне сделать это без коллекций?


person htayal    schedule 30.08.2017    source источник
comment
Для максимального элемента (он же mode) посмотрите на этот вопрос: Поиск режима списка.   -  person Christian König    schedule 30.08.2017
comment
Возможный дубликат Поиск режима списка   -  person araknoid    schedule 30.08.2017


Ответы (4)


Вы можете использовать подход try и except с dict для эмуляции Counter.

def counter(it):
    counts = {}
    for item in it:
        try:
            counts[item] += 1
        except KeyError:
            counts[item] = 1
    return counts

или альтернативно вы можете использовать dict.get со значением по умолчанию 0:

def counter(it):
    counts = {}
    for item in it:
        counts[item] = counts.get(item, 0) + 1
    return counts

И вы должны делать min() и max() вне понимания, чтобы избежать повторного вычисления этого количества (теперь функция O(n) вместо O(n^2):

def minimum_and_maximum_frequency(cnts):
    min_ = min(cnts.values())
    max_ = max(cnts.values())
    min_items = [k for k, cnt in cnts.items() if cnt == min_]
    max_items = [k for k, cnt in cnts.items() if cnt == max_]
    return min_items, max_items

Тогда это будет работать так, как ожидалось:

>>> minimum_and_maximum_frequency(counter([13,12,11,13,14,13,7,11,13,14,12,14,14]))
([7], [13, 14])
person MSeifert    schedule 30.08.2017

s = [13,12,11,13,14,13,7,11,13,14,12,14,14]

occurrences = dict()

for item in s:

    occurrences[item] = occurrences.setdefault(item, 0) + 1

mins = [a for a, b in occurrences.items() if b == min(occurrences.values())]
maxs = [a for a, b in occurrences.items() if b == max(occurrences.values())]

final_vals = [mins, maxs]

defaultdict из collections больше подходит для замены Counter для вычисления вхождения элементов в список. Но поскольку вы ограничиваете использование collections. Таким образом, setdefault более элегантен для работы с KeyError.

person stamaimer    schedule 30.08.2017

как насчет этого:

s = [13,12,11,13,14,13,7,11,13,14,12,14,14]
freq_low = s.count(min(s, key=s.count))
freq_high = s.count(max(s, key=s.count))
mins = [a for a in set(s) if s.count(a) == freq_low]
maxes = [a for a in set(s) if s.count(a) == freq_high]
final_vals = [mins, maxes]
person dummman    schedule 30.08.2017
comment
Это O(n^4) (или, может быть, просто O(n^3)), тогда как проблема может быть легко решена в O(n). - person MSeifert; 30.08.2017

Это очень простое решение, возможно, не самое эффективное (?), но простое.

data = get_data()
freqs, numbers = {}, {}
for i in data:
    freqs[i] = freqs.get(i, 0) + 1
for n, c in freqs.items():
    numbers[c] = numbers.get(c, []) + [n]
counts = list(numbers.keys())
res = (numbers[min(counts)], numbers[max(counts)])

Давайте подробно посмотрим, что у нас есть в скрипте выше, начнем с данных примера, которые вы дали,

In [1]: data = [13,12,11,13,14,13,7,11,13,14,12,14,14]

Мы будем использовать два словаря,

In [2]: freqs, numbers = {}, {}

первый заполняется, повторяя data, его ключи - это отдельные числа в data, а его значения - частота каждого числа в данных (см. примечание для freqs.get(…))

In [3]: for i in data: freqs[i] = freqs.get(i, 0) + 1

второй - это просто обращение первого, ключи - это частоты, а значения - списки чисел с заданной частотой.

In [4]: for n, c in freqs.items(): numbers[c] = numbers.get(c, []) + [n]

In [5]: numbers
Out[5]: {1: [7], 2: [12, 11], 4: [13, 14]}

На данный момент нам нужен список с ключами numbers, т.е.

In [6]: counts = list(numbers.keys())

потому что нас интересуют минимальные и максимальные значения вхождений

In [7]: [numbers[min(counts)], numbers[max(counts)]]
Out[7]: [[7], [13, 14]]

Сноска: метод .get(key, default_value) словаря возвращает значение по умолчанию, если ключ отсутствует в словаре. Мы использовали эту функцию со значением по умолчанию 0 для суммирования вхождений отдельных чисел и с [], пустым списком, для построения список всех номеров с заданной частотой.

person gboffi    schedule 30.08.2017
comment
Может быть, не самый быстрый, но каждый шаг (подсчет, объединение и нахождение крайних значений ключей) составляет O(n), так что общая сложность по-прежнему составляет O(n) - person gboffi; 30.08.2017