**commit** 8199d0aa11068a7ca6fbffea94e781bbaebf8734
**parent** 442898cd2cef5b3c52efb9f5017da42931d7c6d2
**Author:** Sol <sol@plunder.tech>
**Date:** Sat, 2 Sep 2023 12:02:28 -0400
rts: setInteresectionGeneric uses only 2 searches
- Do an initial check to see if there sets are disjoint before doing
any work.
- Instead of doing two searches to determine the lower bound of each
set, compare the smallest element of each set. The lower-bound of
the greater set will always be zero.
- Same logic for the upper bound.
This saves two binary searches on every intersection, at the price of
just two comparisons.
**Diffstat:**

1 file changed, 30 insertions(+), 7 deletions(-)

**diff --git a/lib/Data/Sorted/Set.hs b/lib/Data/Sorted/Set.hs**
@@ -238,16 +238,39 @@ ssetIntersection x@(SET xs) y@(SET ys) =
if ssetMember yv x then ssetSingleton yv else mempty
( xw, yw ) -> ssetIntersectionGeneric x xw y yw
+-- This assumes that neither of the inputs are empty.
+--
+-- TODO: Skip the shrinking optimization if the sizes are small.
ssetIntersectionGeneric :: Ord a => Set a -> Int -> Set a -> Int -> Set a
ssetIntersectionGeneric (SET xs) !xWid (SET ys) !yWid =
- coerce $ runST do
- -- Find the overlapping range of the the sets so we can walk merely the
- -- parts we know overlap
- let xMin = bsearchIndex (ys!0) xs
- let xMax = bsearchPostIndex (ys ! (yWid-1)) xs
- let yMin = bsearchIndex (xs!0) ys
- let yMax = bsearchPostIndex (xs ! (xWid-1)) ys
+ let
+ xSmallest = xs ! 0
+ xLargest = xs ! (xWid-1)
+ ySmallest = ys ! 0
+ yLargest = ys ! (yWid-1)
+ in
+
+ -- If there is no overlap, then the intersection is empty.
+ if xSmallest > yLargest then mempty else
+ if ySmallest > xLargest then mempty else
+
+ -- Find the overlapping range of the the sets so we can walk merely the
+ -- parts we know overlap
+ let
+ (xMin, yMin) =
+ case compare xSmallest ySmallest of
+ EQ -> (0, 0)
+ GT -> (0, bsearchIndex xSmallest ys)
+ LT -> (bsearchIndex ySmallest xs, 0)
+
+ (xMax, yMax) =
+ case compare xLargest yLargest of
+ EQ -> (xWid, yWid)
+ GT -> (bsearchPostIndex yLargest xs, yWid)
+ LT -> (xWid, bsearchPostIndex xLargest ys)
+ in
+ coerce $ runST do
let rWid = min (xMax - xMin) (yMax - yMin)
buf <- newArray rWid (error "setIntersection: uninitialized")
let go o i j = do