Python中len()和pop()的效率 [英] Efficiency of len() and pop() in Python

问题描述

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

Why is this Significantly faster with comments? Shouldn't a pop, a comparison, and a length check be O(1)? Would that significantly affect the speed?

#! /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)) 

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

UPDATE: I'm making the question shorter, because the code being significantly slower was my question. I cared less about the code getting killed at runtime.

推荐答案

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

Just to answer part of the question: popping from the end (the right end) of a list takes constant time in CPython, but popping from the left end (.pop(0)) takes time proportional to the length of the list: all the elements in the_list[1:] are physically moved one position to the left.

如果需要频繁删除索引位置0，最好使用collections.deque的实例.Deques 支持从两端高效的推送和弹出.

If you need to delete index position 0 frequently, much better to use an instance of collections.deque. Deques support efficient pushing and popping from both ends.

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

BTW, when I run the program, I get a clean exception:

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

那恰好是在 32 位 Windows 机器上.这并不让我感到惊讶 ;-)

That happened to be on a 32-bit Windows box. And it doesn't surprise me ;-)

这篇关于Python中len()和pop()的效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！