在计算机的世界中，同一个问题，使用不同的数据结构和算法实现，所使用的资源有很大差别
为了方便量化python中算法的资源消耗，对性能做测试非常有必要，这里针对stack做了python语言
下的性能分析。为后续算法分析做个基础。
代码：
import timeit from timeit import Timer class 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).