Подсчитайте общее количество неуникальных элементов в списке - PullRequest
Новая
       2

Подсчитайте общее количество неуникальных элементов в списке

1 голос
/ 18 марта 2020

Я ищу наиболее эффективный по времени способ подсчета количества неуникальных элементов в большом списке (около 100 000 элементов) для Python.

Метод, который я до сих пор использовал: 

original_list = [1, 4, 6, 2, 2, 1, 5, 3, 2]

duplicates_list = []
for item in original_list:
    if original_list.count(item) > 1:
        duplicates_list.append(item)

duplicates_count = len(duplicates_list)

print(duplicates_count)

# Should give the following answer:
5

В настоящее время большой список из примерно 70-80 тыс. Элементов занимает вычисление в течение 1-2 минут. Мне интересно, сможем ли мы сократить время, необходимое для расчета, как можно меньше (возможно, до 3-10 секунд).

Я действительно ценю всю помощь!

Ответы [ 2 ]

5 голосов
/ 18 марта 2020

Объект Counter должен быть быстрее, так как в вашей версии вы вызываете count() для каждого элемента в списке, то есть 100 000 раз для вашего вопроса. Это приведет к выполнению Count () один раз для всего списка, тогда итерация по объекту Counter будет выполняться только один раз для каждого уникального значения. 

original_list = [1, 4, 6, 2, 2, 1, 5, 3, 2]

from collections import Counter
count = Counter(original_list)

dupes = sum(v for k, v in count.items() if v > 1)
2 голосов
/ 18 марта 2020

Для этого используется поддержка арифметических c операторов в классе Counter - и set, и Counter поддерживают несколько полезных операций: 

>>> li = [1, 4, 6, 2, 2, 1, 5, 3, 2]
>>> s  = set(li)
>>>
>>> len(li) - len(s) + len(Counter(li) - Counter(s))
5
>>>

len(li) - len(set(li)) дает число дубликаты, или количество элементов списка, оставшихся после того, как мы извлечем set элементов.

Чтобы получить список элементов набора, связанных с элементом в оставшемся списке: 

>>> list((Counter(li) - Counter(set(li))))
[1, 2]

И чтобы получить список дубликатов, оставшихся в списке после удаления всех элементов set: 

>>> list((Counter(li) - Counter(set(li))).elements())
[1, 2, 2]

Если бы была операция вычитания для списков, это то, что мы получили бы после вычитания set из списка.

Предлагаемая оптимизация

Если возможно, приложение, использующее этот список из 70-80К элементов, должно постепенно наращивать Счетчик с самого начала, как он заполняет список. При необходимости он может иметь свой список, счетчик или другие необходимые структуры, поэтому метрики или другие типы обработки могут быть сокращены на последующих этапах.

Контрольные показатели

В произвольном порядке, вот как долго каждый алгоритм обрабатывал список случайных чисел из 80K. 

>>> li     = [random.randint(0, 100) for _ in range(80 * 1000)]
>>> n_iter = 1000
>>>
>>> timeit.timeit("s = set(li); "
...               "len(li) - len(s) + len(Counter(li) - Counter(s))", 
...               globals=globals(), number=n_iter)
7.048838693
>>> 
>>> timeit.timeit("sum(v for k, v in Counter(li).items() if v > 1)", 
...               globals=globals(), number=n_iter)
5.787936814
>>>
>>> timeit.timeit(original_posters_script, globals=globals(), number=n_iter)
# Takes too much time to sit through. It's very slow. O(N^2)
>>>

Неудивительно, что самым быстрым алгоритмом является другое решение Counter в выбранном ответе.

...