optimize `PSet.intersect()`

hrldcpr / pcollections

A Persistent Java Collections Library

Other

765 stars 79 forks source link

optimize `PSet.intersect()` #103

Open hrldcpr opened 2 years ago

hrldcpr commented 2 years ago

[ ] if the passed list is a Set, then iterate over whichever set is smaller, so we get O(mlgn) complexity, with m<n
[ ] benchmark that this is actually faster

hrldcpr commented 2 years ago

(Also, is there a heuristic for plus-ing the intersection up from empty if it's small, versus minus-ing it down from full (as the current code does) if it's big? Probably nothing consistent…)