preface
Recently started learning algorithms ,python Books are 《python-data-structure-cn》
From books :python The designer has many choices when implementing the list data structure . Each of these choices can affect the performance of the list operation
. To help them make the right choice , They looked at the most commonly used list data structures , And optimize the implementation , To make the most common operations very fast
. of course , They also try to make less common operations faster , But when a compromise is needed , The performance of less common operations is often sacrificed to support more common operations .
Common operations and time complexity
pop() ,pop(i) ,sort() test
* pop() As the list size becomes larger, it shows a steady trend
* and pop(0) A linear regression of one variable is presented
sort() be relative to pop(0) The time consumption is greatly increased
General layout
code
# coding:utf-8 import timeit from timeit import * from matplotlib import
pyplot import matplotlib.pyplot as plt pop_nlogn = [] popzero_nlogn = []
sort_nlogn = [] pop = Timer("test_list.pop()", "from __main__ import
test_list") popzero = Timer("test_list.pop(0)", "from __main__ import
test_list") sort = Timer("test_list.sort()", "from __main__ import test_list")
x = list(range(1000,4000,1000)) for i in x: test_list = list(range(i))
pop_nlogn.append(pop.timeit(number = 100)) test_list = list(range(i))
popzero_nlogn.append(popzero.timeit(number = 100)) test_list = list(range(i))
sort_nlogn.append(sort.timeit(number = 100)) plt.plot(x,
pop_nlogn,marker='o',label='pop_nlogn') plt.plot(x,
popzero_nlogn,marker='o',label='popzero_nlogn') plt.plot(x,
sort_nlogn,marker='o',label='sort_nlogn') plt.legend() # Make the legend work plt.xlabel('n
size') # X Axis label plt.ylabel("time use") # Y Axis label plt.show()
Technology
Daily Recommendation