I couldn't think of a good way to remove duplicates - since you can just stick the last item in its place. However, after sleeping on it, I realize I can simply move the duplicate to the front and slice off the front duplicate part. I'll try it tonight when I get back!
Michael T. Jones
Chief Technology Advocate, Google Inc.
1600 Amphitheatre Parkway, Mountain View, California 94043
Email: m...@google.com Mobile: 650-335-5765 Fax: 650-649-1938
Organizing the world's information to make it universally accessible and useful
...
> The Add code is a little faster without the range check. It is also a little
> faster with index and mask computed as variables and reused between the test
> and the assignment. (This kind of simple common sub expression elimination
> is something we can hope for in future compilers.) It runs fastest on my
> machine with bytes as the bit set datatype. Remove(), were it one of your
> functions, would be like Add() but would test for set, use &^ to clear the
> bit, and decrement the count. This simple approach is O(1) for add, remove,
> and count -- great when you can afford the storage.
>
> Michael
And if storage is a specific issue (because you might have a larger
range), you can put a tree structure in place. So at the top level, you
mask out the first N bits, pointing into an array of arrays, etc.
You trade off a little bit of performance (because now you have to jump
through the arrays), but you can save potentially lots of memory.
(Depending on how well your data is grouped into sub-ranges.)
John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
iEYEARECAAYFAk4ircIACgkQJdeBCYSNAAM56QCgqnXNUX3Qi6y/X8xgZKyMlCXT
8ccAnRhPHLhfoiGqjD1W8FZwWr2nsjPB
=09ip
-----END PGP SIGNATURE-----