2

所以我有一个包含 85 个项目的列表。我想不断地把这个列表减半（本质上是对项目的二进制搜索）——我的问题是，什么是减少列表的最有效方法？列表理解会不断创建不理想的列表副本。我想就地删除我的列表范围，直到我只剩下一个元素。

我不确定这是否相关，但我使用的是 collections.deque 而不是标准列表。他们可能或多或少地以相同的方式工作，所以我怀疑这很重要。

4

5 回答 5

3

老实说，对于仅仅 85 个项目，几乎任何您想要使用的方法都足够快。不要过早优化。

也就是说，根据您实际在做什么， alist可能比 a 更快deque。Adeque在任一端添加和删除项目的速度更快，但它不支持切片。

使用列表，如果您想复制或删除连续范围的项目（例如，前 42 个），您可以使用切片来执行此操作。假设每次遍历都消除了一半列表，则将项目复制到新列表平均比从现有列表中删除项目要慢（删除需要将未删除的列表的一半在内存中“向左”移动，这将是与复制另一半的时间成本大致相同，但您并不总是需要这样做；删除列表的后半部分不需要移动任何东西）。

为了有效地做到这一点deque，您可能想要pop()或popleft()项目而不是切片它们（大量的属性访问和方法调用，这在 Python 中相对昂贵），并且您必须编写控制 Python 中的操作的循环，这将比本机切片操作慢。

既然你说它基本上是一个二分搜索，实际上可能最快的是简单地找到你想要保留的项目而不修改原始容器，然后返回一个包含该单个项目的新容器。Alist将比 a 更快，deque因为您将通过索引执行大量访问项目。要在 a 中执行此操作，deque将需要 Python 在每次访问项目时从头开始遵循链表，而通过索引访问项目是对 a 的简单、快速计算list。

于 2011-06-07T18:02:56.803 回答
1

collections.deque是通过链表实现的，因此二进制搜索将比线性搜索慢得多。重新考虑你的方法。

于 2011-06-07T17:33:59.630 回答
1

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

x = range(100)
while len(x) > 1:
    if condition:
        x = x[:int(len(x)/2)]
    else:
        x = x[int(len(x)/2):]
于 2011-06-07T17:43:17.587 回答
1
  1. 85 项甚至不值得考虑。电脑很快，真的。
  2. 为什么要从列表中删除范围，而不是简单地选择一个结果？
  3. 如果有充分的理由您不能这样做 (2)：保留原始列表并仅更改两个索引：您正在查看的子列表的开始和结束索引。
于 2011-06-07T18:22:50.703 回答
0

在上一个问题上，我比较了一些用于删除给定谓词的项目列表的技术。（也就是说，我有一个函数返回 True 或 False 是否保留特定项目。）我记得使用列表推导是最快的。事实上，复制真的很便宜。

您唯一可以提高速度的方法取决于您要删除的项目。但是您对此没有任何说明，因此我无法提出任何建议。

于 2011-06-07T18:38:40.363 回答