python中列表的高效约简

2024-03-29 09:29:03 发布

您现在位置:Python中文网/ 问答频道 /正文

所以我有一个85个项目的清单。我想不断地将这个列表减少一半(本质上是对项目的二元搜索)——那么我的问题是,什么是减少列表的最有效方法?列表理解会不断地创建不理想的列表副本。我想就地删除我的列表范围,直到我只剩下一个元素。在

我不确定这是否相关,但我正在使用收藏.deque而不是标准列表。他们的工作方式可能或多或少是一样的,所以我怀疑这是否重要。在


Tags: 项目方法元素列表标准方式副本理想
3条回答

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

不确定这是您真正需要的,但是:

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

事实上,对于仅仅85个项目来说,几乎任何你想使用的方法都足够快。不要过早地优化。在

也就是说,根据你实际在做什么,list可能比deque快。deque在两端添加和删除项的速度更快,但它不支持切片。在

对于一个列表,如果你想复制或删除一系列连续的项目(比如前42个),你可以用一个切片来完成。假设每次删除列表的一半,将项目复制到新列表比从现有列表中删除项目平均要慢(删除需要将未被删除的列表的一半“向左”移动到内存中,这与复制另一半的时间成本大致相同,但您并不总是需要这样做;删除列表的后半部分不需要移动任何内容)。在

为了高效地使用deque来实现这一点,您需要pop()或{}而不是对它们进行切片(大量的属性访问和方法调用,在Python中相对昂贵),并且您必须在Python中编写控制操作的循环,这将比本机切片操作慢。在

既然您说它基本上是一个二进制搜索,那么最快的方法可能是在根本不修改原始容器的情况下找到要保留的项,然后返回一个新的容器来保存该项。list将比deque更快,因为您将通过索引执行大量访问项。要在deque中执行此操作,需要Python在每次访问项时从一开始就跟随链接列表,而按索引访问项是list的简单、快速的计算。在

相关问题 更多 >