Как найти все повторяющиеся элементы в списке и количество повторов?
1,00
р.
р.
Нужна функция, которая, например, для списка: [10, 10, 23, 10, 123, 66, 78, 123] вернёт: {10: 3, 123: 2} Как это можно реализовать?
Ответ Реализация Первый способ: 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 " \ "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 " \ "from collections import Counter "\ "A = [random.randint(0, 100) for r in range(10**6)] " print(timeit.repeat(non_Counter, setup=setup, number=10)) non_Counter = \ """counter = defaultdict(int) for elem in A: counter[elem] += 1""" setup = "import random " \ "from collections import defaultdict " \ "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 " \ "A = [random.randint(0, 100) for r in range(10**6)] " \ "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 секунд.