在python中有效地减少列表

问题描述：

所以我有一个85个项目的列表。我想不断减少这个列表的一半（主要是对项目的二分搜索） - 我的问题是，什么是减少列表最有效的方式？列表理解将持续创建不理想的列表副本。我想就地删除我的列表范围，直到剩下一个元素。在python中有效地减少列表

我不知道这是否是相关的，但我使用collections.deque，而不是一个标准的列表。他们可能或多或少地以相同的方式工作，所以我怀疑这个问题。

请张贴代码。 “减少”并不清楚你的意思。 Python有一个内置的'reduce（）'函数，但你的问题似乎不相关。请提供一些代码来解释你的意思。 – 2011-06-07 17:32:47

您的意思是“减少”功能意义上的组合相邻项目？或者你的意思是删除它们？如果后者，在什么基础上删除项目？ – kindall 2011-06-07 17:36:36

如果你在codereview.stackexchange.com上发布你的代码，你会得到很多人建议提高速度的方法。我不确定你在做什么，但有一个更好的想法（比如通过看代码），这听起来像是一种可以避免“减少”列表的技术。 – 2011-06-07 18:35:59

答

对于仅仅85项，如实，几乎所有你想使用的任何方法会比速度不够快了。不要过早优化。

也就是说，根据你实际在做什么，list可能会比deque更快。 A deque在任一端添加和删除项目都更快，但不支持切片。

与列表，如果你想复制或删除项目的一个连续范围（比如，第42），您可以用切片做到这一点。假设列表的一半在每次通过时被删除，则将项目复制到新列表的速度要比从现有列表中删除项目要慢（删除操作要求将未被删除的列表的一半移到内存中的“向左”，这将是大约与复制另一半相同的时间成本，但是你并不总是需要这样做;删除列表的后半部分将不需要移动任何东西）。

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

既然你说，这基本上是一个二进制搜索，它可能是实际最快只需找到你想保留，而完全不修改原始容器中的项目，然后返回一个新的容器盛装的是单个项目。 A list将比deque更快，因为您将按索引执行大量访问项目。要在deque中执行此操作，每次访问某个项目时，Python都需要从头开始跟踪链接列表，而通过索引访问项目对于list来说是一个简单快速的计算。

谢谢！我结束了对二进制搜索的描述。 – 2011-06-08 17:45:02

答

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

答

不知道这是你真正需要的，但是：

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

//操作符强制整数除法，例如。 'len（x）// 2'几乎等价于int（len（x）/ 2）'。这种类型是强制返回的类型。那是'3 // 2.0''等于1.0 – Dunes 2011-06-07 21:24:43

答

85个项目甚至不值得我们深思。电脑真的很快。
为什么要从列表中删除范围，而不是简单地选择一个结果？
如果有一个很好的理由，为什么你不能这样做（2）：保留原来的列表，并改变只有两个指标：你看子列表的开始和结束索引。

答

关于前一个问题我比较了许多技术去除给予了谓词的项目清单。（也就是说，我有一个函数返回True或False是否保留一个特定的项目。）我记得使用列表理解是最快的。事实是，复制真的很便宜。

您可以采取的唯一措施来提高速度取决于您要删除的项目。但是你没有提到任何有关这方面的信息，所以我不能提出任何建议。

列表理解并不便宜，因为复制很便宜（虽然这是真的），但列表理解很便宜，因为列表理解在C级上进行循环，它几乎绕过了Python循环机制的一半。 – 2011-06-08 06:53:24

@赖瑞安，对。但复制是为什么大多数人和OP认为它更昂贵。但是大多数人认为复印要便宜得多。 – 2011-06-08 15:33:43

在python中有效地减少列表

相关推荐