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

Question

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

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

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

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

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

Answer 1

Метод на месте

Этот метод является квадратичным, потому что у нас есть линейный поиск в списке для каждого элемента списка (к этому мы должны добавить стоимость переупорядочения списка из-за del s).

Тем не менее, можно работать на месте, если мы начнем с конца списка и продолжим в направлении источника, удаляя каждый термин, который присутствует в подсписке слева

Эта идея в коде просто

for i in range(len(l)-1,0,-1): 
    if l[i] in l[:i]: del l[i] 

---

Простой тест реализации

In [91]: from random import randint, seed                                                                                            
In [92]: seed('20080808') ; l = [randint(1,6) for _ in range(12)] # Beijing Olympics                                                                 
In [93]: for i in range(len(l)-1,0,-1): 
    ...:     print(l) 
    ...:     print(i, l[i], l[:i], end='') 
    ...:     if l[i] in l[:i]: 
    ...:          print( ': remove', l[i]) 
    ...:          del l[i] 
    ...:     else: 
    ...:          print() 
    ...: print(l)
[6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5, 2]
11 2 [6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5]: remove 2
[6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5]
10 5 [6, 5, 1, 4, 6, 1, 6, 2, 2, 4]: remove 5
[6, 5, 1, 4, 6, 1, 6, 2, 2, 4]
9 4 [6, 5, 1, 4, 6, 1, 6, 2, 2]: remove 4
[6, 5, 1, 4, 6, 1, 6, 2, 2]
8 2 [6, 5, 1, 4, 6, 1, 6, 2]: remove 2
[6, 5, 1, 4, 6, 1, 6, 2]
7 2 [6, 5, 1, 4, 6, 1, 6]
[6, 5, 1, 4, 6, 1, 6, 2]
6 6 [6, 5, 1, 4, 6, 1]: remove 6
[6, 5, 1, 4, 6, 1, 2]
5 1 [6, 5, 1, 4, 6]: remove 1
[6, 5, 1, 4, 6, 2]
4 6 [6, 5, 1, 4]: remove 6
[6, 5, 1, 4, 2]
3 4 [6, 5, 1]
[6, 5, 1, 4, 2]
2 1 [6, 5]
[6, 5, 1, 4, 2]
1 5 [6]
[6, 5, 1, 4, 2]

In [94]:                                                                                                                             

Answer 2

Если вам нужен один лайнер, возможно, это поможет:

reduce(lambda x, y: x + y if y[0] not in x else x, map(lambda x: [x],lst))

... должно работать, но поправьте меня, если я ошибаюсь

Answer 3

Если вы обычно используете pandas, а эстетика предпочтительнее производительности, тогда рассмотрите встроенную функцию pandas.Series.drop_duplicates:

    import pandas as pd
    import numpy as np

    uniquifier = lambda alist: pd.Series(alist).drop_duplicates().tolist()

    # from the chosen answer 
    def f7(seq):
        seen = set()
        seen_add = seen.add
        return [ x for x in seq if not (x in seen or seen_add(x))]

    alist = np.random.randint(low=0, high=1000, size=10000).tolist()

    print uniquifier(alist) == f7(alist)  # True

Сроки:

    In [104]: %timeit f7(alist)
    1000 loops, best of 3: 1.3 ms per loop
    In [110]: %timeit uniquifier(alist)
    100 loops, best of 3: 4.39 ms per loop

Answer 4

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

def deduplicate(l):
    count = {}
    (read,write) = (0,0)
    while read < len(l):
        if l[read] in count:
            read += 1
            continue
        count[l[read]] = True
        l[write] = l[read]
        read += 1
        write += 1
    return l[0:write]

Answer 5

Решение без использования импортированных модулей или наборов:

text = "ask not what your country can do for you ask what you can do for your country"
sentence = text.split(" ")
noduplicates = [(sentence[i]) for i in range (0,len(sentence)) if sentence[i] not in sentence[:i]]
print(noduplicates)

Дает вывод:

['ask', 'not', 'what', 'your', 'country', 'can', 'do', 'for', 'you']