# Priority queue choice

**URL:** <https://discourse.julialang.org/t/priority-queue-choice/42783>\
**Category:** Performance\
**Created:** [July 9, 2020, 2:12pm UTC](https://discourse.julialang.org/t/priority-queue-choice/42783 "2020-07-09T14:12:30Z")\
**Posts on this page:** 5\
**Page:** 2

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [August 11, 2020, 4:47pm UTC](https://discourse.julialang.org/t/priority-queue-choice/42783/21 "2020-08-11T16:47:11Z")

</div>

Pinging @tim.holy for [https://github.com/JuliaImages/ImageSegmentation.jl/blob/master/src/watershed.jl](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?

---

<div class="post-metadata">

**Author:** ![tim.holy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tim.holy/32/52_2.png) [@tim.holy](https://discourse.julialang.org/u/tim.holy)\
**Post date:** [August 11, 2020, 4:56pm UTC](https://discourse.julialang.org/t/priority-queue-choice/42783/22 "2020-08-11T16:56:01Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [August 11, 2020, 5:45pm UTC](https://discourse.julialang.org/t/priority-queue-choice/42783/23 "2020-08-11T17:45:51Z")

</div>

```julia
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

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

```

---

<div class="post-metadata">

**Author:** ![tim.holy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tim.holy/32/52_2.png) [@tim.holy](https://discourse.julialang.org/u/tim.holy)\
**Post date:** [August 13, 2020, 2:21pm UTC](https://discourse.julialang.org/t/priority-queue-choice/42783/24 "2020-08-13T14:21:27Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [September 1, 2022, 6:49pm UTC](https://discourse.julialang.org/t/priority-queue-choice/42783/25 "2022-09-01T18:49:44Z")

</div>

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>

 ![9E8E0411-BDB5-4424-B545-11EA8A33FD9C](https://global.discourse-cdn.com/julialang/original/3X/2/8/284a6961ea6787c06d1233d5bfed4b1e9ab06892.jpeg)

[Previous page](https://discourse.julialang.org/t/priority-queue-choice/42783.md?page=1)