Python:如何修改列表时内存的使用和优化?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (7)
  • 关注 (0)
  • 查看 (1373)

问题

我的关注点如下:我将一个相对性较大的数据集存储在一个经典的python列表中,为了处理数据,我必须多次迭代列表,对这些元素执行一些操作,并经常从列表中弹出一个项目。

似乎从Python列表中删除一个项目花费O(N),因为Python必须将元素上方的所有项目复制到一个地方。 此外,由于要删除的项目数量与列表中元素的数量大致成比例,因此将导致O(N ^ 2)算法。

我希望找到一个经济高效的解决方案(时间和记忆)。 我研究了在互联网上可以找到的内容,并总结了下面的不同选项。 哪一个是最好的候选人?

保持本地索引:

while processingdata:
    index = 0
    while index < len(somelist):
        item = somelist[index]
        dosomestuff(item)
        if somecondition(item):
            del somelist[index]
        else:
            index += 1

这是我最初想出的解决方案。

向后走:

while processingdata:
    for i in xrange(len(somelist) - 1, -1, -1):
        dosomestuff(item)
        if somecondition(somelist, i):
            somelist.pop(i)

这避免了增加索引变量,但最终的代价与原始版本相同。

列一个新的清单:

while processingdata:
    for i, item in enumerate(somelist):
        dosomestuff(item)
    newlist = []
    for item in somelist:
        if somecondition(item):
            newlist.append(item)
    somelist = newlist
    gc.collect()

这是一个非常天真的策略,以消除元素从一个列表,并需要大量的内存,因为几乎完整的副本列表必须作出。

使用清单理解:

while processingdata:
    for i, item in enumerate(somelist):
        dosomestuff(item)
    somelist[:] = [x for x in somelist if somecondition(x)]

这是非常优雅的,但在掩盖之下,它再一次遍历整个列表,并且必须复制其中的大多数元素。

使用过滤器功能:

while processingdata:
    for i, item in enumerate(somelist):
        dosomestuff(item)
    somelist = filter(lambda x: not subtle_condition(x), somelist)

这还会创建一个占用大量RAM的新列表。

使用itertools的筛选函数:

from itertools import ifilterfalse
while processingdata:
     for item in itertools.ifilterfalse(somecondtion, somelist):
         dosomestuff(item)

此版本的筛选器调用不会创建新列表,但不会对每一项调用doomestuff,从而破坏算法的逻辑。我列入这个例子只是为了创建一个详尽的清单。

边走边移动列表上的项目

while processingdata:
    index = 0
    for item in somelist:
        dosomestuff(item)
        if not somecondition(item):
            somelist[index] = item
            index += 1
    del somelist[index:]

这是一个微妙的方法,似乎成本效益。 我认为它会移动每个项目(或指向每个项目的指针?)一次导致O(N)算法。 最后,我希望Python能够足够聪明地在最后调整列表的大小,而不需要为列表的新副本分配内存。 但不知道。

放弃Python列表:

class Doubly_Linked_List:
    def __init__(self):
        self.first = None
        self.last = None
        self.n = 0
    def __len__(self):
        return self.n
    def __iter__(self):
        return DLLIter(self)
    def iterator(self):
        return self.__iter__()
    def append(self, x):
        x = DLLElement(x)
        x.next = None
        if self.last is None:
            x.prev = None
            self.last = x
            self.first = x
            self.n = 1
        else:
            x.prev = self.last
            x.prev.next = x
            self.last = x
            self.n += 1

class DLLElement:
    def __init__(self, x):
    self.next = None
    self.data = x
    self.prev = None

class DLLIter:
    etc...

这种类型的对象以有限的方式类似于python列表。 但是,保证删除元素O(1)。 我不想去这里,因为这需要大量的代码重构几乎无处不在。

提问于
用户回答回答于

(或甚至一个字典)可能是你在找什么。 它与字典(没有关联的值)是相同的底层结构,但是您的对象确实需要可以哈希。

如果订单在您的清单/设置中很重要,您可以进行订购。 OrderedSet在活动状态上有一个很好的配方。 Python 2.7和3.1也有一个OrderedDict你可以测试你自己的实现,看看这个开销是如何影响你的,但是从hashtable中获得的速度可能是值得的。

根据你在列表中的对象进行的比较,堆(heapq模块)也可能适合你的问题。 堆将最小化插入和删除基础列表中的项目所需的操作数量。

用户回答回答于

Brandon Craig Rhode建议使用collections.deque,这可以适应这个问题:操作不需要额外的内存,并且保持O(n)。 我不知道总的内存使用情况,以及它如何与列表进行比较。 值得注意的是,一个deque必须存储更多的引用,如果它不像使用两个列表那样占用内存,我不会感到惊讶。 你将不得不测试或研究它来认识你自己。

如果使用deque,我的部署方式将与Rhodes建议的略有不同:

from collections import deque
d = deque(range(30))
n = deque()

print d

while True:
    try:
        item = d.popleft()
    except IndexError:
        break

    if item % 3 != 0:
        n.append(item)

print n
用户回答回答于

你没有提供足够的信息,我可以找到很好的回答这个问题。我不知道你的用例是否足以告诉你,如果你需要时间优化,什么样的数据结构会给你带来所需的时间复杂性。典型的解决方案是建立一个新的列表,而不是重复的删除,但显然这加倍(ish)的内存使用。

如果你有内存使用问题,你可能想要放弃使用内存中的Python结构,并使用磁盘上的数据库。许多数据库都可用,并且sqlite附带Python。根据你的使用情况以及你的内存需求有多紧张,array.array或者numpy可能对你有帮助,但是这很大程度上取决于你需要做什么。 array.array将具有与list和numpy数组相似的复杂性,但是会以某种不同的方式工作。使用延迟迭代器(如生成器和itertools模块中的东西)通常可以将内存使用量减少n倍。

使用数据库将改善从任意位置删除项目的时间(尽管如此重要,订单将会丢失)。使用一个字典将会做同样的事情,但可能在高内存使用率。

你也可以考虑blist作为一个列表的替代品,可能会得到你想要的一些妥协。我不相信这会大大增加内存使用量,但它会将项目移除更改为O(log n)。当然,这是以使其他操作更昂贵为代价的。

我将不得不看到测试,认为你的双向链表实现的内存使用不变的因素将小于你通过简单地创建一个新的列表。我真的怀疑它。

我认为,为了得到更具体的答案,你必须更多地分享你的问题课,但一般的建议是

  • 在进行过程中迭代一个列表,构建一个新的列表(或者在需要时使用生成器来生成这些项目)。如果你真的需要一个列表,这将有一个2的记忆因子,这是很好的规模,但如果你的记忆周期短,但没有帮助。
  • 如果内存不足,而不是微优化,可能需要磁盘上的数据库或将数据存储在文件中。
用户回答回答于

双向链表比重新分配列表更糟糕。一个Python列表使用5个单词+每个元素一个单词。双向链接列表将使用每个元素5个词。即使你使用的是单向链表,它仍然是每个元素4个单词 - 比每个元素少于2个单词重建列表所需要的要多得多。

从内存使用的角度来看,将项目移到列表上并在最后删除松弛是最好的方法。如果列表少于一半,Python将释放内存。问问自己的问题是,它真的很重要。列表条目可能指向某些数据,除非列表中有许多重复的对象,与数据相比,用于列表的内存不重要。鉴于此,您可能只是建立一个新的列表。

为了建立一个新的名单,你提出的方法并不好。没有明显的原因,你为什么不能只是一次过去的名单。此外,调用gc.collect()是不必要的,实际上也是有害的--CPython引用计数将立即释放旧列表,甚至其他垃圾收集器在受到内存压力时最好收集。所以这样的事情会起作用:

while processingdata:
    retained = []
    for item in somelist:
        dosomething(item)
        if not somecondition(item):
            retained.append(item)
    somelist = retained

如果不介意在列表理解中使用副作用,那么以下也是一个选项:

def process_and_decide(item):
    dosomething(item)
    return not somecondition(item)

while processingdata:
    somelist = [item for item in somelist if process_and_decide(item)]

内部方法也可以重构,因此机制和业务逻辑是分开的:

def inplace_filter(func, list_):
    pos = 0
    for item in list_:
        if func(item):
            list_[pos] = item
            pos += 1
    del list_[pos:]

while processingdata:
    inplace_filter(process_and_decide, somelist)
用户回答回答于

Python仅存储对列表中对象的引用 - 而不是元素本身。如果逐项增加列表,那么列表(即对象的引用列表)将逐个增加,最终到达Python预先分配在列表末尾的多余内存的末尾(引用!)。 。然后,它将列表(引用!)复制到一个新的更大的地方,而你的列表元素保留在旧的位置。由于你的代码总是访问旧列表中的所有元素,所以通过new_list [i] = old_list [i]将引用复制到一个新列表几乎没有任何负担。唯一的性能提示是一次性分配所有新元素,而不是附加它们(OTOH Python文档说,随着列表大小,超额元素的数量不断增加,分摊的附加仍然是O(1))。如果你缺乏新的列表(引用)的地方,那么我担心你运气不好 - 任何会避免O(n)就地插入/删除的数据结构可能会比简单的4 - 或8字节条目。

用户回答回答于

从你的描述来看,它听起来像是一个deque(“甲板”),正是你正在寻找的东西:

http://docs.python.org/Library/Collections.html#deque-Objects

通过反复调用pop()来遍历它,然后,如果要将弹出的项目保存在双端队列中,请使用appendleft(item)将该项目返回到前面。 为了跟上迭代完成的时间,并且在deque中看到了所有的东西,可以放一个像None一样的标记对象,或者当你启动一个特定的循环并且使用range()时请求deque的len() )弹出()正是那么多项目。

我相信你会发现所有你需要的操作是O(1)。

用户回答回答于

不知道你在这个列表中做什么的具体细节,很难确切地知道在这种情况下什么是最好的。 如果你的处理阶段依赖于list元素的当前索引,那么这将不起作用,但是如果不是这样的话,看起来你已经没有使用Pythonic(在很多方面,最简单的方法):生成器。

如果你正在做的是遍历每个元素,以某种方式处理它,那么要么将该元素包含在列表中,要么使用生成器。 那么你永远不需要将整个迭代器存储在内存中。

def process_and_generate_data(source_iterable):
    for item in source_iterable:
        dosomestuff(item)
        if not somecondition(item):
            yield item

你将需要一个处理循环,处理持久化处理的迭代(写回到一个文件,或其他),或者如果你有多个处理阶段,你希望分成不同的生成器,你可以让你的处理循环通过 下一台发电机。

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励