在Python中最快的去重添加数据到列表的方法是什么（2.5）

Question

我有大约五十万个物品需要放到一个列表里，不能有重复的，如果某个物品已经在列表里了，我还需要知道它的位置。目前我有了这个：

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

问题是，随着列表的变大，查找的速度会越来越慢，直到某个时候根本就不值得继续这样做。我只能用Python 2.5，因为这是一个嵌入式系统。

Answer 1

你可以大大改善这个检查的方式：

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

Answer 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（元组）是可哈希的，因为你不能修改它们。

如果你想存储一些不可哈希的值，那就没有一个快速的通用解决方案。

Answer 3

你可以使用一个叫做 集合 的东西（从CPython 2.4版本开始就有了）来高效地查找重复的值。如果你真的需要一个有序的系统，可以同时使用集合和列表。

用集合来查找会比用 if Item in List 这种方式更快，但对于 List.index(Item) 这种方法来说，速度还是会慢一些。

请注意，使用 ItemNumber=List.index(Item) 在你刚用 List.append(Item) 添加了新项后会非常低效。因为你知道列表的长度，所以可以用 ItemNumber = len(List)-1 来直接获取索引。

为了完全消除使用 List.index 的低效（因为这个方法会在列表中搜索，处理大数据集时非常慢），你可以使用一个字典，把项和它们的索引对应起来。

我可能会这样重写：

# 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