编辑：如何设计和实施实验以对 python 中的两个队列实施进行基准比较

Question

我正在寻找有关如何设计实验以比较 queue 实现的行为的指示，一个是使用 python list 完成的，另一个是使用基准 python queue abstract data type 完成的。

根据我的理解，我可以提供一些代码amortized testing

###############################################################
# Experiment to determine the differences between a list      #
# implemented queue and the 'queue' ADT (abstract data type)#
###############################################################
from pythonds import Queue
import time


class MyQueue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)


q = Queue()


# Steps:
# 1) Enter 10 to five items in both 'MyQueue' and 'Queue'
# 2) This should be done from instance of the various classes
# 3) Check the number of steps that it takes to remove items from
#    these object instances.

m = MyQueue()
t1 = time.time()
for i in range(1, 100001):
    m.enqueue(i)
t2 = time.time()

exec_time = t2 - t1

# m.dequeue()

t3 = time.time()
for u in range(1, 100001):
    q.enqueue(u)
t4 = time.time()

exec_time2 = t4 - t3


t5 = time.time()
if not q.isEmpty():
    while q.items:
        q.dequeue()
t6 = time.time()
exec_time3 = t6 - t5

t7 = time.time()
if not m.items:
    while m.items:
        m.dequeue()
t8 = time.time()
exec_time4 = t8 - t7

print("")
print("----------------------")
print("Enqueue Operations")
print("----------------------")
print("MyQueue Result 1: ",     exec_time)
print("Python Queue Result 2: ", exec_time2)
print("----------------------")
print("Dequeue Operations")
print("----------------------")
print("MyQueue Result 1: ",      exec_time3)
print("Python Queue Result 2: ", exec_time4)

结果：

----------------------
Enqueue Operations
----------------------
MyQueue Result 1:  3.1316871643066406
Python Queue Result 2:  3.1880860328674316
----------------------
Dequeue Operations
----------------------
MyQueue Result 1:  0.028588533401489258
Python Queue Result 2:  9.5367431640625e-07

Answer 1

您可以使用 Python time.time() 来测量每个队列的执行时间。测试应该运行多次，结构中至少有 1000 个元素才能有 "decent" 执行时间。

import time

t1 = time.time()
for i in range(1, 50000):
  m.enqueue(i)
t2 = time.time()
exec_time = t2-t1

使用 m 和 q 执行此操作 enqueue/dequeue 您可以比较执行时间

编辑：如何设计和实施实验以对 python 中的两个队列实施进行基准比较

edit: how to design and implement an experiment to do benchmark comparisons of the two queue implementations in python

python

amortization

amortized-analysis