1
$\begingroup$

In an algorithm I'm designing, I need to do this cycle on a priority queue of constant size N many times, as quickly as possible:

  1. get $K$ highest priority elements (do on them some outside calculation)
  2. append $4K$ kind-of-sorted elements back into the priority queue, removing and ignoring the first $K$ elements from step 1
  3. remove the $3K$ lowest priority elements (in order to keep constant queue size), and return them

In reality, steps 2-3 will probably be merged somehow and so on, but these are the main implementation details.

I'm looking for the fastest implementation of these actions on a priority queue, for a relatively large $N$ and relatively small $K$ (E.G $K=32$, $N=2048$), that can be tweaked a little if needed (E.G change $N\rightarrow 2500$ if it's faster).

I'm not so familiar with data structures, but here's an assortment of things that might work:

  • a sorted array, using $O(1)$ extracts and $O(N)$ merges
  • a pairing heap? weird extract times, but $O(1)$ merges
  • a more exotic heap type? I've found this question for example, with priority queues that technically are quicker at extracts
$\endgroup$

2 Answers 2

0
$\begingroup$

One approach: Store them in a sorted array. To do steps 2 and 3, first sort the list of 4K items, then merge the sorted array of N items with the sorted array of 4K items, then discard the 3K lowest. Merging sorted arrays is easy and can be done in a simple linear scan. As Bulat says, this should be cache-friendly. The asymptotic running time is $O(N)$ per cycle, but since it is cache-friendly it might be fast in practice for the sizes you mention.

Another approach: use a self-balancing binary search tree. Then you can remove the highest K items in $O(K \log N)$ time, and you can append 4K items and then remove the lowest 3K in $O(K \log N)$ time, so the asymptotic running time will be $O(K \log N)$ per cycle. Thus in asymptotic terms this is faster, at least when $N$ is sufficiently large. However, due to the need to follow pointers and the resulting impact on the cache, for the size parameters you mention it might be slower in practice.

$\endgroup$
1
$\begingroup$

If that's practical question, sorted array may be faster than other approaches. The only O(N) operation you will do is memcpy in L1 cache whose speed using AVX2 is 32 bytes per CPU cycle, i.e. ~100 GB/sec.

You will need 2 arrays to make merge. But then you can use spare space for other computations. More complex data structure may easily run out of L1 cache size.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.