Neat data structure: "Ullman" set(onebadseed.com)
onebadseed.com
Neat data structure: "Ullman" set
http://www.onebadseed.com/blog/?p=80
4 comments
But AFAICT, the pop and restore operations stop working once you call del. But if your algorithm only ever adds and backtraces, you should be fine (if you know how many elements you will add or are happy to realloc your arrays from time to time, making add logarithmic).
The "set stack" and map ideas down at the bottom suggest a variant since I was just reading about A* search: a "set priority queue" that keeps the Ullman map's parallel members and values arrays in heap order according to the values. I'm thinking this might be good for A* when the search nodes can be denoted by dense-integer keys but the distances vary over a wider range.
It seems to me the probability of a false positive membership test is non-zero.
No, it's correct -- you can see that by induction on the add operation. If you're allowed to increase n without first ensuring the invariant on the first n members, then it can break, yes.
Yes you're right. Thanks.
This is a rather useless data structure:
You can only store integers and they must be in the range of [0, n>. The simple operations are O(1), because you can just map the positions of all integers based on their value in a second array of size n.
You can only store integers and they must be in the range of [0, n>. The simple operations are O(1), because you can just map the positions of all integers based on their value in a second array of size n.
You're not using it to replace a container ADT. You're using it for a low-overhead fast membership test. When things only store integer keys, usually that implies that you have a fast integer-keyed store for the rest of the information. Most trie implementations work the same way.
The cheap iteration is a big plus of this data structure over a simple set.