On Mon, Jul 30, 2012 at 4:43 PM, Peter Bergner <berg...@vnet.ibm.com> wrote: > On Fri, 27 Jul 2012 15:40:35 +0200 Richard Guenther > <richard.guent...@gmail.com> wrote: >> Also it looks less efficient than sbitmap in the case when >> your main operation is adding to the set and querying the set randomly. > > How so? Adding/deleting a member to a sparseset is an O(1) operation, > as is querying whether something is/isn't a member of a sparseset. > Or are you talking about slower by some small constant factor?
No, but less space efficient and of comparable speed as sbitmap which is also O(1). >> It's space overhead is really huge - for smaller universes a smaller >> SPARSESET_ELT_TYPE would be nice, templates to the rescue! I >> wonder in which cases a unsigned HOST_WIDEST_FAST_INT sized >> universe is even useful (but a short instead of an int is probably too >> small ...) > > Yes, space overhead it large, but the extra space overhead allows sparseset > to have O(1) operations for most set functions and O(N) for iterating over > the members of the set. Obviously, you don't want to use this as in general > set usage, but where speed is critical, it has its uses. True. Richard. > Peter >
