Нужна функция, которая, например, для списка [10, 10, 23, 10, 123, 66, 78, 123] вернёт {10: 3, 123: 2}.
Ответы
Ответ 1
Реализация
Первый способ:
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.
Почему такие результаты
Объяснение проигрыша наивного решения со словарем:
1) Для того, чтобы получить значение из словаря, необходим хеш переменной 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://hg.python.org/cpython/file/tip/Modules/_collectionsmodule.c#l2204) и вызывает функции _PyDict_GetItem_KnownHash, _PyDict_SetItem_KnownHash, что значительно экономит время.
2) Каждый раз при вызове метода get(elem, 0) вызывается инструкция LOAD_ATTR (https://hg.python.org/cpython/file/ed76eac4491e/Python/ceval.c#l2253), которая должна найти нужный метод по имени. Так как метод не изменится, можно вынести его поиск за цикл:
getter = counter.get
for elem in A:
counter[elem] = getter(elem, 0) + 1
[1.917134484341348, 1.9207427770511107, 1.9153613342431033]
Удалось сэкономить еще 0.6 секунд.
Ответ 2
Есть же уже готовый 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})
Ответ 3
Для случая, когда входной список отсортирован, можно использовать 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()).
Ответ 4
захотелось сравнить производительность для массива состоящего из 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
Ответ 5
Если скорость выполнения не важна, то можно сделать так:
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}
Комментариев нет:
Отправить комментарий