fast_hilbert
| Crates.io | fast_hilbert |
| lib.rs | fast_hilbert |
| version | 2.0.0 |
| source | src |
| created_at | 2021-02-11 22:42:37.220885 |
| updated_at | 2022-10-31 21:08:01.662233 |
| description | Fast Hilbert 2D curve computation using an efficient Lookup Table (LUT). |
| homepage | |
| repository | https://github.com/becheran/fast-hilbert |
| max_upload_size | |
| id | 353969 |
| size | 57,381 |
Armin Becher (becheran)
documentation
README
Fast Hilbert
Fast Hilbert 2D curve computation using an efficient Lookup Table (LUT) and only considering the lowest order for a given input.
- Convert from discrete 2D space to 1D hilbert space and reverse
- Generalized for different unsigned integer input types (thanks DoubleHyphen PR#3)
- Speedup via lowest order computation (thanks DoubleHyphen PR#2)
- Very fast using an efficient 512 Byte LUT
- Only one additional dependency
Benchmarking the conversion from full 256x256 discrete 2D space to the 1D hilbert space, shows that fast_hilbert is about 12 times faster compared to the fastest 2D hilbert transformation libs written in rust. Benchmarked on a Intel i5-6400 CPU @ 2.70 GHz, 4 Cores with 8 GB RAM:
| Library | Time | Description |
|---|---|---|
| fast_hilbert | 0.2 ms | Optimized for fast computation in 2D discrete space using an efficient LUT |
| hilbert_2d | 2.5 ms | Also allows other variants such as Moore and LIU |
| hilbert_curve | 2.0 ms | Implements algorithm described on Wikipedia |
| hilbert | 32.1 ms | Allows computation of higher dimensional Hilbert curves |
Especially for higher orders fast_hilbert outperforms other libraries by using only the next lowest relevant order instead of computing the hilbert curve bit per bit for the given input. See PR #2 and #9 for more details.
For example the computation of xy2h(1, 2, 64) is very fast to compute using fast_hilbert compared to a higher x,y pair such as xy2h(u32::MAX-1, u32::MAX-2, 64):
| Library | x=1, y=2, order=64 | x=u32::MAX-1, y=u32::MAX-2, order=64 |
|---|---|---|
| fast_hilbert | 4 ns | 29 ns |
| hilbert_2d | 73 ns | 72 ns |
| hilbert_curve | 67 ns | 49 ns |
| hilbert | 690 ns | 680 ns |