Как вы удаляете дубликаты из списка, сохраняя порядок?

Question

Есть ли встроенная функция, которая удаляет дубликаты из списка в Python, сохраняя при этом порядок? Я знаю, что могу использовать набор для удаления дубликатов, но это разрушает первоначальный порядок. Я также знаю, что я могу катиться так:

def uniq(input):
  output = []
  for x in input:
    if x not in output:
      output.append(x)
  return output

(Спасибо за за это образец кода .)

Но я бы хотел использовать встроенную или более Pythonic идиому, если это возможно.

Смежный вопрос: В Python, какой самый быстрый алгоритм удаления дубликатов из списка, чтобы все элементы были уникальными при сохранении порядка ?

Answer 1

Для типов без хэширования (например, списков), основанных на MizardX:

def f7_noHash(seq)
    seen = set()
    return [ x for x in seq if str( x ) not in seen and not seen.add( str( x ) )]

Answer 2

Заимствование рекурсивной идеи, используемой при определении функции 10000 * для списков в Haskell, это будет рекурсивный подход:

def unique(lst):
    return [] if lst==[] else [lst[0]] + unique(filter(lambda x: x!= lst[0], lst[1:]))

например:.

In [118]: unique([1,5,1,1,4,3,4])
Out[118]: [1, 5, 4, 3]

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

In [122]: %timeit unique(np.random.randint(5, size=(1)))
10000 loops, best of 3: 25.3 us per loop

In [123]: %timeit unique(np.random.randint(5, size=(10)))
10000 loops, best of 3: 42.9 us per loop

In [124]: %timeit unique(np.random.randint(5, size=(100)))
10000 loops, best of 3: 132 us per loop

In [125]: %timeit unique(np.random.randint(5, size=(1000)))
1000 loops, best of 3: 1.05 ms per loop

In [126]: %timeit unique(np.random.randint(5, size=(10000)))
100 loops, best of 3: 11 ms per loop

Мне также кажется интересным, что это может быть легко обобщено другими операциями. Как это:

import operator
def unique(lst, cmp_op=operator.ne):
    return [] if lst==[] else [lst[0]] + unique(filter(lambda x: cmp_op(x, lst[0]), lst[1:]), cmp_op)

Например, вы можете передать функцию, которая использует понятие округления до того же целого числа, как если бы оно было «равенством» в целях уникальности, например:

def test_round(x,y):
    return round(x) != round(y)

тогда уникальный (some_list, test_round) предоставил бы уникальные элементы списка, где уникальность больше не означала традиционное равенство (что подразумевается при использовании любого вида подхода на основе множеств или основанного на дикт-ключах к этой проблеме), но вместо этого означает, что для каждого возможного целого числа K, к которому элементы могут округляться, берется только первый элемент, округляемый до K, например:

In [6]: unique([1.2, 5, 1.9, 1.1, 4.2, 3, 4.8], test_round)
Out[6]: [1.2, 5, 1.9, 4.2, 3]

Answer 3

в 5 раз быстрее уменьшить вариант, но более изощренно

>>> l = [5, 6, 6, 1, 1, 2, 2, 3, 4]
>>> 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())
# use 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]
[5, 6, 1, 2, 3, 4]

Answer 4

Ответ MizardX дает хорошую коллекцию нескольких подходов.

Вот что я придумал, думая вслух:

mylist = [x for i,x in enumerate(mylist) if x not in mylist[i+1:]]

Answer 5

Вы можете ссылаться на понимание списка, поскольку оно строится символом '_ [1]'.
Например, следующая функция unique-if показывает список элементов без изменения их порядка, ссылаясь на его понимание списка.

def unique(my_list): 
    return [x for x in my_list if x not in locals()['_[1]']]

Демо-версия:

l1 = [1, 2, 3, 4, 1, 2, 3, 4, 5]
l2 = [x for x in l1 if x not in locals()['_[1]']]
print l2

Выход:

[1, 2, 3, 4, 5]

Answer 6

Простое рекурсивное решение:

def uniquefy_list(a):
    return uniquefy_list(a[1:]) if a[0] in a[1:] else [a[0]]+uniquefy_list(a[1:]) if len(a)>1 else [a[0]]

Answer 7

l = [1,2,2,3,3,...]
n = []
n.extend(ele for ele in l if ele not in set(n))

Генераторное выражение, которое использует поиск O (1) набора, чтобы определить, следует ли включать элемент в новый список.

Answer 8

Относительно эффективный подход с _sorted_ a numpy массивами:

b = np.array([1,3,3, 8, 12, 12,12])    
numpy.hstack([b[0], [x[0] for x in zip(b[1:], b[:-1]) if x[0]!=x[1]]])

Выходы:

array([ 1,  3,  8, 12])

Answer 9

Вы могли бы сделать что-то вроде уродливого хака для понимания списка.

[l[i] for i in range(len(l)) if l.index(l[i]) == i]

Answer 10

Устранение повторяющихся значений в последовательности, но сохранение порядка оставшихся элементов. Использование функции генератора общего назначения.

# for hashable sequence
def remove_duplicates(items):
    seen = set()
    for item in items:
        if item not in seen:
            yield item
            seen.add(item)

a = [1, 5, 2, 1, 9, 1, 5, 10]
list(remove_duplicates(a))
# [1, 5, 2, 9, 10]



# for unhashable sequence
def remove_duplicates(items, key=None):
    seen = set()
    for item in items:
        val = item if key is None else key(item)
        if val not in seen:
            yield item
            seen.add(val)

a = [ {'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 1, 'y': 2}, {'x': 2, 'y': 4}]
list(remove_duplicates(a, key=lambda d: (d['x'],d['y'])))
# [{'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 2, 'y': 4}]