Neat data structure: "Ullman" set
onebadseed.com
Neat data structure: "Ullman" set
1–9 of 9 posts
Re: Neat data structure: "Ullman" set
#2It seems to me the probability of a false positive membership test is non-zero.
Re: Neat data structure: "Ullman" set
#3It 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.
Re: Neat data structure: "Ullman" set
#4The "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.
Re: Neat data structure: "Ullman" set
#5It 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.
Re: Neat data structure: "Ullman" set
#6But 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).
Re: Neat data structure: "Ullman" set
#7This 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.
Re: Neat data structure: "Ullman" set
#8This 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'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.
Re: Neat data structure: "Ullman" set
#9This 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.
The cheap iteration is a big plus of this data structure over a simple set.