仅当元素尚未存在时,将元素添加到列表的最有效方法是什么？

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)使用dict.这是扫描列表的好方法.但是,当我完成后,我需要按照创建的顺序打印出列表.如果我使用dict,我需要打印出按值排序的键.有没有一个好方法呢？

编辑:我实施了www.brool.com的建议.这是最简单,最快速的.它本质上是一个有序的Dict,但没有开销.表现很棒!

Answer 1

你想使用一套:

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

集合仅包含您添加的任何项目的一个实例,并且比手动迭代列表更有效.

如果您以前没有在Python中使用过套点,那么这个wikibooks页面看起来就像一个很好的入门.

Answer 2

这将最多遍历一次:

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 3

如果您担心内存使用情况,但想要优化常见情况,请保留包含最后n个点及其索引的字典.points_dict = dictionary,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