Удаление дубликатов в списках

Общий подход к получению уникальной коллекции элементов – использование set . Наборы представляют собой неупорядоченные коллекции отдельных объектов. Чтобы создать набор из любого итерабельного, вы можете просто передать его во встроенную функцию set() . Если позже вам понадобится реальный список, вы также можете передать набор в функцию list() .

Следующий пример должен охватывать все, что вы пытаетесь сделать:

 >>> t = [1, 2, 3, 1, 2, 5, 6, 7, 8] >>> t [1, 2, 3, 1, 2, 5, 6, 7, 8] >>> list(set(t)) [1, 2, 3, 5, 6, 7, 8] >>> s = [1, 2, 3] >>> list(set(t) - set(s)) [8, 5, 6, 7] 

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

Если заказ важен для вас, вам придется использовать другой механизм. Этот вопрос более подробно освещает эту тему.

FWIW, новый (v2.7) способ Python для удаления дубликатов из итерабельного, сохраняя его в исходном порядке:

 >>> from collections import OrderedDict >>> list(OrderedDict.fromkeys('abracadabra')) ['a', 'b', 'r', 'c', 'd'] 

В Python 3.5 у OrderedDict есть реализация C. Мои тайминги показывают, что это сейчас и самый быстрый и самый короткий из различных подходов.

В CPython 3.6 регулярный dict теперь упорядочен и компактен. На данный момент это считается детальностью реализации, но, скорее всего, станет гарантированной функцией в будущем. Это дает нам новый быстрый способ дедуплирования при сохранении порядка:

 >>> list(dict.fromkeys('abracadabra')) ['a', 'b', 'r', 'c', 'd'] 

Это однострочный: list(set(source_list)) будет делать трюк.

set – это то, что не может иметь дубликатов.

Обновление: порядок сохранения заказов состоит из двух строк:

 from collections import OrderedDict OrderedDict((x, True) for x in source_list).keys() 

Здесь мы используем тот факт, что OrderedDict запоминает порядок вставки ключей и не изменяет его при обновлении значения в определенном ключе. Мы вставляем True качестве значений, но мы можем вставлять что угодно, значения просто не используются. ( set работает так же, как и dict с игнорируемыми значениями.)

 >>> t = [1, 2, 3, 1, 2, 5, 6, 7, 8] >>> t [1, 2, 3, 1, 2, 5, 6, 7, 8] >>> s = [] >>> for i in t: if i not in s: s.append(i) >>> s [1, 2, 3, 5, 6, 7, 8] 

Если вы не заботитесь о заказе, просто выполните это:

 def remove_duplicates(l): return list(set(l)) 

У гарантированного set нет дубликатов.

Чтобы создать новый список, сохраняющий порядок первых элементов дубликатов в L

newlist=[ii for n,ii in enumerate(L) if ii not in L[:n]]

например, if L=[1, 2, 2, 3, 4, 2, 4, 3, 5] то newlist будет [1,2,3,4,5]

Это проверяет, что каждый новый элемент не появился ранее в списке перед его добавлением. Также им не нужны импорт.

Другой способ:

 >>> seq = [1,2,3,'a', 'a', 1,2] >> dict.fromkeys(seq).keys() ['a', 1, 2, 3] 

Коллега отправил принятый ответ в качестве части его кода ко мне для кодового просмотра сегодня. Хотя я, конечно, восхищаюсь элегантностью ответного вопроса, я не доволен выступлением. Я пробовал это решение (я использую set для уменьшения времени поиска)

 def ordered_set(in_list): out_list = [] added = set() for val in in_list: if not val in added: out_list.append(val) added.add(val) return out_list 

Для сравнения эффективности я использовал случайную выборку из 100 целых чисел – 62 были уникальными

 from random import randint x = [randint(0,100) for _ in xrange(100)] In [131]: len(set(x)) Out[131]: 62 

Ниже приведены результаты измерений

 In [129]: %timeit list(OrderedDict.fromkeys(x)) 10000 loops, best of 3: 86.4 us per loop In [130]: %timeit ordered_set(x) 100000 loops, best of 3: 15.1 us per loop 

Ну, что произойдет, если набор удаляется из решения?

 def ordered_set(inlist): out_list = [] for val in inlist: if not val in out_list: out_list.append(val) return out_list 

Результат не так плох, как у OrderedDict , но все же более чем в 3 раза больше исходного решения

 In [136]: %timeit ordered_set(x) 10000 loops, best of 3: 52.6 us per loop 

У меня был указатель в моем списке, поэтому я не мог использовать вышеупомянутый подход. Я получил ошибку:

 TypeError: unhashable type: 

Поэтому, если вы заботитесь о порядке и / или какие-то предметы расстегиваются . Тогда вы можете найти это полезным:

 def make_unique(original_list): unique_list = [] [unique_list.append(obj) for obj in original_list if obj not in unique_list] return unique_list 

Некоторые могут рассмотреть понимание списка с побочным эффектом, чтобы не быть хорошим решением. Вот альтернатива:

 def make_unique(original_list): unique_list = [] map(lambda x: unique_list.append(x) if (x not in unique_list) else False, original_list) return unique_list 

Простой и легкий:

 myList = [1, 2, 3, 1, 2, 5, 6, 7, 8] cleanlist = [] [cleanlist.append(x) for x in myList if x not in cleanlist] 

Вывод:

 >>> cleanlist [1, 2, 3, 5, 6, 7, 8] 

Попробуйте использовать наборы:

 import sets t = sets.Set(['a', 'b', 'c', 'd']) t1 = sets.Set(['a', 'b', 'c']) print t | t1 print t - t1 

Вы можете использовать функцию numpy unique () (в конечном итоге используя функцию .tolist (), если вам не нужен массив numpy)

 import numpy as np t=['a','a','b','b','b','c','c','c'] a=np.unique(t).tolist() print a >>>['a','b','c'] 

ниже код прост для удаления дубликата в списке

 def remove_duplicates(x): a = [] for i in x: if i not in a: a.append(i) return a print remove_duplicates([1,2,2,3,3,4]) 

он возвращает [1,2,3,4]

Вы также можете сделать это:

 >>> t = [1, 2, 3, 3, 2, 4, 5, 6] >>> s = [x for i, x in enumerate(t) if i == t.index(x)] >>> s [1, 2, 3, 4, 5, 6] 

Причина, по которой выше, заключается в том, что index метод возвращает только первый индекс элемента. Дублирующие элементы имеют более высокие индексы. См. Здесь :

list.index (x [, start [, end]])
Возвращает индекс с нулевым индексом в списке первого элемента, значение которого равно x. Повышает значение ValueError, если такого элемента нет.

Этот человек заботится о заказе без особых хлопот (OrderdDict & others). Вероятно, это не самый пифонический путь, не самый короткий путь, но трюк:

 def remove_duplicates(list): ''' Removes duplicate items from a list ''' singles_list = [] for element in list: if element not in singles_list: singles_list.append(element) return singles_list 

Все подходы, OrderedDicts порядок, которые я видел здесь, пока используют либо наивное сравнение (с наилучшей сложностью O (n ^ 2)), либо тяжелые команды OrderedDicts / set + list , которые ограничены входами хешируемого. Вот хеш-независимое решение O (nlogn):

 def filter_duplicates(lst): # Enumerate the list to restore order lately; reduce the sorted list; restore order def append_unique(acc, item): return acc if acc[-1][1] == item[1] else acc.append(item) or acc srt_enum = sorted(enumerate(lst), key=lambda (i, val): val) return [item[1] for item in sorted(reduce(append_unique, srt_enum, [srt_enum[0]]))] 

В настоящее время вы можете использовать Counter-класс:

 >>> import collections >>> c = collections.Counter([1, 2, 3, 4, 5, 6, 1, 1, 1, 1]) >>> c.keys() dict_keys([1, 2, 3, 4, 5, 6]) 

Вот пример, возвращающий список без сохранения порядка повторения. Не требуется никакого внешнего импорта.

 def GetListWithoutRepetitions(loInput): # return list, consisting of elements of list/tuple loInput, without repetitions. # Example: GetListWithoutRepetitions([None,None,1,1,2,2,3,3,3]) # Returns: [None, 1, 2, 3] if loInput==[]: return [] loOutput = [] if loInput[0] is None: oGroupElement=1 else: # loInput[0]<>None oGroupElement=None for oElement in loInput: if oElement<>oGroupElement: loOutput.append(oElement) oGroupElement = oElement return loOutput 

Уменьшить вариант с сохранением заказа:

Предположим, что у нас есть список:

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

Уменьшить вариант (неэффективный):

 >>> reduce(lambda r, v: v in r and r or r + [v], l, []) [5, 6, 1, 2, 3, 4] 

5 x быстрее, но сложнее

 >>> reduce(lambda r, v: v in r[1] and r or (r[0].append(v) or r[1].add(v)) or r, l, ([], set()))[0] [5, 6, 1, 2, 3, 4] 

Объяснение:

 default = (list(), set()) # user list to keep order # use set to make lookup faster def reducer(result, item): if item not in result[1]: result[0].append(item) result[1].add(item) return result reduce(reducer, l, default)[0] 

Есть много других ответов, предлагающих разные способы сделать это, но они все пакетные операции, а некоторые из них выбрасывают исходный порядок. Это может быть в порядке, в зависимости от того, что вам нужно, но если вы хотите перебирать значения в порядке первого экземпляра каждого значения, и вы хотите удалить дубликаты «на лету» против всех одновременно, вы можете использовать этот генератор:

 def uniqify(iterable): seen = set() for item in iterable: if item not in seen: seen.add(item) yield item 

Это возвращает генератор / итератор, поэтому вы можете использовать его в любом месте, где вы можете использовать итератор.

 for unique_item in uniqify([1, 2, 3, 4, 3, 2, 4, 5, 6, 7, 6, 8, 8]): print(unique_item, end=' ') print() 

Вывод:

 1 2 3 4 5 6 7 8 

Если вам нужен list , вы можете сделать это:

 unique_list = list(uniqify([1, 2, 3, 4, 3, 2, 4, 5, 6, 7, 6, 8, 8])) print(unique_list) 

Вывод:

 [1, 2, 3, 4, 5, 6, 7, 8] 

Вот самое быстрое питоновское решение, дружественное к другим, перечисленным в ответах.

Использование деталей реализации оценки короткого замыкания позволяет использовать понимание списка, которое достаточно быстро. visited.add(item) всегда возвращает None в результате, который оценивается как False , поэтому правая сторона or всегда будет результатом такого выражения.

Время это сами

 def deduplicate(sequence): visited = set() adder = visited.add # get rid of qualification overhead out = [adder(item) or item for item in sequence if item not in visited] return out 

Проверьте это, если вы хотите удалить дубликаты (вместо редактирования нового списка) вместо использования встроенного набора, dict.keys, uniqify, counter

 >>> t = [1, 2, 3, 1, 2, 5, 6, 7, 8] >>> for i in t: ... if i in t[t.index(i)+1:]: ... t.remove(i) ... >>> t [3, 1, 2, 5, 6, 7, 8] 

Использование набора :

 a = [0,1,2,3,4,3,3,4] a = list(set(a)) print a 

Использование уникального :

 import numpy as np a = [0,1,2,3,4,3,3,4] a = np.unique(a).tolist() print a 

Лучший способ удаления дубликатов из списка – использовать функцию set () , доступную в python, снова преобразовать этот набор в список

 In [2]: some_list = ['a','a','v','v','v','c','c','d'] In [3]: list(set(some_list)) Out[3]: ['a', 'c', 'd', 'v'] 

Чтобы удалить дубликаты, сделайте это SET, а затем снова создайте LIST и распечатайте / используйте его. У набора гарантировано наличие уникальных элементов. Например :

 a = [1,2,3,4,5,9,11,15] b = [4,5,6,7,8] c=a+b print c print list(set(c)) #one line for getting unique elements of c 

Вывод будет следующим (проверяется в python 2.7)

 [1, 2, 3, 4, 5, 9, 11, 15, 4, 5, 6, 7, 8] #simple list addition with duplicates [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 15] #duplicates removed!! 

Для полноты, и поскольку это очень популярный вопрос, библиотека toolz предлагает unique функцию:

 >>> tuple(unique((1, 2, 3))) (1, 2, 3) >>> tuple(unique((1, 2, 1, 3))) (1, 2, 3) 

Я думаю, что преобразование в набор – это самый простой способ удалить дубликат:

 list1 = [1,2,1] list1 = list(set(list1)) print list1 

Вы можете сделать это просто с помощью наборов.

Шаг1: Получить различные элементы списков
Шаг2 Получить общие элементы списков
Шаг 3 Объедините их

 In [1]: a = ["apples", "bananas", "cucumbers"] In [2]: b = ["pears", "apples", "watermelons"] In [3]: set(a).symmetric_difference(b).union(set(a).intersection(b)) Out[3]: {'apples', 'bananas', 'cucumbers', 'pears', 'watermelons'} 

 def remove_duplicates(A): [A.pop(count) for count,elem in enumerate(A) if A.count(elem)!=1] return A 

Компиляция списка для удаления дубликатов

Если вы не заботитесь о порядке и хотите чего-то другого, чем предлагаемые выше питонические способы (т. Е. Его можно использовать в интервью), тогда:

 def remove_dup(arr): size = len(arr) j = 0 # To store index of next unique element for i in range(0, size-1): # If current element is not equal # to next element then store that # current element if(arr[i] != arr[i+1]): arr[j] = arr[i] j+=1 arr[j] = arr[size-1] # Store the last element as whether it is unique or repeated, it hasn't stored previously return arr[0:j+1] if __name__ == '__main__': arr = [10, 10, 1, 1, 1, 3, 3, 4, 5, 6, 7, 8, 8, 9] print(remove_dup(sorted(arr))) 

Сложность времени: O (n)

Вспомогательное пространство: O (n)

Ссылка: http://www.geeksforgeeks.org/remove-duplicates-sorted-array/