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

Более длинный ответ: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52560

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

x = [1, 1, 2, 'a', 'a', 3]
y = []
for each in x:
    if each not in y:
        y.append(each)

Взято из http://www.peterbe.com/plog/uniqifiers-benchmark

def f5(seq, idfun=None):  
    # order preserving 
    if idfun is None: 
        def idfun(x): return x 
    seen = {} 
    result = [] 
    for item in seq: 
        marker = idfun(item) 
        # in old Python versions: 
        # if seen.has_key(marker) 
        # but in new ones: 
        if marker in seen: continue 
        seen[marker] = 1 
        result.append(item) 
    return result

>>> def unique(list):
...   y = []
...   for x in list:
...     if x not in y:
...       y.append(x)
...   return y

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

Вот один для изменения списка на месте:

def unique(items):
  seen = set()
  for i in xrange(len(items)-1, -1, -1):
    it = items[i]
    if it in seen:
      del items[i]
    else:
      seen.add(it)

Итерация в обратном направлении по индексам гарантирует, что удаление элементов не повлияет на итерацию.

O (n), если dict - хэш, O (nlogn), если dict - дерево, и простой, фиксированный. Спасибо Мэтью за предложение. Извините, я не знаю основных типов.

def unique(x):    
  output = []
  y = {}
  for item in x:
    y[item] = ""

  for item in x:
    if item in y:
      output.append(item)

  return output

def unique(items):
    found = set([])
    keep = []

    for item in items:
        if item not in found:
            found.add(item)
            keep.append(item)

    return keep

print unique([1, 1, 2, 'a', 'a', 3])

Вы можете сделать что-то действительно классное на Python, чтобы решить эту проблему. Вы можете создать понимание списка, которое будет ссылаться на себя при создании. Следующее:

   # remove duplicates...
   def unique(my_list):
       return [x for x in my_list if x not in locals()['_[1]'].__self__]

Обновлено: Я удалил "себя", и он работает в Mac OS X, Python 2.5.1.

_ [1] - это «секретная» ссылка Python на новый список. Вышеизложенное, конечно, немного беспорядочно, но вы можете адаптировать его под свои нужды по мере необходимости. Например, вы можете написать функцию, которая возвращает ссылку на понимание; это было бы больше похоже на:

return [x for x in my_list if x not in this_list()]

>>> x=[1,1,2,'a','a',3]
>>> y = [ _x for _x in x if not _x in locals()['_[1]'] ]
>>> y
[1, 2, 'a', 3]

"locals () ['_ [1]']" - это "секретное имя" создаваемого списка.

Один лайнер:

new_list = reduce(lambda x,y: x+[y][:1-int(y in x)], my_list, [])

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

>>> x  = []
>>> y = set()
>>> def add_to_x(val):
...     if val not in y:
...             x.append(val)
...             y.add(val)
...     print x
...     print y
... 
>>> add_to_x(1)
[1]
set([1])
>>> add_to_x(1)
[1]
set([1])
>>> add_to_x(1)
[1]
set([1])
>>> 

has_key в Python - O (1). Вставка и извлечение из хэша также O (1). Дважды перебирает n элементов, поэтому O (n).

def unique(list):
  s = {}
  output = []
  for x in list:
    count = 1
    if (s.has_key(x)):
      count = s[x] + 1

    s[x] = count
  for x in list:
    count = s[x]
    if (count > 0):
      s[x] = 0
      output.append(x)
  return output

Один проход.

a = [1,1,'a','b','c','c']

new_list = []
prev = None

while 1:
    try:
        i = a.pop(0)
        if i != prev:
            new_list.append(i)
        prev = i
    except IndexError:
        break

С помощью:

lst = [8, 8, 9, 9, 7, 15, 15, 2, 20, 13, 2, 24, 6, 11, 7, 12, 4, 10, 18, 13, 23, 11, 3, 11, 12, 10, 4, 5, 4, 22, 6, 3, 19, 14, 21, 11, 1, 5, 14, 8, 0, 1, 16, 5, 10, 13, 17, 1, 16, 17, 12, 6, 10, 0, 3, 9, 9, 3, 7, 7, 6, 6, 7, 5, 14, 18, 12, 19, 2, 8, 9, 0, 8, 4, 5]

И используя модуль timeit:

$ python -m timeit -s 'import uniquetest' 'uniquetest.etchasketch(uniquetest.lst)'

И так далее для различных других функций (которые я назвал в честь их плакатов), у меня были следующие результаты (на моем Intel MacBook Pro первого поколения):

Allen:                  14.6 µs per loop [1]
Terhorst:               26.6 µs per loop
Tarle:                  44.7 µs per loop
ctcherry:               44.8 µs per loop
Etchasketch 1 (short):  64.6 µs per loop
Schinckel:              65.0 µs per loop
Etchasketch 2:          71.6 µs per loop
Little:                 89.4 µs per loop
Tyler:                 179.0 µs per loop

[1] Обратите внимание, что Аллен изменяет список на месте - я считаю, что это исказило время, поскольку модуль timeit запускает код 100000 раз, и 99999 из них находятся в списке без дублирования.

Резюме: Прямая реализация с наборами побеждает запутанные однострочники :-)

Не знаю, быстро это или нет, но, по крайней мере, все просто.

Просто преобразуйте его сначала в набор, а затем снова в список

def unique(container):
  return list(set(container))

Это самый быстрый метод на месте, который я нашел (при наличии большого количества дубликатов):

def unique(l):
    s = set(); n = 0
    for x in l:
        if x not in s: s.add(x); l[n] = x; n += 1
    del l[n:]

Это на 10% быстрее, чем реализация Аллена, на которой она основана (синхронизировано с timeit.repeat, JIT скомпилировано psyco). Он сохраняет первый экземпляр любого дубликата.

repton-infinity: Мне было бы интересно, можете ли вы подтвердить мои сроки.

Здесь есть несколько отличных и эффективных решений. Однако для тех, кто не интересуется самым эффективным решением O(n), я бы выбрал простое однострочное решение O(n^2*log(n)):

def unique(xs):
    return sorted(set(xs), key=lambda x: xs.index(x))

или более эффективное двухслойное решение O(n*log(n)):

def unique(xs):
    positions = dict((e,pos) for pos,e in reversed(list(enumerate(xs))))
    return sorted(set(xs), key=lambda x: positions[x])

Если вы удалите пустой список из вызова set () в ответе Terhost, вы получите небольшой прирост скорости.

Изменять: found = set ([])
к: найдено = набор ()

Однако вам совсем не нужен набор.

def unique(items):
    keep = []

    for item in items:
        if item not in keep:
            keep.append(item)

    return keep

Используя timeit, я получил следующие результаты:

с комплектом ([]) - 4.97210427363
с комплектом () - 4.65712377445
без набора - 3,44865284975

Обязательная вариация на базе генератора:

def unique(seq):
  seen = set()
  for x in seq:
    if x not in seen:
      seen.add(x)
      yield x

a = [1,2,3,4,5,7,7,8,8,9,9,3,45]

def unique (l):

ids = {}
for item in l:
    if not ids.has_key(item):
        ids[item]=item
return  ids.keys()

распечатать

распечатать уникальный (а)

----------------------------

Вставка элементов займет theta (n) получение, если элемент выходит или нет, займет постоянное время тестирование всех предметов потребует также тета (n) Итак, мы можем видеть, что это решение будет принимать theta (n) Имейте в виду, что словарь в Python реализован с помощью хеш-таблицы

Обновлять: на Python3.7 +:

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

^{old answer:}

Вот самое быстрое решение (для следующего ввода):

def del_dups(seq):
    seen = {}
    pos = 0
    for item in seq:
        if item not in seen:
            seen[item] = True
            seq[pos] = item
            pos += 1
    del seq[pos:]

lst = [8, 8, 9, 9, 7, 15, 15, 2, 20, 13, 2, 24, 6, 11, 7, 12, 4, 10, 18, 
       13, 23, 11, 3, 11, 12, 10, 4, 5, 4, 22, 6, 3, 19, 14, 21, 11, 1, 
       5, 14, 8, 0, 1, 16, 5, 10, 13, 17, 1, 16, 17, 12, 6, 10, 0, 3, 9, 
       9, 3, 7, 7, 6, 6, 7, 5, 14, 18, 12, 19, 2, 8, 9, 0, 8, 4, 5]
del_dups(lst)
print(lst)
# -> [8, 9, 7, 15, 2, 20, 13, 24, 6, 11, 12, 4, 10, 18, 23, 3, 5, 22, 19, 14, 
#     21, 1, 0, 16, 17]

Поиск в словаре выполняется немного быстрее, чем в Python 3.

На месте однострочник для этого:

>>> x = [1, 1, 2, 'a', 'a', 3]
>>> [ item for pos,item in enumerate(x) if x.index(item)==pos ]
[1, 2, 'a', 3]

Удалите дубликаты и сохраните порядок:

Это быстрый двухстрочный редактор, который использует встроенные функции понимания списков и словарных статей.

x = [1, 1, 2, 'a', 'a', 3]

tmpUniq = {} # temp variable used below 
results = [tmpUniq.setdefault(i,i) for i in x if i not in tmpUniq]

print results
[1, 2, 'a', 3]

Функция dict.setdefaults () возвращает значение, а также добавляет его к temp dict непосредственно в понимании списка. Использование встроенных функций и хэшей dict будет работать для максимальной эффективности процесса.

Вот два рецепта из документации itertools:

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

def unique_justseen(iterable, key=None):
    "List unique elements, preserving order. Remember only the element just seen."
    # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B
    # unique_justseen('ABBCcAD', str.lower) --> A B C A D
    return imap(next, imap(itemgetter(1), groupby(iterable, key)))

Это может быть самый простой способ:

list(OrderedDict.fromkeys(iterable))

Начиная с Python 3.5, OrderedDict теперь реализован на C, поэтому он стал самым коротким, чистым и быстрым.

Это самый быстрый, сравнивая все материалы из этого длительное обсуждение и других ответов, приведенных здесь, со ссылкой на этот ориентир. Это еще на 25% быстрее, чем самая быстрая функция из обсуждаемых, f8. Спасибо Дэвиду Кирби за идею.

def uniquify(seq):
    seen = set()
    seen_add = seen.add
    return [x for x in seq if x not in seen and not seen_add(x)]

Некоторое сравнение времени:

$ python uniqifiers_benchmark.py 
* f8_original 3.76
* uniquify 3.0
* terhorst 5.44
* terhorst_localref 4.08
* del_dups 4.76

x = [] # Your list  of items that includes Duplicates

# Assuming that your list contains items of only immutable data types

dict_x = {} 

dict_x = {item : item for i, item in enumerate(x) if item not in dict_x.keys()}
# Average t.c. = O(n)* O(1) ; furthermore the dict comphrehension and generator like behaviour of enumerate adds a certain efficiency and pythonic feel to it.

x = dict_x.keys() # if you want your output in list format