[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

efficient set computations

In regard to (in)efficiency of union in Genera, I suppose
most people know that basic set operations can be done
in linear time if the objects are taggable.  The tagging
can be done on plists or via object slots (won't work
for numbers and other basic types).

Thus, for the union of A and B, all elements of A are given
the same unique tag.  Any untagged element in B is added
to A (or to a copy, as you like).  Duplicates can be
avoided by fancier tagging schemes and checking before tagging.
Intersection is done by selecting only tagged items from B.

All this assumes object identity, so it is strictly
an eq operation.  For equal, can build hash table and 
check that.  We use the tagging approach for handling
large collections of CLOS objects by mixing in a tag slot.

bob futrelle
biological knowledge lab
northeastern u, boston

"The opinions expressed here are just that."