在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

您可以使用集合(在2.4版本的CPython中)有效地查找重复值.如果您确实需要索引系统,则可以使用集合和列表.

使用集合执行查找将消除开销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

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中,大多数类型都是可清除的,除非它们是可以修改其内容的容器.例如:lists不可清除,因为你可以修改它们的内容,但tuples是可以清除的,因为你不能.

如果您尝试存储不可清除的值,则没有快速的通用解决方案.

Answer 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