1) reset, or rather batch deleting all its members 2) iterating over its members only take O(n) time.
Disadvantage of Ullman set: can only process Integer smaller than N, if we can't know the upperbound of its members, Ullman set can do nothing about this, which in contrast is the advantage of hashmap.
Sent to you by jeffye via Google Reader:
via Research on Search by Dell Zhang on 2/23/09The Ullman set is a clever data structure for a set of n integers densely distributed over a range, say from 0 to N-1. It uses O(N) space, and supports construction, destruction, adding, deleting, membership-test as well as cardinality operations in O(1) time. Moreover iterating over its members only takes O(n) time.
Things you can do from here:
- Subscribe to Research on Search using Google Reader
- Get started using Google Reader to easily keep up with all your favorite sites
Post a Comment