Каков самый быстрый способ добавить данные в список без дублирования в python (2.5)

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

if Item in List:
    ItemNumber=List.index(Item)
else:
    List.append(Item)
    ItemNumber=List.index(Item)

Проблема заключается в том, что по мере роста списка он становится все медленнее, пока в какой-то момент это просто не стоит делать. Я ограничен python 2.5, потому что это встроенная система.

Ответы

Ответ 1

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

Выполнение поиска с помощью набора приведет к удалению служебных данных if Item in List, но не к List.index(Item)

Обратите внимание, что ItemNumber=List.index(Item) будет очень неэффективным после List.append(Item). Вы знаете длину списка, поэтому ваш индекс можно получить с помощью ItemNumber = len(List)-1.

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

Я могу переписать его следующим образом:

# earlier in the program, NOT inside the loop
Dup = {}

# inside your loop to add items:
if Item in Dup:
    ItemNumber = Dup[Item]
else:
    List.append(Item)
    Dup[Item] = ItemNumber = len(List)-1

Ответ 2

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

existing = dict()
if Item in existing:
    ItemNumber = existing[Item]
else:
    ItemNumber = existing[Item] = len(List)
    List.append(Item)

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

Items = set()
# ...
Items.add(Item) # will do nothing if Item is already added

Оба из них требуют, чтобы ваш объект был хешируемым. В Python большинство типов хешируются, если они не являются контейнером, содержимое которого может быть изменено. Например: list не хешируются, потому что вы можете изменить их содержимое, но tuple хешируются, потому что вы не можете.

Если вы пытались сохранить значения, которые не хешируются, не существует быстрого общего решения.

Ответ 3

Вы можете улучшить проверку:

check = set(List)

for Item in NewList:
    if Item in check: ItemNumber = List.index(Item)
    else:
        ItemNumber = len(List)
        List.append(Item)

Или, еще лучше, если порядок не важен, вы можете сделать это:

oldlist = set(List)
addlist = set(AddList)
newlist = list(oldlist | addlist)

И если вам нужно перебрать элементы, которые были дублированы:

for item in (oldlist & addlist):
    pass # do stuff

Ответ 4

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

Помогает ли этот ответ указывать вам время на обмен времени/памяти, о котором я говорю? Я могу помочь прояснить больше, если вы захотите.