python - 为什么列出追加和弹出(0)比增加和减少队列中的前后计数器更快?
问题描述
我已经使用以下方法在队列中实现了推送和弹出功能。
- 初始化列表为 [], push:list.append(), pop:list.pop(0)
- 将列表初始化为 [None]*100,front=rear=0, push: list[rear]=item, rear++, pop: front++ (在增加前或后时,它正在执行 x = (x+1)%100)。
我期待,第二种方法会更快,因为 pop in 第二种方法只会增加前计数器,而 pop in 第一种方法必须将所有列表项移动到较低的索引,例如从列表1到列表 [0],从列表[2] 列出1等。
但是我对 timeit() 的实验表明第一种方法更快。谁能解释为什么?
代码:
def initialiseQueue():
global L,Ld,front,rear,size
L=[None]*100
Ld=[]
front=0
rear=0
size = 100
def enqueue(x):
global L, rear, size
if (rear+1)%size==front: # full
print("Queue is full. Can't add new item.")
return 1
else:
L[rear] = x
rear = (rear +1)%size
return 0
def dequeue():
global L, front,rear, size
if front==rear: #empty
print("Queue is empty")
else:
x = L[front]
front = (front + 1)%size
return x
from random import *
def qDQ(m,n,way='default'):
for _ in range(m):
for i in range(n):
x = randint(1,10)
addToQueue(x,way)
for i in range(n):
removefromQueue(way)
def addToQueue(x,way):
global L,Ld
if way == 'default':
Ld.append(x)
else:
enqueue(x)
def removefromQueue(way):
global L,Ld
if way == 'default':
return Ld.pop(0)
else:
return dequeue()
from time import *
from timeit import *
m,n=input("Enter two integers separated with spaces:").split(" ")
m=int(m)
n=int(n)
a = timeit(stmt="qDQ(m,n,'default')",setup='initialiseQueue()',timer=process_time,number=10000, globals=globals())
b = timeit(stmt="qDQ(m,n,'special')",setup='initialiseQueue()',timer=process_time,number=10000, globals=globals())
print("Process time for add/remove from queue using list built-in functions:",a)
print("Process time for add/remove from queue using approach 2:",b)
print("Hence","approach 1" if a<b else "approach 2","is faster!")
解决方案
Python 是一种解释型语言。它将函数执行转换为“虚拟机”的字节码。
您的enqueue
函数转换为以下操作:
>>> import dis #Python disassembler from std lib
>>> dis.dis(enqueue)
3 0 LOAD_GLOBAL 0 (rear)
2 LOAD_CONST 1 (1)
4 BINARY_ADD
6 LOAD_GLOBAL 1 (size)
8 BINARY_MODULO
10 LOAD_GLOBAL 2 (front)
12 COMPARE_OP 2 (==)
14 POP_JUMP_IF_FALSE 28
4 16 LOAD_GLOBAL 3 (print)
18 LOAD_CONST 2 ("Queue is full. Can't add new item.")
20 CALL_FUNCTION 1
22 POP_TOP
5 24 LOAD_CONST 1 (1)
26 RETURN_VALUE
7 >> 28 LOAD_FAST 0 (x)
30 LOAD_GLOBAL 4 (L)
32 LOAD_GLOBAL 0 (rear)
34 STORE_SUBSCR
8 36 LOAD_GLOBAL 0 (rear)
38 LOAD_CONST 1 (1)
40 BINARY_ADD
42 LOAD_GLOBAL 1 (size)
44 BINARY_MODULO
46 STORE_GLOBAL 0 (rear)
9 48 LOAD_CONST 3 (0)
50 RETURN_VALUE
52 LOAD_CONST 0 (None)
54 RETURN_VALUE
而append
是一个内置操作,高度优化并用 C 编码(用于 CPython)。
也是如此pop
。
我认为这至少可以解释为什么您的代码要慢得多的一个原因。
优化是一项艰巨的任务,效率取决于许多因素,并且在各个层面都可能出现意外,因此最好抵制过早的优化:只有在遇到问题时才开始查看这些细节。
为了比较,这里是对列表中调用内置函数的相同反汇编append
:
>>> import dis
>>> def append(l, x):
... l.append(x)
...
>>> dis.dis(append)
2 0 LOAD_FAST 0 (l)
2 LOAD_METHOD 0 (append)
4 LOAD_FAST 1 (x)
6 CALL_METHOD 1
8 POP_TOP
10 LOAD_CONST 0 (None)
12 RETURN_VALUE
>>>
实际上它只是在做LOAD_METHOD
and CALL_METHOD
。
推荐阅读
- javascript - Meteor 不提供目录中的所有 HTML 文件
- angular - 如何管理包含具有共享功能的不同应用程序的单个 Angular 项目
- r - 从宽到长塑造一个巨大的data.table(1,000,000 × 4,000 别名8GB)
- javascript - 无法通过单击(仅选项卡有效)react-places-autocomplete 来选择建议。(不是 z-index 问题)
- elasticsearch - NEST:由于空搜索导致的弹性搜索性能问题
- r - 麻烦子设置data.frame/对因素错误没有意义
- excel - 在用户窗体中使用图表图像而不保存到磁盘
- javascript - 带有两个事务的 IndexedDB:1 个读取然后 1 个更新
- typescript - 你会称这种 TypeScript 不能做的推理是什么?
- java - 无法使用 Build > Build Project 在 Intellij 中构建项目