Упорядоченные множества Python 2.7

Question

У меня есть список, из которого я пытаюсь удалить дубликаты. Я использую Python 2.7.1, поэтому я могу просто использовать функцию set () . Однако это меняет мой список. Что для моего конкретного случая неприемлемо.

Ниже приведена функция, которую я написал; который делает это. Однако мне интересно, есть ли лучший / более быстрый способ. Также любые комментарии по этому поводу будут оценены.

    def ordered_set(list_):

        newlist = []
        lastitem = None
        for item in list_:

            if item != lastitem:
                newlist.append(item)
                lastitem = item

        return newlist

Вышеупомянутая функция предполагает, что ни один из элементов не будет Нет , и что элементы расположены по порядку (т. Е. ['a', 'a', 'a', 'b ',' b ',' c ',' d '] )

Данная функция возвращает ['a', 'a', 'a', 'b', 'b', 'c', 'd'] как ['a' , 'b', 'c', 'd'] .

Answer 1

Еще один очень быстрый метод с набором:

def remove_duplicates(lst):
    dset = set()
    # relies on the fact that dset.add() always returns None.
    return [item for item in lst
            if item not in dset and not dset.add(item)] 

Answer 2

Используйте OrderedDict:

from collections import OrderedDict

l = ['a', 'a', 'a', 'b', 'b', 'c', 'd']
d = OrderedDict()

for x in l:
    d[x] = True

# prints a b c d
for x in d:
    print x,
print

Answer 3

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

>>> def remove_dups_stable(s):
...   seen = set()
...   for i in s:
...     if i not in seen:
...       yield i
...       seen.add(i)

>>> list(remove_dups_stable(['q', 'w', 'e', 'r', 'q', 'w', 'y', 'u', 'i', 't', 'e', 'p', 't', 'y', 'e']))
['q', 'w', 'e', 'r', 'y', 'u', 'i', 't', 'p']

Answer 4

Я знаю, что на этот вопрос уже дан ответ, но вот одна строка (плюс импорт):

from collections import OrderedDict
def dedupe(_list):
    return OrderedDict((item,None) for item in _list).keys()

>>> dedupe(['q', 'w', 'e', 'r', 'q', 'w', 'y', 'u', 'i', 't', 'e', 'p', 't', 'y', 'e'])
['q', 'w', 'e', 'r', 'y', 'u', 'i', 't', 'p']

Answer 5

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

Если бы список был неупорядоченным, то вам понадобился бы помощник set, чтобы содержать элементы, которые вы уже посетили, но в вашем случае это не обязательно.

Answer 6

Существует уникальное решение, описанное в http://docs.python.org/2/library/itertools.html

def unique_everseen(iterable, key=None):
    "List unique elements, preserving order. Remember all elements ever seen."
    # unique_everseen('AAAABBBCCDAABBB') --> A B C D
    # unique_everseen('ABBCcAD', str.lower) --> A B C D
    seen = set()
    seen_add = seen.add
    if key is None:
        for element in ifilterfalse(seen.__contains__, iterable):
            seen_add(element)
            yield element
    else:
        for element in iterable:
            k = key(element)
            if k not in seen:
                seen_add(k)
                yield element

Answer 7

если ваш список не отсортирован, тогда ваш вопрос не имеет смысла.например, [1,2,1] может стать [1,2] или [2,1]

, если ваш список большой, вы можете записать свой результат обратно в тот же список, используя SLICEчтобы сохранить в памяти :

>>> x=['a', 'a', 'a', 'b', 'b', 'c', 'd']
>>> x[:]=[x[i] for i in range(len(x)) if i==0 or x[i]!=x[i-1]]
>>> x
['a', 'b', 'c', 'd']

для встроенного удаления см. Удаление элементов из списка при повторении или Удаление элементов из списка при повторении без использования дополнительной памяти вPython

один прием, который вы можете использовать, заключается в том, что если вы знаете, что x отсортирован, и знаете, что x [i] = x [i + j], то вам не нужно ничего проверять между x [i] и x [i + j] (и если вам не нужно удалять эти значения j, вы можете просто скопировать нужные значения в новый список)

Так что пока вы не можете разбить nоперации, если все в наборе уникально, т. е. len (set (x)) = len (x). Вероятно, существует алгоритм, который имеет n сравнений в худшем случае, но может иметь n / 2 сравнений в качестве наилучшего (или ниже n)./ 2 в лучшем случае, если вы как-то знаете, заранее знаете, что len (x) / len (set (x))> 2 из-за сгенерированных вами данных):

оптимальный алгоритм, вероятно, будет использовать бинарный поиск, чтобы найти максимум j для каждого минимума i в подходе типа «разделяй и властвуй».Начальные деления, вероятно, будут иметь длину len (x) / приблизительную (len (set (x))).Надеюсь, это можно сделать так, что даже если len (x) = len (set (x)), он все равно использует только n операций.

Answer 8

Выглядит нормально для меня. Если вы действительно хотите использовать наборы, сделайте что-то вроде этого:

def ordered_set (_list) :
    result = set()
    lastitem = None
    for item in _list :
        if item != lastitem :
            result.add(item)
            lastitem = item
    return sorted(tuple(result))

Я не знаю, какую производительность вы получите, вы должны проверить это; вероятно, то же самое из-за перегрева метода!

Если вы действительно параноик, как и я, читайте здесь:

http://wiki.python.org/moin/HowTo/Sorting/

http://wiki.python.org/moin/PythonSpeed/PerformanceTips

Только что вспомнил (содержит ответ):

http://www.peterbe.com/plog/uniqifiers-benchmark