I am using a priority queue to search paths on an integer lattice. In general, there is not a unique minimum element in the priority queue, so I augment the priorities with a value that is designed to break ties deterministically. This ensures that the search order does not depend on how the priority queue itself breaks ties. Setting different seeds for this hash also lets me get different paths, corresponding to different arbitrary choices made during the search algorithm.
For example, in the priority queue I may have two paths with the same priority:
2 => [(1, 1), (1, 2)] 2 => [(1, 1), (2, 1)]
and to break ties, I do
(2, 0xcafecafe) => [(1, 1), (1, 2)] (2, 0xbeefbeef) => [(1, 1), (2, 1)]
0xcafecafe is derived from
[(1, 1), (1, 2)] and some seed, and
0xbeefbeef is derived, with the same computation, from
[(1, 1), (2, 1)] and the same seed.
I have been using
hash to generate these tie-breaker values, however I notice that it seems to be not ideal. In the first place,
hash is allowed to change between versions of Julia. That doesn’t bother me too much.
I would like these numbers to be closer to 0.5:
julia> f(n) = count(x -> hash((1, 2), x) > hash((2, 1), x), rand(UInt64, n)) / n f (generic function with 1 method) julia> f(1_000_000) 0.434676 julia> f(1_000_000) 0.434022 julia> f(1_000_000) 0.434066 julia> f(1_000_000_000) 0.434203099
I would like to avoid using a RNG with “external” state. It would be nice to preserve ties between paths that are actually equal.
Any recommendations or keywords?