python中两种栈实现方式的性能对比

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

在计算机的世界中，同一个问题，使用不同的数据结构和算法实现，所使用的资源有很大差别

为了方便量化python中算法的资源消耗，对性能做测试非常有必要，这里针对stack做了python语言

下的性能分析。为后续算法分析做个基础。

代码：

import timeitfrom timeit import Timerclass Stack:
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def push(self,item):
self.items.append(item)
def pop(self):
return self.items.pop() def peek(self):
return self.items[len(self.items) - 1]
def size(self):
return len(self.items)
s = Stack()class StackA:
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def push(self,item):
self.items.insert(0,item)
def pop(self):
return self.items.pop(0) def peek(self):
return self.items[0]
def size(self):
return len(self.items)s1 = StackA()print("stack performing test:")
def stack_push_test():
for i in range(1000):
s.push('dog')def stack_pop_test():
for i in range(1000):
s.pop()t1 = Timer("stack_push_test()","from __main__ import stack_push_test")
print("stack_push_test ",t1.timeit(number=100),"milliseconds")
t2 = Timer("stack_pop_test()","from __main__ import stack_pop_test")
print("stack_pop_test ",t2.timeit(number=100),"milliseconds")print("stackA performing test:")
def stacka_push_test():
for i in range(1000):
s1.push('dog')def stacka_pop_test():
for i in range(1000):
s1.pop()t3 = Timer("stacka_push_test()","from __main__ import stacka_push_test")
print("stacka_push_test ",t3.timeit(number=100),"milliseconds")
t4 = Timer("stacka_pop_test()","from __main__ import stacka_pop_test")
print("stacka_pop_test ",t4.timeit(number=100),"milliseconds")

在linux上运行的主频为2.4G的系统上运行结果：

stack performing test:
('stack_push_test ', 0.020203113555908203, 'milliseconds')
('stack_pop_test ', 0.02147078514099121, 'milliseconds')
stackA performing test:
('stacka_push_test ', 2.8804190158843994, 'milliseconds')
('stacka_pop_test ', 1.8630762100219727, 'milliseconds')

可以看出，不同的stack实现，对性能的影响是巨大的，显然是第一种stack实现的效率比较高。

具体原因是两者的算法复杂度是不一样的，第一种是O(1）第二种是O(n).