В Python, какой самый быстрый алгоритм удаления дубликатов из списка, чтобы все элементы были уникальными * при сохранении порядка *?
Например:
>>> x = [1, 1, 2, 'a', 'a', 3]
>>> unique(x)
[1, 2, 'a', 3]
Предположим, элементы списка могут быть хэшируемыми.
Пояснение: результат должен сохранить первый дубликат в списке. Например, [1, 2, 3, 2, 3, 1] становится [1, 2, 3].
27 ответов
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])
С помощью:
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)'
И так далее для различных других функций (которые я назвал в честь их плакатов), у меня есть следующие результаты (на моем первом 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 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.
То, что будет самым быстрым, зависит от того, какой процент вашего списка дубликатов. Если это почти все дубликаты с несколькими уникальными элементами, создание нового списка, вероятно, будет быстрее. Если это в основном уникальные предметы, удаление их из исходного списка (или копии) будет быстрее.
Вот один для изменения списка на месте:
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)
Итерация в обратном направлении по индексам гарантирует, что удаление элементов не повлияет на итерацию.
Это самый быстрый метод на месте, который я нашел (при условии большой доли дубликатов):
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: Мне было бы интересно, если бы вы могли подтвердить мои сроки.
Это может быть самый простой способ:
list(OrderedDict.fromkeys(iterable))
Начиная с Python 3.5, OrderedDict теперь реализован на C, поэтому он стал самым коротким, чистым и быстрым.
Обязательный генераторный вариант:
def unique(seq):
seen = set()
for x in seq:
if x not in seen:
seen.add(x)
yield x
Один лайнер:
new_list = reduce(lambda x,y: x+[y][:1-int(y in x)], my_list, [])
Взято с 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
Это самый быстрый способ, сравнивающий все материалы из этого длительного обсуждения и других ответов, приведенных здесь, со ссылкой на этот тест. Это еще на 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 = [1, 1, 2, 'a', 'a', 3]
>>> [ item for pos,item in enumerate(x) if x.index(item)==pos ]
[1, 2, '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()]
Удалить дубликаты и сохранить порядок:
Это быстрый 2-х строчный режим, использующий встроенную функциональность списков и диктов.
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 будет работать для максимизации эффективности процесса.
Обязательно ли дубликаты должны быть в списке в первую очередь? Нет затрат на поиск элементов, но есть немного больше на добавление элементов (хотя это должно быть 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
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
Вот два рецепта из документации 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)))
Здесь есть несколько отличных, эффективных решений. Тем не менее, для тех, кто не обеспокоен абсолютным наиболее эффективным 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])
У меня нет опыта работы с python, но алгоритм должен был бы отсортировать список, затем удалить дубликаты (путем сравнения с предыдущими элементами в списке) и, наконец, найти позицию в новом списке, сравнивая со старым списком.
Более длинный ответ: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52560
Если вы уберете пустой список из вызова set () в ответе Terhost, вы получите небольшое повышение скорости.
Изменение: найдено = установлено ([])
to: 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
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
>>> def unique(list):
... y = []
... for x in list:
... if x not in y:
... y.append(x)
... return y
>>> 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]']" - это "секретное имя" создаваемого списка.
Я не знаю, быстро это или нет, но, по крайней мере, все просто.
Просто преобразуйте его сначала в набор, а затем снова в список
def unique(container):
return list(set(container))
Я не проводил никаких тестов, но одним из возможных алгоритмов могло бы быть создание второго списка и итерация по первому списку. Если элемент отсутствует во втором списке, добавьте его во второй список.
x = [1, 1, 2, 'a', 'a', 3]
y = []
for each in x:
if each not in y:
y.append(each)
А =[1,2,3,4,5,7,7,8,8,9,9,3,45]
уникальность определения (л):
ids={}
for item in l:
if not ids.has_key(item):
ids[item]=item
return ids.keys()
распечатать
печать уникальная (а)
----------------------------
Для вставки элементов потребуется получение тета (n), если элемент выходит или нет, потребуется постоянное время для тестирования всех элементов, а также тэта (n), поэтому мы можем видеть, что это решение будет принимать тэта (п) Медведь в уме этот словарь в python реализуется хеш-таблицей
Один проход
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