为什么列表追加和弹出（0）比增加和减少队列中的前后计数器快？

Question

我已经使用以下方法在队列中实现了push和pop函数

1. 将列表初始化为[]，push:list.append（），pop:list.pop（0）
2. 将列表初始化为[None]*100，front=rear=0，push:list[rear]=item，rear++，pop:front++（当向前或向后递增时，它执行x=（x+1）%100）

我原以为，第二种方法会更快，因为第二种方法中的pop-in只会增加前计数器，而第一种方法中的pop-in必须将所有列表项移到更低的索引，例如从list1到list[0]，从list[2]到list1等等

但我对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!")

Answer 1

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和CALL_METHOD