Priority queue choice

[mschauer]

Pinging @tim.holy for https://github.com/JuliaImages/ImageSegmentation.jl/blob/master/src/watershed.jl applications. This could profit from a vector + index map based implementation as above instead of Dict based implementation?

[tim.holy]

It seems quite possible. I scanned the thread above but didn’t see any benchmarks, did I miss them? The other issues is that the watershed needs CartesianIndexes because we loop over neighbors. But perhaps a conversion step would be adequate.

It would be worth profiling to figure out the bottlenecks before taking any other action.

[mschauer]

using DataStructures, BenchmarkTools
using Random, ZigZagBoomerang

function poisson_concert(n, T, Q = PriorityQueue{Int,Float64}())
    out = Int[]
    t = 0.0
    for i in 1:n
        enqueue!(Q, i => randexp())
    end
    while t < T
        i, t = peek(Q)
        Q[i] = t + randexp()
        push!(out, i)
    end
    out
end

spoisson_concert(n, T) = poisson_concert(n, T, ZigZagBoomerang.SPriorityQueue{Int,Float64}())


using TrackingHeaps

function poisson_concert(n, T, Q::TrackingHeap)
    out = Int[]
    t = 0.0
    for i in 1:n
        track!(Q, randexp())
    end
    while t < T
        i, t = TrackingHeaps.top(Q)
        Q[i] = t + randexp()
        push!(out, i)
    end
    out
end
tpoisson_concert(n, T) = poisson_concert(n, T, TrackingHeap(Float64, S=NoTrainingWheels()))

@btime poisson_concert(100, 1000.0)
@btime spoisson_concert(100, 1000.0)
@btime tpoisson_concert(100, 1000.0)

gives

16.993 ms (34 allocations: 2.01 MiB)
9.042 ms (31 allocations: 2.01 MiB)
5.398 ms (44 allocations: 2.01 MiB)

[tim.holy]

That does seem promising. Provided that the lookup of the CartesianIndex doesn’t erase the benefit, I’d definitely be open to an alternate implementation.

Benchmarks for all of JuliaImages are very much on the TODO list these days, which would make this kind of thing easier to analyze.

[mschauer]

Cross Post: 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.

Illustration: Changing the priority of two local minimum indices in a line graph changes some neighbouring indices into local minima.

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