为什么双端队列这么快？

Question

我最近在做一个关于双端队列（deque）的工作，这是我朋友前几天教我的（同一个朋友之前让我解决一个不使用int的整数问题）。总之，我发现deque的速度非常快，于是我写了一些代码，比较了用deque逐个删除元素找中位数和用标准列表逐个删除元素找中位数的速度。在测试中，deque只用了0.09秒，而标准列表却花了89秒。我不明白为什么deque这么快，因为最后不管是deque还是标准列表，都是从一个有序列表中逐个删除元素，理论上应该是差不多的时间。有人能告诉我deque是怎么工作的，以及它为什么这么快吗？注意：下面的列表已经从79,360个元素缩短到1052个，以符合Stack Overflow的字符限制。如果你想重现我做的列表，可以把列表中的元素复制粘贴大约80次。抱歉给你带来不便。

from collections import deque as d
from time import time as t

#ignore this part
inp = [3,45,235,2,5,2,3,5,6,7,2,1,2,45,5,32,5,43,255,325,32,3,5,235,42,5,1,24,1,2,4,3,1,2,3,2,1,2,4,5,432,1,4,52,432,35,2,3,5,2,34,5,2,23,5,34,5,2,3,34,52,53,25,2,3,45,235,2,5,2,3,5,6,7,2,1,2,45,5,32,5,43,255,325,32,3,5,235,42,5,1,24,1,2,4,3,1,2,3,2,1,2,4,5,432,1,4,52,432,35,2,3,5,2,34,5,2,23,5,34,5,2,3,34,52,53,25,2,3,45,235,2,5,2,3,5,6,7,2,1,2,45,5,32,5,43,255,325,32,3,5,235,42,5,1,24,1,2,4,3,1,2,3,2,1,2,4,5,432,1,4,52,432,35,2,3,5,2,34,5,2,23,5,34,5,2,3,34,52,53,25,2,3,45,235,2,5,2,3,5,6,7,2,1,2,45,5,32,5,43,255,325,32,3,5,235,42,5,1,24,1,2,4,3,1,2,3,2,1,2,4,5,432,1,4,52,432,35,2,3,5,2,34,5,2,23,5,34,5,2,3,34,52,53,25,2,3,45,235,2,5,2,3,5,6,7,2,1,2,45,5,32,5,43,255,325,32,3,5,235,42,5,1,24,1,2,4,3,1,2,3,2,1,2,4,5,432,1,4,52,432,35,2,3,5,2,34,5,2,23,5,34,5,2,3,34,52,53,25,2,3,45,235,2,5,2,3,5,6,7,2,1,2,45,5,32,5,43,255,325,32,3,5,235,42,5,1,24,1,2,4,3,1,2,3,2,1,2,4,5,432,1,4,52,432,35,2,3,5,2,34,5,2,23,5,34,5,2,3,34,52,53,25,2,3,45,235,2,5,2,3,5,6,7,2,1,2,45,5,32,5,43,255,325,32,3,5,235,42,5,1,24,1,2,4,3,1,2,3,2,1,2,4,5,432,1,4,52,432,35,2,3,5,2,34,5,2,23,5,34,5,2,3,34,52,53,25,2,3,45,235,2,5,2,3,5,6,7,2,1,2,45,5,32,5,43,255,325,32,3,5,235,42,5,1,24,1,2,4,3,1,2,3,2,1,2,4,5,432,1,4,52,432,35,2,3,5,2,34,5,2,23,5,34,5,2,3,34,52,53,25,2,3,45,235,2,5,2,3,5,6,7,2,1,2,45,5,32,5,43,255,325,32,3,5,235,42,5,1,24,1,2,4,3,1,2,3,2,1,2,4,5,432,1,4,52,432,35,2,3,5,2,34,5,2,23,5,34,5,2,3,34,52,53,25,2,3,45,235,2,5,2,3,5,6,7,2,1,2,45,5,32,5,43,255,325,32,3,5,235,42,5,1,24,1,2,4,3,1,2,3,2,1,2,4,5,432,1,4,52,432,35,2,3,5,2,34,5,2,23,5,34,5,2,3,34,52,53,25,2,3,45,235,2,5,2,3,5,6,7,2,1,2,45,5,32,5,43,255,325,32,3,5,235,42,5,1,24,1,2,4,3,1,2,3,2,1,2,4,5,432,1,4,52,432,35,2,3,5,2,34,5,2,23,5,34,5,2,3,34,52,53,25,2,3,45,235,2,5,2,3,5,6,7,2,1,2,45,5,32,5,43,255,325,32,3,5,235,42,5,1,24,1,2,4,3,1,2,3,2,1,2,4,5,432,1,4,52,432,35,2,3,5,2,34,5,2,23,5,34,5,2,3,34,52,53,25,2,3,45,235,2,5,2,3,5,6,7,2,1,2,45,5,32,5,43,255,325,32,3,5,235,42,5,1,24,1,2,4,3,1,2,3,2,1,2,4,5,432,1,4,52,432,35,2,3,5,2,34,5,2,23,5,34,5,2,3,34,52,53,25,2,3,45,235,2,5,2,3,5,6,7,2,1,2,45,5,32,5,43,255,325,32,3,5,235,42,5,1,24,1,2,4,3,1,2,3,2,1,2,4,5,432,1,4,52,432,35,2,3,5,2,34,5,2,23,5,34,5,2,3,34,52,53,25,2,3,45,235,2,5,2,3,5,6,7,2,1,2,45,5,32,5,43,255,325,32,3,5,235,42,5,1,24,1,2,4,3,1,2,3,2,1,2,4,5,432,1,4,52,432,35,2,3,5,2,34,5,2,23,5,34,5,2,3,34,52,53,25,2,3,45,235,2,5,2,3,5,6,7,2,1,2,45,5,32,5,43,255,325,32,3,5,235,42,5,1,24,1,2,4,3,1,2,3,2,1,2,4,5,432,1,4,52,432,35,2,3,5,2,34,5,2,23,5,34,5,2,3,34,52,53,25,2,3,45,235,2,5,2,3,5,6,7,2,1,2,45,5,32,5,43,255,325,32,3,5,235,42,5,1,24]
print(len(inp))

# here's the important code
inp.sort()
# use deque
st1 = t()
def convert(inp):
    return d(inp)

converted = convert(inp)

def wompwomp(inp):
    while len(inp) > 2:
        inp.pop()
        inp.popleft()

    if len(inp) == 2:
        return (inp[0] + inp[1])/2
    else:
        return inp[0]

print(wompwomp(converted))
et1 = t()

tim1 = et1 - st1
print(f" Time is {tim1}")


# standard
st2 = t()


while len(inp) > 2:
    inp.remove(inp[0])
    inp.remove(inp[-1])
if len(inp) == 2:
    inp = (inp[0] + inp[1])/2
else:
    pass

et2 = t()
tim2 = et2 - st2
print(f"Time is {tim2}")
print(str(inp))