ViewVC logotype

Revision 14

Jump to revision: Previous Next
Author: sburson
Date: Mon Jun 11 01:34:38 2007 UTC (6 years, 10 months ago)
Changed paths: 2
Log Message:
Added historically-related set/bag/map optimization.

This optimization applies to `union', `intersection', `set-difference',
`set-difference-2', `bag-difference', and `map-merge'; and `compare' on
sets, bags, and maps.  (Of these, the difference operations are probably the
ones on which it is most useful.)  It very cheaply detects cases where the
two operands share some of their subtrees, and takes the appropriate
shortcut.  (For example, the set-difference of a subtree and itself is the
empty set.)  The two operands are likely to share some subtrees if they are
historically related; e.g., if one is the result of performing a small
number of `with' and/or `less' operations on the other, or if both of them
are related in this way to a third collection.  In such cases, these
algorithms can now run in log time rather than linear time, making this a
potentially quite significant optimization.

Changed paths:

Path Details
Directorytrunk/Code/fset.lisp modified , text changed
Directorytrunk/Code/wb-trees.lisp modified , text changed

  ViewVC Help
Powered by ViewVC 1.1.5