将元素添加到列表中，只有在未存在时，最有效的方法是什么？

Question

我在Python中有以下代码：

def point_to_index(point):
    if point not in points:
        points.append(point)
    return points.index(point)

这段代码效率非常低，特别是因为我预计points会增长到几百万个元素。

如果这个点不在列表中，我需要遍历列表3次：

1. 查找这个点并确认它不在列表里
2. 到列表的末尾添加一个新元素
3. 从头到尾遍历列表，直到找到这个点的索引

如果这个点在列表中，我需要遍历两次：

1. 查找这个点并确认它在列表里
2. 几乎到达列表的末尾，直到找到这个点的索引

有没有更高效的方法来做这个呢？比如，我知道：

• 我更可能调用这个函数时，传入的点不在列表中。
• 如果这个点在列表中，它更可能靠近末尾，而不是在开头。

所以如果我能让代码：

if point not in points:

从末尾到开头搜索列表，这样在点已经在列表中的时候会提高性能。

不过，我不想这样做：

if point not in reversed(points):

因为我想象reversed(points)本身会消耗很多资源。

我也不想把新点添加到列表的开头（假设我知道怎么在Python中做到这一点），因为那样会改变索引，而索引必须保持不变才能让算法正常工作。

我能想到的唯一改进就是尽量只遍历一次，如果可能的话，从末尾到开头。总之：

• 有没有好的方法来做到这一点？
• 有没有更好的方法来优化这个函数？

编辑：我收到了关于只遍历一次的建议。有没有办法让index()从末尾到开头查找？

编辑：有人问为什么索引很重要。我试图用OFF文件格式来描述一个3D表面。这个格式用顶点和面来描述一个表面。首先列出顶点，然后用顶点的索引列表来描述面。这就是为什么一旦我把一个顶点添加到列表中，它的索引不能改变。

编辑：有一些建议（比如igor的）使用字典。这是一个很好的解决方案，用于扫描列表。然而，当我完成后，我需要按创建时的顺序打印出列表。如果我使用字典，我需要按值对它的键进行排序。有没有好的方法做到这一点？

编辑：我实现了www.brool.com的建议。这是最简单和最快的。它本质上是一个有序字典，但没有额外的开销。性能非常好！

Answer 1

这个方法最多只会遍历一次：

def point_to_index(point):
    try: 
        return points.index(point)
    except ValueError:
        points.append(point)
        return len(points)-1

你也可以试试这个版本，它考虑到了匹配项可能靠近列表的末尾。要注意的是，reversed() 在处理非常大的列表时几乎没有成本——它不会创建副本，也不会多次遍历列表。

def point_to_index(point):
    for index, this_point in enumerate(reversed(points)):
        if point == this_point:
            return len(points) - (index+1)
    else:
        points.append(point)
        return len(points)-1

你还可以考虑保持一个并行的 dict 或 set 来检查某个点是否存在，因为这两种类型的查找速度都很快，时间复杂度是 O(1)。当然，这样做会消耗不少内存。

显然，如果这些点有序的话，你会有很多其他方法来加速这段代码，特别是可以使用二分查找来进行成员测试。

Answer 2

你想使用一个 集合：

>>> x = set()
>>> x
set([])
>>> x.add(1)
>>> x
set([1])
>>> x.add(1)
>>> x
set([1])

集合里每个添加的项目只会出现一次，这样比起手动一个个遍历列表要高效得多。

如果你之前没有用过Python的集合，可以看看 这个维基书页面，它看起来是个不错的入门资料。

Answer 3

如果你担心内存使用量，但又想优化常见的情况，可以保持一个字典，里面存储最近的 n 个点和它们的索引。这里的 points_dict 就是这个字典，max_cache 是缓存的大小。

def point_to_index(point):
    try:
        return points_dict.get(point, points.index(point))
    except:
        if len(points) >= max_cache:
            del points_dict[points[len(points)-max_cache]]
        points.append(point)
        points_dict[points] = len(points)-1
        return len(points)-1