Python中len()和pop()的效率

Question

为什么评论显着加快？弹出,比较和长度检查不应该是O(1)吗？这会显着影响速度吗？

#! /usr/bin/python                                                                
import math                                                                       

pmarbs = []                                                                       
pows = 49                                                                         
pmarbs.append("W")                                                                
inc = 1                                                                           
for i in range(pows):                                                             
    count = 0                                                                     
    j = 0                                                                         
    ran = int(pow(2, i))                                                          
    marker = len(pmarbs) - inc                                                    
    while (j < ran):                                                              
        #potential marble choice                                                  
        pot = pmarbs[marker - j]                                                  
        pot1 = pot + "W"                                                          
        pot2 = pot + "B"                                                          

        if (pot2.count('W') < pot2.count('B')) and (len(pot2) > (i+1)):           
            count += 1                                                            
        else:                                                                     
            pmarbs.append(pot2)                                                   

        pmarbs.append(pot1)                                                       
#        if(len(pmarbs[0]) < i):                                                  
#           pmarbs.pop(0)                                                         
#           marker -= 1                                                           
        j += 1                                                                    


    if (count != 0):                                                              
        print(count)                                                              
        print("length of pmarbs = %s" % len(pmarbs)) 

更新:我的问题更短,因为代码明显更慢是我的问题.我不太关心在运行时被杀死的代码.

Answer 1

只是为了回答部分问题:从列表的末尾(右端)弹出在CPython中需要恒定的时间,但是从左端弹出(.pop(0))花费的时间与列表的长度成正比: 所有元素the_list[1:]都是物理的向左移动了一个位置.

如果需要频繁删除索引位置0,那么使用实例要好得多collections.deque.Deques支持从两端有效推送和弹出.

顺便说一下,当我运行程序时,我得到一个干净的异常:

...
length of pmarbs = 8306108
Traceback (most recent call last):
  File "xxx.py", line 22, in <module>
    pmarbs.append(pot2)
MemoryError

这恰好是在一个32位的Windows机器上.它并没有让我感到惊讶;-)

Answer 2

list.pop(index)是一个O(n)操作,因为从列表中删除值后,您必须将列表中每个其他值的内存位置移动一个.pop在大型列表上反复调用是浪费计算周期的好方法.如果你绝对必须一遍又一遍地从大型列表的前面删除collections.deque,这将为你提供更快的插入和删除前端.

len()是O(1) 因为缺失是O(n)的,因为如果你要确保在列表中的所有值都在旁边对方的内存分配,列表的总长度就是尾部的内存位置-头部的存储位置.如果你不关心的性能len()和类似的操作,那么你可以使用一个链表做一定时间的插入和删除-只是使len()是O(n)和pop()是O(1)(你会得到像其他一些时髦的东西O(n)查找).

我所说的一切也pop()都适用insert()- 除了append()通常需要的东西O(1).

我最近处理了一个问题,需要从一个非常大的列表中删除大量元素(大约10,000,000个整数),并且我pop()每次需要删除的东西时都使用了我最初的愚蠢实现- 结果证明根本不起作用,因为它花O(n)了甚至算法的一个循环,这本身需要n时间.

我的解决方案是创建一个set()调用ignore,其中我保留了所有"已删除"元素的索引.我有一些辅助函数来帮助我不必考虑跳过这些,所以我的算法并没有太难看.最终做的是O(n)每10,000次迭代执行一次传递以删除所有元素ignore并再次使ignore 变为空,这样我从缩小的列表中获得了更高的性能,而只需要为删除操作完成10,000次工作.

另外,你应该得到一个内存错误,因为你试图分配一个肯定比你的硬盘大得多的列表 - 更不用说你的记忆了.