Comparing deque maintaining sorted order and a heap

from random import seed, randint from collections import deque from bisect import insort from heapq import heapify, nsmallest from time import perf_counter import matplotlib.pyplot as plt def find_min(deq_len, nums): elems = nums[:deq_len] elems.sort() deq = deque(elems, maxlen=deq_len) for num in nums[deq_len:]: if num < deq[-1]: deq.pop() insort(deq, num) return deq seed(0) deq_len = 15 nums = [randint(0,10000) for i in range(1000)] s = perf_counter() min_bisect_deque = list(find_min(deq_len, nums)) e = perf_counter() bisect_deque_time = e-s heapify(nums) s = perf_counter() min_heap = nsmallest(deq_len, nums) e = perf_counter() heap_time = e-s assert min_bisect_deque == min_heap # Plot results labels = ['sorted deque', 'heap'] x_coords, y_coord = [0.34, 1.05], 0.00006 plt.title('''Comparing a deque, maintaining sorted order and a heap\n to find the smallest elements in a long sequence''') [0.5, 1.1], [bisect_deque_time, heap_time], width=0.5, lw=1, color=['#BCCDE8','#B1A6CA'], edgecolor='black', alpha=0.7 ) for i, label in enumerate(labels): plt.annotate(label, xy=(x_coords[i], y_coord), fontsize=16, color='white') plt.xticks([]) plt.ylabel('Time (s)') plt.tight_layout() Comparing a deque and a heap to extract the smallest items from a sequence

The deque doesn't seem nearly as efficient, but it may still be an alternative if a heap is not available. We keep only as much data as needed while moving through the entire sequence, which may be available as a stream.