У меня есть контейнер cont. Если я хочу узнать, есть ли у него дубликаты, я просто проверю len(cont) == len(set(cont)).
Предположим, что я хочу найти дублирующий элемент, если он существует (только любой произвольный повторяющийся элемент). Есть ли опрятный и эффективный способ написать это?
[Python 3]
Хорошо, мой первый ответ получил довольно много хлопот, поэтому я подумал, что попробую несколько разных способов сделать это и сообщить о различиях. Вот мой код.
import sys
import itertools
def getFirstDup(c, toTest):
# Original idea using list slicing => 5.014 s
if toTest == '1':
for i in xrange(0, len(c)):
if c[i] in c[:i]:
return c[i]
# Using two sets => 4.305 s
elif toTest == '2':
s = set()
for i in c:
s2 = s.copy()
s.add(i)
if len(s) == len(s2):
return i
# Using dictionary LUT => 0.763 s
elif toTest == '3':
d = {}
for i in c:
if i in d:
return i
else:
d[i] = 1
# Using set operations => 0.772 s
elif toTest == '4':
s = set()
for i in c:
if i in s:
return i
else:
s.add(i)
# Sorting then walking => 5.130 s
elif toTest == '5':
c = sorted(c)
for i in xrange(1, len(c)):
if c[i] == c[i - 1]:
return c[i]
# Sorting then groupby-ing => 5.086 s
else:
c = sorted(c)
for k, g in itertools.groupby(c):
if len(list(g)) > 1:
return k
return None
c = list(xrange(0, 10000000))
c[5000] = 0
for i in xrange(0, 10):
print getFirstDup(c, sys.argv[1])
В принципе, я пробую это по-разному, как указано в исходном файле. Я использовал команду Linux time и собрал время выполнения в реальном времени, выполнив такие команды
time python ./test.py 1
с 1, являющимся тем алгоритмом, который я хотел попробовать. Каждый алгоритм ищет первый дубликат в 10 000 000 целых чисел и работает десять раз. В списке есть одно дублирование, которое "в основном отсортировано", хотя я попытался отсортировать отсортированные списки, не заметив пропорциональной разницы между алгоритмами.
Мое первоначальное предложение плохо сделало в 5.014 с. Мое понимание решения icyrock.com также плохо выполнялось в 4.305 с. Затем я попытался использовать словарь для создания LUT, который дал лучшее время исполнения в 0.763 с. Я попытался использовать оператор in на наборах и получил 0.772 с, почти так же хорошо, как словарь LUT. Я пробовал сортировать и ходить по списку, что давало жалкое время 5.130 с. Наконец, я попробовал предложение Джона Мачина об itertools, что дало плохое время 5.086 с.
Таким образом, словаря LUT, как представляется, является способом перехода, при этом операции установки (которые могут использовать LUT в его реализации) являются близкими секундами.
Обновление: я попробовал предложение razpeitia, и кроме того, что вам нужно точно знать, какой дублирующий ключ вы ищете, фактический алгоритм сделал наихудшее до сих пор (66.366 с).
Обновление 2: я уверен, что кто-то скажет, что этот тест является предвзятым, потому что дублирующее местоположение находится рядом с одним концом списка. Попробуйте запустить код, используя другое место, перед тем, как выполнить downvoting и сообщите о своих результатах!
Вы можете начать добавлять их в набор, и как только вы попытаетесь добавить элемент, который уже находится в наборе, вы нашли дубликат.
Не ясно, что точка нахождения одного произвольного элемента, который является дубликатом или одним или несколькими другими элементами коллекции... вы хотите удалить его? объединить его атрибуты с атрибутами своих близнецов/триплетов/.../N-tuplets? В любом случае, операция O (N), которая, если она повторяется до тех пор, пока не будет обнаружена больше дубликатов, является операцией O (N ** 2).
Однако вы можете получить крупную сделку на складе алгоритмов: сортировать коллекцию - O (N * log (N)), а затем использовать itertools.groupby для группировки дубликатов и круиза по пучкам, игнорируя сгустки размером 1 и делать все, что вам нужно, с пучками размером > 1 - все это только около O (N).
from collections import Counter
cont = [1, 2, 3]
c = Counter(cont)
x = someItem
if c[x] == 0:
print("Not in cont")
elif c[x] == 1:
print("Unique")
else:
print("Duplicate")
Вам нужно отсканировать все элементы для дубликатов, поскольку они могут быть только последними, которые вы проверяете, поэтому вы не можете получить более эффективное, чем наихудшее время O (N), как и линейный поиск. Но простой линейный поиск для поиска дубликата будет использовать память O (N), потому что вам нужно отслеживать, что вы видели до сих пор.
Если массив отсортирован, вы можете найти дубликаты в O (N) времени без использования дополнительной памяти, поскольку повторяющиеся пары будут рядом друг с другом.
Если ваш контейнер представляет собой список, вы можете просто передать значение, которое вы ищете для метода count(), и проверить результат:
>>> l = [1,1,2,3]
>>> l.count(1)
2
>>>
Словарь не может иметь повторяющиеся ключи и не может быть установлен. Вне этого мне нужно было бы знать, какой контейнер это. Я предполагаю, что реальный момент - всегда следить за тем, чтобы вы не пропустили очевидное решение проблемы, прежде чем приступать к кодированию пользовательского решения. Я иногда становлюсь жертвой этого.
В соответствии с http://wiki.python.org/moin/TimeComplexity большинство операций с списками ужасно неэффективны (просто подтвердили, что x in myList кажется O(N) в python3).
Метод, заданный исходным плакатом , эффективен, потому что это O (N) время и пространство (это "лучший" вы можете, не делая дополнительных предположений о вашем списке, поскольку операции с списками например x in myList O(N)).
Существует большая оптимизация, которая позволяет итеративно наращивать набор. Это быстро вернется к определенным спискам, например. [0,1,1,2,3,4,5,...]. Однако вы неявно принимаете немного о распределении своих списков (например, вы оптимизируете для этого случая или оптимизируете дубликаты в конце или оба?). Хорошая вещь об этой оптимизации заключается в том, что она не влияет на асимптотическую скорость. Здесь, как я бы его кодировал элегантно:
def hasDuplicate(iter):
visited = set()
for item in iter:
if item in visited:
return True
visited.add(item)
return False
Вы также можете вернуть первый дубликат, но вы не можете вернуть None; вам придется поднять исключение, так как итеративный может содержать None.
sidenote: Есть способы улучшить космическую эффективность для незначительного удара по эффективности времени (например, фильтры цветения).
Другие предложения, похожие на jonesy ответ. По крайней мере, в python3 (не тестировались в python 2.7), когда c [-5000] = 0, это становится быстрее, чем решение 3 и 4 исходного ответа. В противном случае он только немного быстрее, чем решение 1 и 2...
elif toTest == '7':
for i in c:
if c.count(i)>1:
return i
Попробуйте следующее:
def getFirstDup(cont):
for i in xrange(0, len(cont)):
if cont[i] in cont[:i]:
return cont[i]
return None