Thank you for sharing! It's great to have more wavelet libraries. I don't often use those, but when I do the choice is scarce. It's great to have another option!
> Can a wavelet be used with SIMD 128bit operations?
Popcount works great in this context, but that only gives you linear speedups. Doing rank/select in O(1) instead of O(N) is a bigger win, and you get that by precomputing superblocks.
> Or are they used with 4x4 Matrix operators? Are wavelets good for that kind of math?
Nope, different kind of matrix. Just refers to a nicer packing of a wavelet tree with space wasted by bookkeeping pointers between tree nodes.
No, the library itself does not use unsafe Rust at all.
The Python bindings are built using PyO3, which internally uses unsafe (as required to interface with the CPython C API), but that is fully encapsulated within PyO3. The core data structure and algorithms remain purely safe Rust.
Looks good to me. Have you considered adding a really practical realworld example? As someone who loves looking at examples I like your small examples in the readme, but it still leaves me wondering a bit what I actually would use this library for.
Many people don't know what you would use wavelets for or where they really shine. I for example know wavelets are used in image compression algorithms but that's about it. I am curious where else this could be applied.
Thanks for the feedback!
You're right, just listing features doesn't make the use cases very clear.
I'm planning to add more concrete, real-world examples to the README and examples to better show where wavelet matrices really shine.
Thank you for sharing! It's great to have more wavelet libraries. I don't often use those, but when I do the choice is scarce. It's great to have another option!
Can a wavelet be used with SIMD 128bit operations? Or are they used with 4x4 Matrix operators? Are wavelets good for that kind of math?
> Can a wavelet be used with SIMD 128bit operations?
Popcount works great in this context, but that only gives you linear speedups. Doing rank/select in O(1) instead of O(N) is a bigger win, and you get that by precomputing superblocks.
> Or are they used with 4x4 Matrix operators? Are wavelets good for that kind of math?
Nope, different kind of matrix. Just refers to a nicer packing of a wavelet tree with space wasted by bookkeeping pointers between tree nodes.
Does this contain unsafe? Even the Linux kernel's Rust code have memory safety bugs. https://news.ycombinator.com/item?id=46309536
No, the library itself does not use unsafe Rust at all. The Python bindings are built using PyO3, which internally uses unsafe (as required to interface with the CPython C API), but that is fully encapsulated within PyO3. The core data structure and algorithms remain purely safe Rust.
> git clone https://github.com/math-hiyoko/wavelet-matrix.git && find wavelet-matrix -type f -name '*.rs' -exec grep 'unsafe' {} +
No.
What's a good reference to learn about Wavelet Matrices?
Start with Wavelet trees (much more intuitive): https://www.alexbowe.com/wavelet-trees/
The matrix version is just an implementation detail to store the tree in a less tree-like shape so you don't need as many pointers.
Looks good to me. Have you considered adding a really practical realworld example? As someone who loves looking at examples I like your small examples in the readme, but it still leaves me wondering a bit what I actually would use this library for.
Many people don't know what you would use wavelets for or where they really shine. I for example know wavelets are used in image compression algorithms but that's about it. I am curious where else this could be applied.
Thanks for the feedback! You're right, just listing features doesn't make the use cases very clear. I'm planning to add more concrete, real-world examples to the README and examples to better show where wavelet matrices really shine.