Как найти повторяющиеся элементы в списке питон

Как получить только повторяющиеся элементы из списка на Python?

Будет хорошо работать только на небольших массивах. Т.к. временная сложность O(n^2). Лучше соорудить свой велосипед за O(n) времени, но с доп. расходом памяти:

In [18]: def f(l): . seen = Counter() . result = [] . for x in l: . if seen[x] == 1: . result.append(x) . seen[x] += 1 . . return result . In [19]: f(['test', 'test1', 'test', 'test', 'test2', 'test2']) Out[19]: ['test', 'test2']

Roman Kitaev, можно сделать, однострочник, не сильно увеличив время работы

result = [k for k, v in Counter(t).items() if v > 1]

Как получить уникальные элементы списка python

Предположим, есть список, который содержит повторяющиеся числа:

numbers = [1, 1, 2, 3, 3, 4]

Но нужен список с уникальными числами:

numbers = [1, 2, 3, 4]

Есть несколько вариантов, как можно получить уникальные значения. Разберем их.

Вариант №1. Использование множества (set) для получения элементов

Использование множества ( set ) — один из вариантов. Он удобен тем, что включает только уникальные элементы. После этого множество можно обратно превратить в список.

Посмотрим на два способа использования множества и списка. Первый — достаточно подробный, но он позволяет увидеть происходящее на каждом этапе.

 
numbers = [1, 2, 2, 3, 3, 4, 5] 
 
def get_unique_numbers(numbers): 
list_of_unique_numbers = [] 
unique_numbers = set(numbers) 
 
for number in unique_numbers: 
list_of_unique_numbers.append(number) 
 
return list_of_unique_numbers 
 
print(get_unique_numbers(numbers)) 

Разберем, что происходит на каждом этапе. Есть список чисел numbers . Передаем его в функцию get_unique_numbers .
Внутри этой функции создается пустой список, который в итоге будет включать все уникальные числа. После этого используется set для получения уникальных чисел из списка numbers .






 
unique_numbers = set(numbers) 

В итоге имеется перечень из уникальных чисел. Осталось сделать из него список. Для этого можно использовать цикл, перебирая каждый из элементов.
 
for number in unique_numbers: 
list_of_unique_numbers.append(number) 

На каждой итерации текущее число добавляется в список list_of_unique_numbers . Наконец, именно этот список возвращается в конце программы.
Есть и более короткий способ использования множества для получения уникальных значений в Python. О нем и пойдет речь дальше.
Короткий вариант с set
Весь код выше можно сжать в одну строку с помощью встроенных в Python функций.
 
numbers = [1, 2, 2, 3, 3, 4, 5] 
unique_numbers = list(set(numbers)) 
print(unique_numbers) 

Хотя этот код сильно отличается от первого примера, идея та же. Сперва множество используется для получения уникальных значений. После этого множество превращается в список.






 
unique_numbers = list(set(numbers)) 

Проще всего думать «изнутри наружу» при чтении этого кода. Самый вложенный код выполняется первым: set(numbers) . Затем — внешний блок: list(set(numbers)) .
Вариант №2. Использование цикла for
Также стоит рассмотреть подход с использованием цикла.
Для начала нужно создать пустой список, который будет включать уникальные числа. После этого можно задействовать цикл для итерации по каждому числу в переданном списке. Если число из него есть в уникальном, то можно переходить к следующему элементу. В противном случае — добавить это число.
Рассмотрим два способа использования цикла. Начнем с более подробного.
 
numbers = [20, 20, 30, 30, 40] 
 
def get_unique_numbers(numbers): 
unique = [] 
 
for number in numbers: 
if number in unique: 
continue 
else: 
unique.append(number) 
return unique 
 
print(get_unique_numbers(numbers)) 

Вот что происходит на каждом этапе. Сначала есть список чисел numbers . Он передается в функцию get_unique_numbers .






Внутри этой функции создается пустой список unique . В итоге он будет включать все уникальные значения.
Цикл будет использоваться для перебора по числам в списке numbers .
 
for number in numbers: 
if number in unique: 
continue 
else: 
unique.append(number) 

Условные конструкции в цикле проверяют, есть ли число текущей итерации в списке unique . Если да, то цикл переходит на следующую итерации. Если нет — число добавляется в список.
Важно отметить, что добавляются только уникальные числа. Когда цикл завершен, список unique с уникальными числами возвращается.
Короткий способ с циклом
Есть и другой способ использования варианта с циклом, который короче на несколько строк.






 
numbers = [20, 20, 30, 30, 40] 
 
def get_unique_numbers(numbers): 
unique = [] 
for number in numbers: 
if number not in unique: 
unique.append(number) 
return unique 

Разница в условной конструкции. В этот раз она следующая — если числа нет в unique , то его нужно добавить.
 
if number not in unique: 
unique.append(number) 

В противном случае цикл перейдет к следующему числу в списке numbers .
Результат будет тот же. Но иногда подобное читать сложнее, когда булево значение опускается.
Есть еще несколько способов поиска уникальных значений в списке Python. Но достаточно будет тех, которые описаны в этой статье.






Я создал этот блог в 2018 году, чтобы распространять полезные учебные материалы, документации и уроки на русском. На сайте опубликовано множество статей по основам python и библиотекам, уроков для начинающих и примеров написания программ.
Мои контакты: Почта

Python Q https://yandex.ru/q/loves/python Online

Python Q CEO Pythonru admin@pythonru.com https://secure.gravatar.com/avatar/b16f253879f7349f64830c64d1da4415?s=96&d=mm&r=g CEO Pythonru Python Александр Редактор https://t.me/cashncarryhttps://pythonru.com/https://yandex.ru/q/profile/cashnc/ PythonRu.com  admin@pythonru.com Alex Zabrodin 2018-10-26 Online Python, Programming, HTML, CSS, JavaScript 
Как найти все повторяющиеся элементы в списке и количество повторов?
Стоимость составления списка-счетчика: нужно 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 = 1> чтобы дубликаты найти. Если производительность подсчёта элементов с помощью словаря интересует, то посмотрите Python - Is a dictionary slow to find frequency of each character? 
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.3k 4 4 золотых знака 25 25 серебряных знаков 52 52 бронзовых знака

стоит отсеять уникальные элементы: 1>

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 серебряных знаков 311 311 бронзовых знаков
Если скорость выполнения не важна, то можно сделать так:






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
Решить данную задачу на языке Python можно несколькими способами. Классический вариант - брать по очереди элементы списка и сравнить каждый со стоящими за ним. При первом же совпадении элементов делается вывод, что в списке есть одинаковы элементы и работа программы завершается.
Еще одним способом решения может быть использование типа данных "множества" ( set ). Как известно, в множествах не может быть одинаковых элементов. При преобразовании списка во множество в нем одинаковые элементы будут представлены единожды, то есть дубли удалятся. Если после этого сравнить длину исходного списка и множества, то станет ясно, есть ли в списке одинаковые элементы. Если длины совпадают, значит все элементы списка уникальны. Если нет, значит, были одинаковые элементы.
Допустим, исходный список генерируется таким кодом:
from random import random N = 10 arr = [0] * N for i in range(N): arr[i] = int(random() * 50) print(arr)
Пример решения классическим способом:
for i in range(N-1): for j in range(i+1, N): if arr[i] == arr[j]: print("Есть одинаковые") quit() print("Все элементы уникальны")
Здесь j принимает значения от следующего элемента за тем, для которого ищется совпадение, до последнего в списке. Сравнивать элемент с индексом i с элементами, стоящими впереди него, не надо, т. к. эти сравнения уже выполнялись на предыдущих итерациях внешнего цикла.
Решение задачи с помощью множества:
setarr = set(arr) if len(arr) == len(setarr): print("Все элементы уникальны") else: print("Есть одинаковые")
Функция set преобразует список во множество.
Примеры выполнения кода:
[2, 4, 1, 2, 45, 38, 26, 11, 49, 25] Есть одинаковые
[44, 49, 21, 19, 23, 27, 34, 9, 41, 31] Все элементы уникальны
В Python у списков есть метод count , который подсчитывает количество элементов списка, чьи значения совпадают с переданным в метод значением. Таким образом мы можем решить задачу, перебирая элементы списка и передавая каждый в метод count(item) . Если хотя бы однажны метод вернет число больше 1, значит в списке имеются повторы значений.
from random import randrange N = 10 arr = [randrange(50) for i in range(N)] print(*arr) for item in arr: if arr.count(item) > 1: print("Есть одинаковые") break else: print("Все элементы уникальны")
В программе выше ветка else цикла for срабатывает только в случае, если работа цикла не была прервана с помощью оператора break .
В более сложном варианте данной задачи может требоваться определить неуникальные элементы, то есть выявить значения, которые встречаются в списке более одного раза, а не просто сказать, есть повторы или нет. Здесь мы не можем использовать прерывание цикла, так как в списке может повторяться и другое значение. Также не можем для всех элементов списка вызывать count() , так как в этом случае метод будет вызываться повторно для уже учтенных ранее значений. Например, результат работы такой программы
from random import randrange N = 10 arr = [randrange(50) for i in range(N)] print(*arr) for item in arr: count = arr.count(item) if count > 1: print(f"Элемент встречается раз") 
может выглядеть так:
9 36 43 21 48 6 19 13 3 48 Элемент 48 встречается 2 раз Элемент 48 встречается 2 раз
Чтобы исключить из перебора повторы значений, мы можем преобразовать список во множество. После этого перебирать в цикле элементы множества, которые уникальны.
from random import randrange N = 10 arr = [randrange(50) for i in range(N)] print(*arr) setarr = set(arr) for item in setarr: count = arr.count(item) if count > 1: print(f"Элемент встречается раз")
X Скрыть Наверх
Решение задач на Python


Похожие публикации:

Hstl что это
Как обойти защиту от записи с экрана
Как сделать чтобы код повторялся в python
Что такое cov в теории вероятности