Increasing the performance of python heapq?

532 Views Asked by At

I'm looking to improve the speed at which I can remove (pop) the smallest item from a list or array while also adding items on the fly. The maximum number of items is fixed, so I could use initialized numpy arrays but so far I've seen the best performance with heapq. Below is my implementation is Cython, the dummy code below runs in about 0.7 seconds.

Is anything better possible within Python? I've briefly looked at sorted lists (https://pypi.org/project/sortedcontainers/) but saw no performance improvement. Will I see a noticeable improvement by switching to pure C? In my full code I only need to use the heappush and heappop operations.

from _heapq import *
cdef int i
cdef list openHeap = []

for i in range(320000*8):
    heappush(openHeap, (i, 22))

EDIT: To clarify, in the full code the values being pushed to the heap are not in any sorted or predefined order (hence using the heap to efficiently find the minimum value).

0

There are 0 best solutions below