Repository : ssh://[email protected]/containers On branch : ghc-head Link : http://git.haskell.org/?p=packages/containers.git;a=commit;h=f74c0d40502a9e5ccb827ef20284799692664b55
>--------------------------------------------------------------- commit f74c0d40502a9e5ccb827ef20284799692664b55 Author: Milan Straka <[email protected]> Date: Sun Nov 11 15:57:16 2012 +0100 Remove from docs that hedge-union is faster in (big `union` small) case. As measured by SetOperations-Set.hs and SetOperations-Map.hs benchmarks, it is not the case. Depending on the relative order of elements in the set/map, both (big `union` small) and (small `union` big) cases can be faster than the other. >--------------------------------------------------------------- f74c0d40502a9e5ccb827ef20284799692664b55 Data/Map/Base.hs | 11 ++++++----- Data/Map/Strict.hs | 8 ++++---- Data/Set/Base.hs | 6 +++--- 3 files changed, 13 insertions(+), 12 deletions(-) diff --git a/Data/Map/Base.hs b/Data/Map/Base.hs index 146c5f3..8fe866c 100644 --- a/Data/Map/Base.hs +++ b/Data/Map/Base.hs @@ -1191,7 +1191,6 @@ unionsWith f ts -- It prefers @t1@ when duplicate keys are encountered, -- i.e. (@'union' == 'unionWith' 'const'@). -- The implementation uses the efficient /hedge-union/ algorithm. --- Hedge-union is more efficient on (bigset \``union`\` smallset). -- -- > union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")] @@ -1232,7 +1231,6 @@ unionWith f m1 m2 -- | /O(n+m)/. -- Union with a combining function. The implementation uses the efficient /hedge-union/ algorithm. --- Hedge-union is more efficient on (bigset \``union`\` smallset). -- -- > let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value -- > unionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "5:a|A"), (7, "C")] @@ -1311,6 +1309,8 @@ differenceWithKey f t1 t2 = mergeWithKey f id (const Tip) t1 t2 -- | /O(n+m)/. Intersection of two maps. -- Return data in the first map for the keys existing in both maps. -- (@'intersection' m1 m2 == 'intersectionWith' 'const' m1 m2@). +-- The implementation uses an efficient /hedge/ algorithm comparable with +-- /hedge-union/. -- -- > intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "a" @@ -1333,7 +1333,8 @@ hedgeInt blo bhi (Bin _ kx x l r) t2 = let l' = hedgeInt blo bmi l (trim blo bmi {-# INLINABLE hedgeInt #-} #endif --- | /O(n+m)/. Intersection with a combining function. +-- | /O(n+m)/. Intersection with a combining function. The implementation uses +-- an efficient /hedge/ algorithm comparable with /hedge-union/. -- -- > intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA" @@ -1344,8 +1345,8 @@ intersectionWith f m1 m2 {-# INLINABLE intersectionWith #-} #endif --- | /O(n+m)/. Intersection with a combining function. --- Intersection is more efficient on (bigset \``intersection`\` smallset). +-- | /O(n+m)/. Intersection with a combining function. The implementation uses +-- an efficient /hedge/ algorithm comparable with /hedge-union/. -- -- > let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar -- > intersectionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "5:a|A" diff --git a/Data/Map/Strict.hs b/Data/Map/Strict.hs index 9ecefcc..faa0478 100644 --- a/Data/Map/Strict.hs +++ b/Data/Map/Strict.hs @@ -713,7 +713,6 @@ unionWith f m1 m2 -- | /O(n+m)/. -- Union with a combining function. The implementation uses the efficient /hedge-union/ algorithm. --- Hedge-union is more efficient on (bigset \``union`\` smallset). -- -- > let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value -- > unionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "5:a|A"), (7, "C")] @@ -767,7 +766,8 @@ differenceWithKey f t1 t2 = mergeWithKey f id (const Tip) t1 t2 Intersection --------------------------------------------------------------------} --- | /O(n+m)/. Intersection with a combining function. +-- | /O(n+m)/. Intersection with a combining function. The implementation uses +-- an efficient /hedge/ algorithm comparable with /hedge-union/. -- -- > intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA" @@ -778,8 +778,8 @@ intersectionWith f m1 m2 {-# INLINABLE intersectionWith #-} #endif --- | /O(n+m)/. Intersection with a combining function. --- Intersection is more efficient on (bigset \``intersection`\` smallset). +-- | /O(n+m)/. Intersection with a combining function. The implementation uses +-- an efficient /hedge/ algorithm comparable with /hedge-union/. -- -- > let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar -- > intersectionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "5:a|A" diff --git a/Data/Set/Base.hs b/Data/Set/Base.hs index 5247261..9790163 100644 --- a/Data/Set/Base.hs +++ b/Data/Set/Base.hs @@ -535,7 +535,6 @@ unions = foldlStrict union empty -- | /O(n+m)/. The union of two sets, preferring the first set when -- equal elements are encountered. -- The implementation uses the efficient /hedge-union/ algorithm. --- Hedge-union is more efficient on (bigset `union` smallset). union :: Ord a => Set a -> Set a -> Set a union Tip t2 = t2 union t1 Tip = t1 @@ -582,8 +581,9 @@ hedgeDiff blo bhi t (Bin _ x l r) = merge (hedgeDiff blo bmi (trim blo bmi t) l) {-------------------------------------------------------------------- Intersection --------------------------------------------------------------------} --- | /O(n+m)/. The intersection of two sets. --- Elements of the result come from the first set, so for example +-- | /O(n+m)/. The intersection of two sets. The implementation uses an +-- efficient /hedge/ algorithm comparable with /hedge-union/. Elements of the +-- result come from the first set, so for example -- -- > import qualified Data.Set as S -- > data AB = A | B deriving Show _______________________________________________ ghc-commits mailing list [email protected] http://www.haskell.org/mailman/listinfo/ghc-commits
