Fast(er) priority queues?

mschauer · September 1, 2022, 6:47pm

For what it is worth I implemented a sort of priority queue which keeps track of local minima instead of a single global minimum. Keys are real priorities and a fix index set 1:n (coordinates). You need a graph to define which sense of “locally this coordinate is the next thing to work on” you want.

An advantage is that it allows parallelism (work on local minima which are separated enough to not interfere with each other). I made the structure thread safe in this sense.

For my usecase it’s working nicely … not sure if useful for others. I leave a demo and if you are interested I can explain a bit more.

gist.github.com

https://gist.github.com/mschauer/54c6baf5ced6160ef7acaa13463e0b9c

partialqueue.jl

#=
ZigZagBoomerang.jl has implemented something like a priority queue keeping track of 
local minima (or high priority task).

Think of graph where vertices are tasks that are assigned priorities (smaller = higher priority) 
and edges between two tasks indicate if the higher priority task has to be worked on before the
lower priority task (edge) or both can be worked on in parallel (no edge).

It’s thread-safe in the sense that priorities can be updated in different threads 
if one has a proper coloring of the vertices and updates the task of one color in @threads

This file has been truncated. show original