Python: найти дубликат в контейнере эффективно

Question

У меня есть контейнер cont.Если я хочу выяснить, есть ли у него дубликаты, я просто проверю len(cont) == len(set(cont)).

Предположим, я хочу найти дубликат элемента, если он существует (просто любой произвольный дубликат элемента).Есть ли какой-нибудь аккуратный и эффективный способ написать это?

[Python 3]

Answer 1

Вы можете начать добавлять их в набор, и как только вы попытаетесь добавить элемент, который уже находится в наборе, вы найдете дубликат.

Answer 2

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

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 в его реализации), являющимися секундой закрытия.

---

Обновление: я попробовал предложение распейции, и кроме того факта, что вам нужно точно знать, какой дублирующий ключ вы ищете, реальный алгоритм пока что хуже всего (66,366 с).

---

Обновление 2: я уверен, что кто-то скажет, что этот тест необъективен, поскольку дублирующее местоположение находится рядом с одним концом списка. Попробуйте запустить код в другом месте, прежде чем понижать голосование, и сообщите о своих результатах!

Answer 3

Не ясно, какой смысл находить один произвольный элемент, который является дубликатом, или один или несколько других элементов коллекции ... вы хотите удалить его?объединить его атрибуты с атрибутами его близнецов / триплетов / ... / N-tuplets?В любом случае, это операция O (N), которая, если она повторяется до тех пор, пока больше не будут обнаружены дубликаты, является операцией O (N ** 2).

Однако вы можете получить оптовую сделку на складе алгоритма:отсортируйте коллекцию - O (N * log (N)) - и затем используйте itertools.groupby, чтобы собрать дубликаты и пройтись по группам, игнорируя пакеты размера 1 и делая все, что вы хотите с пакетами размера>1 - все это только о O (N).

Answer 4

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")

Answer 5

Другие предложения, похожие на ответ Джонси.По крайней мере, в 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

Answer 6

Согласно http://wiki.python.org/moin/TimeComplexity большинство операций со списками ужасно неэффективны (только что подтвердили, что x in myList в python3 * O(N)).

Метод, данный оригинальным постером , эффективен , потому что это 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: Существуют способы повышения эффективности использования пространства для незначительного снижения эффективности времени (например, фильтры Блума).

Answer 7

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

>>> l = [1,1,2,3]
>>> l.count(1)
2
>>> 

В словаре не может быть дубликатов ключейи не может набор.Помимо этого, мне нужно знать, что это за контейнер.Я предполагаю, что реальная цель - всегда убедиться, что вы не пропустили очевидное решение проблемы, прежде чем приступить к написанию собственного решения.Я сам становлюсь жертвой этого иногда :)

Answer 8

Попробуйте это:

def getFirstDup(cont):
    for i in xrange(0, len(cont)):
        if cont[i] in cont[:i]:
            return cont[i]
    return None

Answer 9

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

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