Menu
What is a good way to represent sparse set of integers (really C memory addresses) in a compact and fast way. I already know about the obvious things like bit-vectors and run-length encoding. but I want something much more compact than one word per set element. I need to add and remove elements and test for membership. I do not need other set operations, like union.
I read about one such library many years ago but have since forgotten its name. I think it was released as open source by HP and had a womans name.
568
A sparse set is a specialized data structure for representing a set of integers. It can be useful in some very narrow and specific cases, namely when the universe of possible values is very large but used very sparingly and the set is iterated often or cleared often.
The sparse array is an array in which most of the elements have the same value(the default value is zero or null). Sparse matrices are those array that has the majority of their elements equal to zero. A sparse array is an array in which elements do not have contiguous indexes starting at zero.
To check whether a matrix is a sparse matrix, we only need to check the total number of elements that are equal to zero. If this count is more than (m * n)/2, we return true.
You are referring to a judy array. It was a HP project. I think they are used in ruby and are available in c. Very interesting data structure. Making use of the fact that allocations are (at least) word aligned, having separate structures for dense and sparse ranges.
http://judy.sourceforge.net/index.html
72
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
