Как найти все повторяющиеся элементы в списке и количество повторов?
Стоимость составления списка-счетчика: нужно 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 секунд.
Отслеживать
ответ дан 8 июн 2016 в 17:31
6,389 4 4 золотых знака 35 35 серебряных знаков 57 57 бронзовых знаков
Использование .get() , filter(lambda) некрасиво выглядит. Если вам profiler говорит, что подсчёт элементов является узким местом и Counter() не достаточно быст для ваших целей, то в этом случае можно попробовать collections.defaultdict , тогда код выглядит как: for elem in A: counter[elem] += 1 и dups =
9 июн 2016 в 19:45
@jfs, я когда писал ответ даже не задумывался, что можно пробовать оптимизировать такие простые вещи. А оказалось, что по оптимизации строки counter[elem] = counter.get(elem, 0) + 1 можно целую статью написать с объяснениями, экспериментами и выкладками dis . Даже если перед циклом написать getter = counter.get , то производительность возрастает на 20%. Ну как так-то?
9 июн 2016 в 19:56
Меня смущает тот факт, что используется неидиоматичный код, без хорошей на то причины. И мне хорошо известно, что много вариантов по микрооптимизации можно придумать (нажмите на ссылку из моего предыдущего комментария)—я не понимаю к чему тут оптимизировать, но если вас это интересует, то я вижу в ответе пример кода ( filter(lambda) ), который одновременно некрасивый и медленный (я привёл пример, как более идиоматично и эффективно данную задачу решить в прошлом комментарии).
9 июн 2016 в 20:03
@jfs, согласен, if count > 1 выглядит лучше — изменил.
9 июн 2016 в 21:18
Хорошо, что filter(lambda) убрали. Что мешает .items() вызывать, чтобы избежать counter[elem] как показано в моём первом комментарии? 2- Если вы о сложности операций упоминаете, то в худшем случае (для специально сконструированного ввода) квадратичное поведение может быть у словаря, а не линейное. В среднем (для случайного ввода) поведение линейное амортизированное. 3- Измерение производительности является тяжёлой задачей, поэтому не стоит большого внимания полученным цифрам придавать, если вы не провели работу по учёту многих, многих факторов. Переместите counter = .. из setup.
10 июн 2016 в 10:52
Есть же уже готовый Counter в модуле collections.
from collections import Counter c = Counter([10, 10, 23, 10, 123, 66, 78, 123]) print(c) Отслеживать
ответ дан 8 июн 2016 в 17:43
20.4k 4 4 золотых знака 25 25 серебряных знаков 52 52 бронзовых знака
стоит отсеять уникальные элементы:
9 июн 2016 в 19:25
захотелось сравнить производительность для массива состоящего из 1.000.000 элементов:
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() # dict solution def dct(A): counter = <> for elem in A: counter[elem] = counter.get(elem, 0) + 1 return 1, counter)> 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=) 100 loops, best of 3: 14.4 ms per loop In [71]: df = pd.DataFrame() In [72]: %paste (df.val .value_counts() .reset_index() .query('val > 1') .rename(columns=) ) ## -- End pasted text -- Out[72]: val count 0 10 3 1 123 2 Отслеживать
ответ дан 9 июн 2016 в 16:47
MaxU — stand with Ukraine MaxU — stand with Ukraine
149k 12 12 золотых знаков 59 59 серебряных знаков 132 132 бронзовых знака
Хм, Counter — потомок dict , и подсчет он ведет точно таким методом: mapping[elem] = mapping.get(elem, 0) + 1 , и метод get не переопределен. Единственный момент, что есть типа реализация этой строки на С и если она импортируется, то используется именно она. Что они там могли написать?
9 июн 2016 в 18:27
Ага, так вот же настоящий счетчик для Counter — hg.python.org/cpython/file/tip/Modules/… — там какой-то адок — я обновлю свой ответ с поясненем, почему Counter быстрее.
9 июн 2016 в 18:37
@m9_psy, спасибо за ссылку — немного запутанно, но интересно
9 июн 2016 в 20:01
#!/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) # ->
Если список неотсортирован, то сортировка это O(n * log n) операция. На практике следует измерять производительность разных вариантов, если производительность этого кода имеет значение в вашем случае (так как для небольшого n , O(n * log n) операция может быть быстрее O(n) операции, такой как с использованием Counter() ).
Отслеживать
ответ дан 9 июн 2016 в 19:56
52.2k 11 11 золотых знаков 108 108 серебряных знаков 312 312 бронзовых знаков
Если скорость выполнения не важна, то можно сделать так:
def test(lst): return 1> print(test([10, 10, 23, 10, 123, 66, 78, 123])) Отслеживать
ответ дан 8 июн 2016 в 18:16
user194374 user194374
Один из способов решения этой задачи — использовать словарь. Можно создать словарь, в котором каждому элементу списка соответствует количество его повторений, и в цикле перебрать элементы списка, добавляя их в словарь.
Вот пример такой функции:
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) #
Функция 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() В этом коде сначала импортируется модуль 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) #
В этом коде определяется функция count_unique , которая принимает список lst и возвращает словарь, в котором каждому уникальному элементу списка
Удалить все дубликаты из списка. Python
Для удаления дубликатов из списка можно использовать функцию set(), которая автоматически удаляет все повторяющиеся элементы. Но если необходимо сохранить порядок элементов, можно использовать следующий код:
def remove_duplicates(lst):
«»»Удаляет дубликаты из списка, сохраняя порядок элементов.»»»
seen = set()
result = []
for item in lst:
if item not in seen:
seen.add(item)
result.append(item)
return result
В этой функции мы создаем пустое множество seen для отслеживания уже пройденных элементов и пустой список result для сохранения уникальных элементов в том же порядке, в котором они были в исходном списке. Затем мы проходимся по каждому элементу списка lst. Если элемент еще не встречался, мы добавляем его в множество seen и в список result. Если же элемент уже был встречен, мы его игнорируем. Наконец, мы возвращаем список result как результат функции.
Переписать другими словами
Написать сочинение по запросу
Или попробуйте другие режимы нейросети.
Сберегите свое время и избавьтесь от лишних копий в списке благодаря нашей нейросети. Наша онлайн-система удалит все дубликаты в несколько секунд, а вы сможете потратить свое время на более важные задачи. Наша нейросеть пишет текст, и использует современные методы машинного обучения, чтобы справиться с задачей на 100%. Безопасность и удобство использования гарантированы. Попробуйте уже сегодня и убедитесь сами!
Python-сообщество
- Начало
- » Python для новичков
- » Поиск одинаковых элементов в списке
#1 Июнь 4, 2013 20:03:59
che1911 Зарегистрирован: 2013-06-04 Сообщения: 2 Репутация: 0 Профиль Отправить e-mail
Поиск одинаковых элементов в списке
Есть список из нескольких строковых значений. Как определить, есть ли в списке повторяющиеся элементы?
#2 Июнь 4, 2013 22:40:33
elisk Зарегистрирован: 2013-04-09 Сообщения: 35 Репутация: 7 Профиль Отправить e-mail
Поиск одинаковых элементов в списке
s = ['qqqq', 'wwww', 'eeee', 'qqqq', 'zzzz', 'zzzz', 'qqqq'] z = <> for i in s: if i in z: z[i] += 1 else: z[i] = 1 print z
#3 Июнь 4, 2013 22:56:32
dimy44 От: Евпатория Зарегистрирован: 2012-04-21 Сообщения: 463 Репутация: 42 Профиль
Поиск одинаковых элементов в списке
>>> L = ["a", "b", "c", "b"] >>> ("yes", "no")[len(L)==len(set(L))] 'yes' >>>
#4 Июнь 5, 2013 07:04:04
che1911 Зарегистрирован: 2013-06-04 Сообщения: 2 Репутация: 0 Профиль Отправить e-mail
Поиск одинаковых элементов в списке
elisk, спасибо, работает, но немного сложнее чем нужно.
dimy44, вау! Очень круто, спасибо. А где почитать про set?
Отредактировано che1911 (Июнь 5, 2013 07:34:34)
#5 Июнь 5, 2013 20:45:41
o7412369815963 От: Зарегистрирован: 2009-06-17 Сообщения: 1986 Репутация: 32 Профиль Отправить e-mail
Поиск одинаковых элементов в списке
Пример от elisk, можно заменить на
from collections import Counter Counter(['qqqq', 'wwww', 'eeee', 'qqqq', 'zzzz', 'zzzz', 'qqqq'])
Получение одинаковых элементов многоуровневого списка
Здравствуйте. Имеется многоуровневый список (рисунок 1), как получить на выходе все повторяющиеся элементы? Для одноуровневого списка это сделать несложно, а вот с многоуровневым возникли проблемы. Должно быть как на рисунке 2. Перепробовал кучу способов, но все утыкается в уровни, не до конца понимаю как с ними работать. 
Рисунок 1. 
Рисунок 2
19.03.2018 в 18:31 #7698 Score: 0
Karma: 4 pts
Добрый день. Через ноды динамо это, наверняка, можно сделать. Но первым в голову пришло решение на питоне:
list = IN[0] res = [] for i in range(len(list)): if list[i] in list[i + 1:] or list[i] in res: res.append(list[i]) # Назначьте вывод переменной OUT. OUT = res
Единственное, что сортировка не такая, как в примере.
19.03.2018 в 20:16 #7699 Score: 0
Karma: 86 pts
Несколько примеров тут:
2-х уровневый можно так :
https://pastebin.com/zAGkCWeP
21.03.2018 в 10:15 #7702 Score: 0
Karma: 134 pts
Все смотрю на эту задачу и не понимаю условия….
Все ещё актуально ?Если задача ещё актуальна, могу набросать код.
Если задание “получить на выходе все повторяющиеся элементы”, то ответ был бы 2,5,9. Т.е. конечным элементом должен быть не список, а цифра в списке. Так ли это?
Тогда для меня нет проблем в поиске любых элементов и их сравнения в списках любой глубины и сложности. Задачу предлагаю решать через map и рекурсии. Ещё вариант – из списка любой сложности сделать одноуровневый массив и уже в нем искать соответствия.
21.03.2018 в 10:33 #7703 Score: 0
list = IN[0] res = [] for i in range(len(list)): if list[i] in list[i + 1:] or list[i] in res: res.append(list[i]) # Назначьте вывод переменной OUT. OUT = res Этот вариант хорошо сработал , спасибо всем.