Как найти все повторяющиеся элементы в списке и количество повторов?
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 секунд.
[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 секунд.
