fp.

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!

Comments

koolala•1mo ago

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?

mrkeen•1mo ago

> 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.

atoav•1mo ago

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.

math-hiyoko•1mo ago

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.

yourdetect•1mo ago

Does this contain unsafe? Even the Linux kernel's Rust code have memory safety bugs. https://news.ycombinator.com/item?id=46309536

simgt•1mo ago

> git clone https://github.com/math-hiyoko/wavelet-matrix.git && find wavelet-matrix -type f -name '*.rs' -exec grep 'unsafe' {} +

No.

math-hiyoko•1mo ago

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.

joshlk•1mo ago

What's a good reference to learn about Wavelet Matrices?

mrkeen•1mo ago

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.

kennykartman•1mo ago

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!