11

为什么评论的速度明显更快？弹出、比较和长度检查不应该是 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))

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

4

2 回答 2

20

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

如果您需要经常删除索引位置 0，最好使用collections.deque. 双端队列支持从两端进行高效推送和弹出。

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

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

那恰好是在一个 32 位的 Windows 机器上。这并不让我感到惊讶；-)

于 2013-10-18T04:53:45.010 回答
10

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

len()是O(1) 因为删除是O(n)，因为如果您确保列表中的所有值都在内存中彼此相邻分配，则列表的总长度只是尾部的内存位置 - 头部的内存位置。如果您不关心len()和类似操作的性能，那么您可以使用链表来进行恒定时间的插入和删除——这只是做len()beO(n)和pop()be 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 分之一的工作。

另外，你应该得到一个内存错误，因为你正在尝试分配一个绝对比你的硬盘大得多的列表 - 更不用说你的内存了。

于 2013-10-18T05:03:08.600 回答