Нужна функция, которая, например, для списка:
[10, 10, 23, 10, 123, 66, 78, 123]
вернёт:
{10: 3, 123: 2}
Как это можно реализовать?
Stack Overflow на русском — это сайт вопросов и ответов для программистов. Присоединяйтесь! Регистрация займёт не больше минуты.
Присоединиться к сообществуA = [10, 10, 23, 10, 123, 66, 78, 123]
counter = {}
for elem in A:
counter[elem] = counter.get(elem, 0) + 1
doubles = {element: count for element, count in counter.items() if count > 1}
print(doubles)
from collections import Counter
counter = Counter(A)
from collections import defaultdict
counter = defaultdict(int)
for elem in A:
counter[elem] += 1
Стоимость составления списка-счетчика: нужно n раз вставить в словарь значения. Вставка состоит из двух операций: сначала проверка, есть ли такой номер в словаре и, собственно, вставка - все вместе O(1) среднем или O(n) в худшем для редких случаев, когда у всех элементов одинаковый хеш. То есть стоимость составления счетчика - O(n) в среднем, O(n^2) в худшем.
Следущий шаг - отфильтровать только нужное. В худшем случае нужно пройти по всему счетчику - снова n операций по O(1) или в худшем O(n) - взять из словаря, сравнить с единицей, записать в новый словарь. В среднем O(n).
Итого O(n) в среднем или для специально подготовленных данных O(n^2) в худшем.
Обновление с большим массивом: Минутка замеров:
import timeit
non_Counter = \
"""counter = {}
for elem in A:
counter[elem] = counter.get(elem, 0) + 1"""
setup = "import random\n" \
"A = [random.randint(0, 100) for r in range(10**6)]"
print(timeit.repeat(non_Counter, setup=setup, number=10))
non_Counter = """Counter(A)"""
setup = "import random\n" \
"from collections import Counter\n"\
"A = [random.randint(0, 100) for r in range(10**6)]\n"
print(timeit.repeat(non_Counter, setup=setup, number=10))
non_Counter = \
"""counter = defaultdict(int)
for elem in A:
counter[elem] += 1"""
setup = "import random\n" \
"from collections import defaultdict\n" \
"A = [random.randint(0, 100) for r in range(10**6)]"
print(timeit.repeat(non_Counter, setup=setup, number=10))
Результат:
[2.461800295429222, 2.456825704148736, 2.50377292183442]
[0.7278253601108151, 0.7268121314832463, 0.7283143209274385]
[1.3038446032438102, 1.3117127258723897, 1.3013156371393428]
Как видно из результатов, быстрее всех решение с Counter.
Объяснение проигрыша наивного решения со словарем:
Для того, чтобы получить значение из словаря, необходим хеш переменной elem
. Значение хеша необходимо дважды: для того, чтобы получить предыдущее значение и для того, чтобы установить новое. Очевидно, вычислять два хеша - производить двойную работу. Замеры:
non_Counter = \
"""
args = [None, None]
for elem in A:
hash(elem)
hash(elem)"""
setup = "import random\n" \
"A = [random.randint(0, 100) for r in range(10**6)]\n" \
"counter = {}"
print(timeit.repeat(non_Counter, setup=setup, number=10))
[1.4283945417028974, 1.433934455438878, 1.4188164931286842]
Как видно, лишнее вычисление съедает 0.7 секунд или 30% от общего времени. К сожалению, нет стандартной возможности получить значение из словаря по значению хеша. В классе Counter функция подсчета написана на более низком уровне (https://github.com/python/cpython/blob/3.11/Modules/_collectionsmodule.c#L2284) и вызывает функции _PyDict_GetItem_KnownHash, _PyDict_SetItem_KnownHash, что значительно экономит время.
Также каждый раз при вызове метода get(elem, 0)
вызывается инструкция LOAD_ATTR, которая должна найти нужный метод по имени. Так как метод не изменится, можно вынести его поиск за цикл. Трюк старый, надо с ним быть внимательнее в новых версиях интерпретатора, может это более не работает:
getter = counter.get
for elem in A:
counter[elem] = getter(elem, 0) + 1
[1.917134484341348, 1.9207427770511107, 1.9153613342431033]
Удалось сэкономить еще 0.6 секунд.
.get()
, filter(lambda)
некрасиво выглядит. Если вам profiler говорит, что подсчёт элементов является узким местом и Counter()
не достаточно быст для ваших целей, то в этом случае можно попробовать collections.defaultdict
, тогда код выглядит как: for elem in A: counter[elem] += 1
и dups = {e: count for e, count in counter.items() if count > 1}
чтобы дубликаты найти. Если производительность подсчёта элементов с помощью словаря интересует, то посмотрите Python - Is a dictionary slow to find frequency of each character?
counter[elem] = counter.get(elem, 0) + 1
можно целую статью написать с объяснениями, экспериментами и выкладками dis
. Даже если перед циклом написать getter = counter.get
, то производительность возрастает на 20%. Ну как так-то?
filter(lambda)
), который одновременно некрасивый и медленный (я привёл пример, как более идиоматично и эффективно данную задачу решить в прошлом комментарии).
filter(lambda)
убрали. Что мешает .items()
вызывать, чтобы избежать counter[elem]
как показано в моём первом комментарии? 2- Если вы о сложности операций упоминаете, то в худшем случае (для специально сконструированного ввода) квадратичное поведение может быть у словаря, а не линейное. В среднем (для случайного ввода) поведение линейное амортизированное. 3- Измерение производительности является тяжёлой задачей, поэтому не стоит большого внимания полученным цифрам придавать, если вы не провели работу по учёту многих, многих факторов. Переместите counter = ..
из setup.
Есть же уже готовый Counter в модуле collections.
from collections import Counter
c = Counter([10, 10, 23, 10, 123, 66, 78, 123])
print(c)
получаем вот что: Counter({10: 3, 123: 2, 66: 1, 78: 1, 23: 1})
{e: count for e, count in c.items() if count > 1}
захотелось сравнить производительность для массива состоящего из 1.000.000 элементов:
Setup:
from collections import Counter
import pandas as pd
# random list (length: 1.000.000)
l = np.random.randint(1,100, 10**6).tolist()
# pandas DF
df = pd.DataFrame({'val':l})
# dict solution
def dct(A):
counter = {}
for elem in A:
counter[elem] = counter.get(elem, 0) + 1
return {key: counter[key] for key in filter(lambda elem: counter[elem] > 1, counter)}
Timing:
In [79]: %timeit Counter(l)
10 loops, best of 3: 48 ms per loop
сам по себе Counter - достаточно быстрый, но нам еще надо будет отфильтровать результат ...
In [80]: %timeit dct(l)
10 loops, best of 3: 178 ms per loop
In [81]: %timeit df.val.value_counts().reset_index().query('val > 1').rename(columns={'index':'val', 'val':'count'})
100 loops, best of 3: 14.4 ms per loop
Pandas demonstration:
In [71]: df = pd.DataFrame({'val': [10, 10, 23, 10, 123, 66, 78, 123]})
In [72]: %paste
(df.val
.value_counts()
.reset_index()
.query('val > 1')
.rename(columns={'index':'val', 'val':'count'})
)
## -- End pasted text --
Out[72]:
val count
0 10 3
1 123 2
dict
, и подсчет он ведет точно таким методом: mapping[elem] = mapping.get(elem, 0) + 1
, и метод get
не переопределен. Единственный момент, что есть типа реализация этой строки на С и если она импортируется, то используется именно она. Что они там могли написать?
Для случая, когда входной список отсортирован, можно использовать itertools.groupby()
вместо {el: count for el, count in collections.Counter(L).items() if count > 1}
:
#!/usr/bin/env python
from itertools import groupby
L = [10, 10, 23, 10, 123, 66, 78, 123]
duplicates = {}
for el, group in groupby(sorted(L)):
count = len(list(group))
if count > 1:
duplicates[el] = count # element -> number of occurrences
print(duplicates) # -> {10: 3, 123: 2}
Если список неотсортирован, то сортировка это O(n * log n)
операция. На практике следует измерять производительность разных вариантов, если производительность этого кода имеет значение в вашем случае (так как для небольшого n
, O(n * log n)
операция может быть быстрее O(n)
операции, такой как с использованием Counter()
).
Если скорость выполнения не важна, то можно сделать так:
def test(lst):
return {a: lst.count(a) for a in set(lst) if lst.count(a) > 1}
print(test([10, 10, 23, 10, 123, 66, 78, 123]))
Вывод:
{10: 3, 123: 2}
Один из способов решения этой задачи - использовать словарь. Можно создать словарь, в котором каждому элементу списка соответствует количество его повторений, и в цикле перебрать элементы списка, добавляя их в словарь.
Вот пример такой функции:
def count_repeats(lst):
"""
Возвращает словарь, в котором каждому элементу списка lst соответствует
количество его повторений.
"""
repeats = {}
for item in lst:
if item in repeats:
repeats[item] += 1
else:
repeats[item] = 1
return repeats
# Пример использования функции
lst = [10, 10, 23, 10, 123, 66, 78, 123]
repeats = count_repeats(lst)
print(repeats) # {10: 3, 123: 2}
Функция count_repeats
принимает на вход список lst
, перебирает его элементы и добавляет их в словарь repeats
. Если элемент уже есть в словаре, то увеличивается значение соответствующей пары ключ-значение, если же элемента еще нет в словаре, то добавляется пара с ключом равным этому элементу и значением 1
.
Вы можете использовать эту функцию, чтобы найти повторяющиеся элементы в списке и количество их повторений.
Вы также можете использовать функцию Counter из модуля collections, чтобы посчитать количество повторений элементов списка. Эта функция возвращает словарь, в котором каждому элементу списка соответствует количество его повторений.
Вот пример кода, который использует функцию Counter:
from collections import Counter
def count_repeats(lst):
"""
Возвращает словарь, в котором каждому элементу списка lst соответствует
количество его повторений.
"""
return Counter(lst)
# Пример использования функции
lst = [10, 10, 23, 10, 123, 66, 78, 123]
repeats = count_repeats(lst)
print(repeats) # Counter({10: 3, 123: 2})
В этом коде сначала импортируется модуль collections
и функция Counter
, а затем определяется функция count_repeats
, которая принимает список lst
и возвращает результат вызова функции Counter
на этом списке.
Вы также можете использовать функцию most_common
из модуля collections
, чтобы найти топ-N самых часто встречающихся элементов в списке. Эта функция принимает список и число N, и возвращает список кортежей, каждый из которых содержит элемент и количество его повторений.
Вот пример кода, который использует функцию most_common
:
from collections import Counter
def find_top_repeats(lst, n):
"""
Возвращает топ-N самых часто встречающихся элементов в списке lst.
"""
return Counter(lst).most_common(n)
# Пример использования функции
lst = [10, 10, 23, 10, 123, 66, 78, 123]
top_repeats = find_top_repeats(lst, 2)
print(top_repeats) # [(10, 3), (123, 2)]
В этом коде сначала импортируется модуль collections
и функция Counter
, а затем определяется функция find_top_repeats
, которая принимает список lst
и число n
, и возвращает результат вызова функции most_common
Если вам нужно найти только уникальные элементы в списке, то можете использовать функцию set. Эта функция создает множество из элементов списка, удаляя повторяющиеся элементы. Множество не содержит повторяющихся элементов, поэтому вы можете использовать его, чтобы найти уникальные элементы в списке.
Вот пример кода, который использует функцию set
:
def find_unique(lst):
"""
Возвращает список уникальных элементов в списке lst.
"""
return list(set(lst))
# Пример использования функции
lst = [10, 10, 23, 10, 123, 66, 78, 123]
unique = find_unique(lst)
print(unique) # [66, 78, 10, 123, 23]
В этом коде определяется функция find_unique
, которая принимает список lst
и возвращает список уникальных элементов. Для этого список преобразуется в множество
Если вам нужно найти только уникальные элементы в списке и посчитать их количество, то можете соединить два предыдущих подхода: сначала использовать функцию set
для нахождения уникальных элементов, а затем функцию count_repeats
для подсчета их количества.
Вот пример кода, который реализует этот подход:
def count_unique(lst):
"""
Возвращает словарь, в котором каждому уникальному элементу списка lst соответствует
количество его повторений.
"""
repeats = {}
for item in set(lst):
repeats[item] = lst.count(item)
return repeats
# Пример использования функции
lst = [10, 10, 23, 10, 123, 66, 78, 123]
unique_counts = count_unique(lst)
print(unique_counts) # {66: 1, 78: 1, 10: 3, 123: 2}
В этом коде определяется функция count_unique
, которая принимает список lst
и возвращает словарь, в котором каждому уникальному элементу списка
#Добавление в словарь элементов списка и количества их вхождений:
l = [10, 10, 23, 10, 123, 66, 78, 123]
num = 0
d = {}
for i in l:
kol = l.count(l[num])
val = l[num]
num+=1
d[val] = kol
print(d)
#Результат:
{10: 3, 23: 1, 123: 2, 66: 1, 78: 1}