Closed DoubleHyphen closed 3 years ago
Branch with benchmark of linden: https://github.com/becheran/fast-hilbert/tree/linden-bench
Thank you so much! Now, let's see.
hilbert
's, so I don't think there's much meaning in making further comparisons. In any event, it appears that the speedup was 5x. Significant, but I'll admit I was hoping for more… hilbert
's crate maintainer had described the algorithm used therein as very fast, so at the very least I'd have expected it to match the implementation you found on Wikipedia instead of being twice as slow.hilbert
calls “amount of bits to examine”. In the beginning, I thought that Hilbert encoding was like Morton encoding, in that I expected it to be insensitive to all leading zeros. This, in the general case, is not true. What I noticed whilst refactoring, however, is that all leading zeros that come in multiples of D (where D is the amount of dimensions) can be safely ignored without changing the final result. fast_hilbert
and experiment a bit and let you know.Here is the code I used for the experiments in 2.:
for _ in 0..1024 {
let x = rand::random::<u32>() & 65535;
let y = rand::random::<u32>() & 65535;
let original_key = fast_hilbert::xy2h(x, y, 32);
println!("x: {:010}\ny: {:010}\nkey: {}", x, y, original_key);
for i in (16..32).step_by(2) {
let new_key = fast_hilbert::xy2h(x, y, i);
assert_eq!(original_key, new_key);
}
}
order
parametre (which I call, with no small amount of perverse joy, disorderly) and instead calculates the ideal order
based on x
and y
. Benchmark it and see; I suspect the speed won't have changed much, if at all.
(And also, as I mentioned: The pattern repeats every D
bits, which in this case is 2 because you're examining a 2-D curve.)
lindel
crate in the benchmarks you produce? Mr Chernoch's code has some… inefficiencies, let's say, which I took upon myself to correct. I don't think it'll come anywhere remotely close to your own speed, but I also suspect it'll at least fall within the same ball-park as the other crates.u8
s oru16
s would be trivial, but the part about the arbitrary dimensions will take a bit more thought methinks.Thanks in advance!