在Python中高效地减少列表

Question

我有一个包含85个项目的列表。我想要不断地将这个列表减半（其实就是对这些项目进行二分查找）——我的问题是，最有效的减半方法是什么？使用列表推导会不断创建列表的副本，这样不太理想。我希望能就地删除列表中的一部分，直到只剩下一个元素。

我不确定这是否相关，但我使用的是collections.deque，而不是标准列表。不过它们的工作方式大致相同，所以我觉得这可能没什么大问题。

Answer 1

不确定这是不是你真正需要的，但：

x = range(100)
while len(x) > 1:
    if condition:
        x = x[:int(len(x)/2)]
    else:
        x = x[int(len(x)/2):]

Answer 2

collections.deque 是通过链表来实现的，所以用二分查找的方法会比线性查找慢得多。建议你重新考虑一下你的方法。

Answer 3

对于仅仅85个项目来说，老实说，几乎任何你想用的方法都足够快。别急着优化。

不过，具体情况要看你在做什么，list（列表）可能比deque（双端队列）更快。deque在两端添加和删除项目时更快，但它不支持切片操作。

使用list时，如果你想复制或删除一段连续的项目（比如前42个），可以用切片来实现。假设每次操作都删除一半的列表，复制项目到新列表的速度通常会比从现有列表中删除项目慢（删除时需要把未删除的那一半“向左”移动，这个过程的时间成本大致和复制另一半相当，但并不总是需要这样；比如删除列表的后半部分时就不需要移动任何东西）。

如果用deque来高效地做到这一点，你应该使用pop()或popleft()来删除项目，而不是切片（因为切片涉及很多属性访问和方法调用，这在Python中相对比较耗时），而且你还得自己写一个循环来控制这个操作，这样的速度会比原生的切片操作慢。

既然你说这基本上是一个二分查找，实际上最快的方式可能是直接找到你想保留的项目，而不修改原来的容器，然后返回一个只包含那个项目的新容器。对于这个操作，list会比deque快，因为你会频繁通过索引访问项目。使用deque时，每次访问项目都需要从头开始遍历链表，而通过索引访问list中的项目则是一个简单快速的计算。