1
exercises 중 하나 (즉, # 6)는 큐 구현의 성능 (목록 끝 부분의 머리 부분)을 비교하도록 요청합니다. 약간의 차이가있을 수있는 것처럼 들리므로, 나는 그것을 알아 내려고 노력했다. 여기파이썬에서 큐 구현 간의 차이점
import timeit
class QueueStart(object):
'''Queue implementation with head in the beginning of a list'''
def __init__(self):
self.items = []
def enqueue(self, i):
self.items.append(i)
def dequeue(self):
return self.items.pop(0)
def isEmpty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
class QueueEnd(object):
'''Queue implementation with head at the end of a list'''
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.insert(0, item)
def dequeue(self):
return self.items.pop()
def isEmpty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
# store results for further plotting
start_add_list = [] # QueueStart.enqueue(item) runtimes for inputs of different sizes
start_pop_list = [] # the same for QueueStart.dequeue(item)
end_add_list = [] # the same for QueueEnd.enqueue(item)
end_pop_list = [] # the same for QueueEnd.dequeue(item)
for i in range(100000, 500000, 10000):
qs = QueueStart()
qs.items = list(range(i))
qe = QueueEnd()
qe.items = list(range(i))
start_add = timeit.Timer('qs.enqueue(1)', 'from __main__ import qs')
start_pop = timeit.Timer('qs.dequeue()', 'from __main__ import qs')
end_add = timeit.Timer('qe.enqueue(1)', 'from __main__ import qe')
end_pop = timeit.Timer('qe.dequeue()', 'from __main__ import qe')
start_add_list.append(start_add.timeit(number=1000))
start_pop_list.append(start_pop.timeit(number=1000))
end_add_list.append(end_add.timeit(number=1000))
end_pop_list.append(end_pop.timeit(number=1000))
그리고 여기가 내 실험 
insert 및 pop(index)는 O (n)이있는 것으로 알려져 결과를 반영 플롯입니다 내 코드입니다. 흥미로운 점은 그래프에서 볼 때 insert(0, item)은 pop(0)의 두 배가 걸리는 것을 볼 수 있습니다. 그 관찰은 저에게 이것이 왜 그런지 궁금합니다. 표면적으로 볼 때 두 가지 방법이 매우 유사하지만 외관상으로는 흥미로운 점이 있습니다. 그래서, 질문은 : 당신이 그것을 알아 내도록 도울 수 있습니까?
이것은 기본 배열에 추가하고 삭제할 때 작업이 메모리를 관리하는 방법에 따라 구현에 따라 다를 수 있습니다. 예를 들어,'pop (0)'은 어떤 배열 요소가'[0]'인지를 바꿀 수있는 반면,'insert (0, ...)'는 한 슬롯 위로 모든 것을 계속해서 푸시해야 할 것입니다. 배열의 앞쪽에. – chepner
@chepner : 운동에서 나오는 책의 제목은 : "pop이리스트의 끝에서 호출되면 그것은 O (1)을 취하지 만, pop이리스트의 첫 번째 요소 나 중간에있는 어떤 곳에서 호출 될 때 O (n)이 이유는 파이썬이리스트를 구현하는 방법에있다. **리스트 앞에서 항목을 가져올 때, 파이썬의 구현에서,리스트의 다른 모든 원소들은 한 위치에서 시작 부분으로 더 가깝게 이동한다. **. " 알다시피,'insert (0, ...)'와'pop (0)'모두 최악의 경우에 교대조를 만들지 만, 상수 요인의 차이가 어디에서 유래하는지는 분명하지 않다. –