Most active commenters
  • math-hiyoko(3)

Show HN: High-Performance Wavelet Matrix for Python, Implemented in Rust

(pypi.org)
91 points math-hiyoko | 11 comments | 17 Dec 25 19:35 UTC | HN request time: 0.915s | source | bottom

I built a Rust-powered Wavelet Matrix library for Python.

There were surprisingly few practical Wavelet Matrix implementations available for Python, so I implemented one with a focus on performance, usability, and typed APIs. It supports fast rank/select, top-k, quantile, range queries, and even dynamic updates.

Feedback welcome!

1. koolala ◴[18 Dec 25 04:54 UTC] No.46309000[source]▶
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?
replies(1): >>46309220 #
2. mrkeen ◴[18 Dec 25 05:37 UTC] No.46309220[source]▶
> 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.

3. atoav ◴[18 Dec 25 08:29 UTC] No.46310203[source]▶
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.

replies(1): >>46318098 #
4. yourdetect ◴[18 Dec 25 09:12 UTC] No.46310473[source]▶
Does this contain unsafe? Even the Linux kernel's Rust code have memory safety bugs. https://news.ycombinator.com/item?id=46309536
replies(2): >>46310553 #>>46310560 #
5. simgt ◴[18 Dec 25 09:23 UTC] No.46310553[source]▶
> git clone https://github.com/math-hiyoko/wavelet-matrix.git && find wavelet-matrix -type f -name '*.rs' -exec grep 'unsafe' {} +

No.

6. math-hiyoko ◴[18 Dec 25 09:25 UTC] No.46310560[source]▶
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.
7. joshlk ◴[18 Dec 25 10:14 UTC] No.46310886[source]▶
What's a good reference to learn about Wavelet Matrices?
replies(1): >>46311305 #
8. mrkeen ◴[18 Dec 25 11:12 UTC] No.46311305[source]▶
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.

9. kennykartman ◴[18 Dec 25 14:08 UTC] No.46312842[source]▶
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!
10. math-hiyoko ◴[18 Dec 25 20:19 UTC] No.46318098[source]▶
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.