data-store 0.3.0.1 → 0.3.0.3
raw patch · 11 files changed
+210/−326 lines, 11 filesdep ~basedep ~containersdep ~lens
Dependency ranges changed: base, containers, lens, transformers, vector
Files
- benchmarks/src/01.hs +60/−288
- benchmarks/src/Common.hs +49/−2
- benchmarks/src/DS/B01.hs +11/−11
- benchmarks/src/TS/B01.hs +19/−0
- data-store.cabal +23/−15
- src/Data/Map/Extra.hs +4/−0
- src/Data/Store.hs +27/−7
- src/Data/Store/Internal/Function.hs +6/−1
- src/Data/Store/Internal/Type.hs +6/−1
- src/Data/Store/Selection.hs +5/−0
- tests/Test/Data/Store01.hs +0/−1
benchmarks/src/01.hs view
@@ -5,6 +5,9 @@ ( main ) where +#define BENCH_SMALL+#define BENCH_ESSENTIALS+ -------------------------------------------------------------------------------- import Control.DeepSeq (NFData(..)) import Control.Exception.Base (evaluate)@@ -23,9 +26,6 @@ import Common -------------------------------------------------------------------------------- -#define BENCH_SMALL-#define BENCH_ESSENTIALS- data RNF where RNF :: NFData a => a -> RNF @@ -34,278 +34,127 @@ main :: IO () main = C.defaultMainWith C.defaultConfig (liftIO . evaluate $ rnf- [ RNF elems500- , RNF elems10000- , RNF elems20000-#ifndef BENCH_SMALL- , RNF elems100000+ [+ RNF elems100000 , RNF elems200000 , RNF elems400000 , RNF elems800000-#endif , RNF elems5000x5000 , RNF elems10000x5000 - , RNF ds10000- , RNF ds20000-#ifndef BENCH_SMALL , RNF ds100000 , RNF ds200000- --, RNF ds400000- --, RNF ds800000-#endif - , RNF map10000- , RNF map20000-#ifndef BENCH_SMALL , RNF map100000 , RNF map200000- --, RNF map400000- --, RNF map800000-#endif - , RNF is10000- , RNF is20000-#ifndef BENCH_SMALL , RNF is100000 , RNF is200000-#endif- - , RNF ts10000- , RNF ts20000-#ifndef BENCH_SMALL+ , RNF ts100000 , RNF ts200000-#endif , RNF elem9999999 , RNF elem2500 ]) -- Insert 1 element into a store of size N. No collisions.- [ {-- C.bgroup "insert (Int) 01 10000"+ [+ {-+ C.bgroup "insert (Int) 01 100000" [ C.bcompare- [ C.bench "DS" $ C.nf (DS.B01.insert elem9999999) ds10000- , C.bench "DS (Unsafe)" $ C.nf (DS.B01.insertUnsafe elem9999999) ds10000+ [ C.bench "DS" $ C.whnf (DS.B01.insert elem9999999) ds100000+ , C.bench "DS (Unsafe)" $ C.whnf (DS.B01.insertUnsafe elem9999999) ds100000 #ifndef BENCH_DS , C.bench "Map" $ C.whnf (insertMap elem9999999) map10000- , C.bench "IS" $ C.nf (IS.B01.insert elem9999999) is10000- , C.bench "TS" $ C.nf (TS.B01.insert elem9999999) ts10000-#endif- ]- ]- , C.bgroup "insert (Int) 01 20000"- [ C.bcompare- [ C.bench "DS" $ C.nf (DS.B01.insert elem9999999) ds20000- , C.bench "DS (Unsafe)" $ C.nf (DS.B01.insertUnsafe elem9999999) ds20000-#ifndef BENCH_DS- , C.bench "Map" $ C.whnf (insertMap elem9999999) map20000- , C.bench "IS" $ C.nf (IS.B01.insert elem9999999) is20000- , C.bench "TS" $ C.nf (TS.B01.insert elem9999999) ts20000-#endif- ]- ]- , C.bgroup "insert-collision (Int) 01 10000"- [ C.bcompare- [ C.bench "DS" $ C.nf (DS.B01.insert elem2500) ds10000-#ifndef BENCH_DS- , C.bench "Map" $ C.whnf (insertMap elem2500) map10000- , C.bench "IS" $ C.nf (IS.B01.insert elem2500) is10000- , C.bench "TS" $ C.nf (TS.B01.insert elem2500) ts10000-#endif- ]- ]- , C.bgroup "insert-collision (Int) 01 20000"- [ C.bcompare- [ C.bench "DS" $ C.nf (DS.B01.insert elem2500) ds20000-#ifndef BENCH_DS- , C.bench "Map" $ C.whnf (insertMap elem2500) map20000- , C.bench "IS" $ C.nf (IS.B01.insert elem2500) is20000- , C.bench "TS" $ C.nf (TS.B01.insert elem2500) ts20000-#endif- ]- ]- -}- C.bgroup "lookup OO EQ (Int) 01 20000"- [ C.bcompare- [ C.bench "DS" $ C.nf (DS.B01.lookupOOEQ 10000) ds20000- , C.bench "DS (Lens)" $ C.nf (DS.B01.lookupOOEQLens 10000) ds20000-#ifndef BENCH_DS- , C.bench "Map" $ C.nf (Data.Map.lookup 10000) map20000- , C.bench "IS" $ C.nf (IS.B01.lookupOOEQ 10000) is20000- , C.bench "TS" $ C.nf (TS.B01.lookupOOEQ 10000) ts20000-#endif- ]- ]- , C.bgroup "lookup OO GE (Int) 01 20000 (500)"- [ C.bcompare- [ C.bench "DS" $ C.nf (DS.B01.lookupOOGE 19500) ds20000- , C.bench "DS (Lens)" $ C.nf (DS.B01.lookupOOGELens 19500) ds20000- , C.bench "DS (Test)" $ C.nf (insertListDSUnsafe elems500) DS.B01.empty-#ifndef BENCH_DS- , C.bench "IS" $ C.nf (IS.B01.lookupOOGE 19500) is20000- , C.bench "TS" $ C.nf (TS.B01.lookupOOGE 19500) ts20000-#endif- ]- ]- , C.bgroup "lookup OM EQ (Int) 01 20000"- [ C.bcompare- [ C.bench "DS" $ C.nf (DS.B01.lookupOMEQ 200) ds20000- , C.bench "DS (Lens)" $ C.nf (DS.B01.lookupOMEQLens 200) ds20000-#ifndef BENCH_DS- , C.bench "IS" $ C.nf (IS.B01.lookupOMEQ 200) is20000- , C.bench "TS" $ C.nf (TS.B01.lookupOMEQ 200) ts20000-#endif- ]- ]- , C.bgroup "lookup OM GE (Int) 01 20000 (500)"- [ C.bcompare- [ C.bench "DS" $ C.nf (DS.B01.lookupOMGE 3900) ds20000- , C.bench "DS (Lens)" $ C.nf (DS.B01.lookupOMGELens 3900) ds20000-#ifndef BENCH_DS- , C.bench "IS" $ C.nf (IS.B01.lookupOMGE 3900) is20000- , C.bench "TS" $ C.nf (TS.B01.lookupOMGE 3900) ts20000-#endif- ]- ]- , C.bgroup "lookup MM EQ (Int) 01 20000"- [ C.bcompare- [ C.bench "DS" $ C.nf (DS.B01.lookupMMEQ 200) ds20000- , C.bench "DS (Lens)" $ C.nf (DS.B01.lookupMMEQLens 200) ds20000-#ifndef BENCH_DS- , C.bench "IS" $ C.nf (IS.B01.lookupMMEQ 200) is20000- , C.bench "TS" $ C.nf (TS.B01.lookupMMEQ 200) ts20000-#endif- ]- ]-- -- BIG INPUTS- -- Insert 1 element into a store of size N. No collisions.-#ifndef BENCH_SMALL - , C.bgroup "insert (Int) 01 100000"- [ C.bcompare- [ C.bench "DS" $ C.nf (DS.B01.insert elem9999999) ds100000- , C.bench "DS (Unsafe)" $ C.nf (DS.B01.insertUnsafe elem9999999) ds100000-#ifndef BENCH_DS- , C.bench "IS" $ C.nf (IS.B01.insert elem9999999) is100000- , C.bench "Map" $ C.whnf (insertMap elem9999999) map100000- , C.bench "TS" $ C.nf (TS.B01.insert elem9999999) ts100000+ , C.bench "IS" $ C.whnf (IS.B01.force . IS.B01.insert elem9999999) is100000+ , C.bench "TS" $ C.whnf (TS.B01.force . TS.B01.insert elem9999999) ts100000 #endif ] ] , C.bgroup "insert (Int) 01 200000" [ C.bcompare [ C.bench "DS" $ C.nf (DS.B01.insert elem9999999) ds200000- , C.bench "DS (Unsafe)" $ C.whnf (DS.B01.insertUnsafe elem9999999) ds200000+ , C.bench "DS (Unsafe)" $ C.nf (DS.B01.insertUnsafe elem9999999) ds200000 #ifndef BENCH_DS- , C.bench "IS" $ C.nf (IS.B01.insert elem9999999) is200000- , C.bench "Map" $ C.whnf (insertMap elem9999999) map200000- , C.bench "TS" $ C.nf (TS.B01.insert elem9999999) ts200000+ , C.bench "Map" $ C.whnf (insertMap elem9999999) map20000+ , C.bench "IS" $ C.whnf (IS.B01.force . IS.B01.insert elem9999999) is200000+ , C.bench "TS" $ C.whnf (TS.B01.force . TS.B01.insert elem9999999) ts200000 #endif ] ] , C.bgroup "insert-collision (Int) 01 100000" [ C.bcompare- [ C.bench "DS" $ C.nf (DS.B01.insert elem2500) ds100000+ [ C.bench "DS" $ C.whnf (DS.B01.insert elem2500) ds100000 #ifndef BENCH_DS- , C.bench "IS" $ C.whnf (IS.B01.insert elem2500) is100000- , C.bench "Map" $ C.nf (insertMap elem2500) map100000- , C.bench "TS" $ C.nf (TS.B01.insert elem2500) ts100000+ , C.bench "Map" $ C.whnf (insertMap elem2500) map100000+ , C.bench "IS" $ C.whnf (IS.B01.force . IS.B01.insert elem2500) is100000+ , C.bench "TS" $ C.whnf (TS.B01.force . TS.B01.insert elem2500) ts100000 #endif ] ] , C.bgroup "insert-collision (Int) 01 200000" [ C.bcompare- [ C.bench "DS" $ C.nf (DS.B01.insert elem2500) ds200000+ [ C.bench "DS" $ C.whnf (DS.B01.insert elem2500) ds200000 #ifndef BENCH_DS- , C.bench "IS" $ C.nf (IS.B01.insert elem2500) is200000- , C.bench "Map" $ C.nf (insertMap elem2500) map200000- , C.bench "TS" $ C.nf (TS.B01.insert elem2500) ts200000+ , C.bench "Map" $ C.whnf (insertMap elem2500) map200000+ , C.bench "IS" $ C.whnf (IS.B01.force . IS.B01.insert elem2500) is200000+ , C.bench "TS" $ C.whnf (TS.B01.force . TS.B01.insert elem2500) ts200000 #endif ] ]- , C.bgroup "lookup OO EQ (Int) 01 200000"+ -}+ C.bgroup "lookup OO EQ (Int) 01 200000" [ C.bcompare- [ C.bench "DS" $ C.nf (DS.B01.lookupOOEQ 2500) ds200000- , C.bench "DS (Lens)" $ C.nf (DS.B01.lookupOOEQLens 2500) ds200000+ [ C.bench "DS" $ C.whnf (forceList . DS.B01.lookupOOEQ 10000) ds200000+ , C.bench "DS (Lens)" $ C.whnf (forceList . DS.B01.lookupOOEQLens 10000) ds200000 #ifndef BENCH_DS- , C.bench "IS" $ C.nf (IS.B01.lookupOOEQ 2500) is200000- , C.bench "Map" $ C.whnf (Data.Map.lookup 2500) map200000- , C.bench "TS" $ C.nf (TS.B01.lookupOOEQ 2500) ts200000+ , C.bench "Map" $ C.nf (Data.Map.lookup 10000) map200000+ , C.bench "IS" $ C.whnf (forceList . IS.B01.lookupOOEQ 10000) is200000+ , C.bench "TS" $ C.whnf (forceList . TS.B01.lookupOOEQ 10000) ts200000 #endif ] ] , C.bgroup "lookup OO GE (Int) 01 200000 (500)" [ C.bcompare- [ C.bench "DS" $ C.nf (DS.B01.lookupOOGE 199000) ds200000- , C.bench "DS (Lens)" $ C.nf (DS.B01.lookupOOGELens 199000) ds200000+ [ C.bench "DS" $ C.whnf (forceList . DS.B01.lookupOOGE 199500) ds200000+ , C.bench "DS (Lens)" $ C.whnf (forceList . DS.B01.lookupOOGELens 199500) ds200000 #ifndef BENCH_DS- , C.bench "IS" $ C.nf (IS.B01.lookupOOGE 199000) is200000- , C.bench "TS" $ C.nf (TS.B01.lookupOOGE 199500) ts200000+ , C.bench "IS" $ C.whnf (forceList . IS.B01.lookupOOGE 199500) is200000+ , C.bench "TS" $ C.whnf (forceList . TS.B01.lookupOOGE 199500) ts200000 #endif ] ] , C.bgroup "lookup OM EQ (Int) 01 200000" [ C.bcompare- [ C.bench "DS" $ C.nf (DS.B01.lookupOMEQ 200) ds200000- , C.bench "DS (Lens)" $ C.nf (DS.B01.lookupOMEQLens 200) ds200000+ [ C.bench "DS" $ C.whnf (forceList . DS.B01.lookupOMEQ 200) ds200000+ , C.bench "DS (Lens)" $ C.whnf (forceList . DS.B01.lookupOMEQLens 200) ds200000 #ifndef BENCH_DS- , C.bench "IS" $ C.nf (IS.B01.lookupOMEQ 200) is200000- , C.bench "TS" $ C.nf (TS.B01.lookupOMEQ 200) ts200000+ , C.bench "IS" $ C.whnf (forceList . IS.B01.lookupOMEQ 200) is200000+ , C.bench "TS" $ C.whnf (forceList . TS.B01.lookupOMEQ 200) ts200000 #endif ] ] , C.bgroup "lookup OM GE (Int) 01 200000 (500)" [ C.bcompare- [ C.bench "DS" $ C.nf (DS.B01.lookupOMGE 39900) ds200000- , C.bench "DS (Lens)" $ C.nf (DS.B01.lookupOMGELens 39900) ds200000+ [ C.bench "DS" $ C.whnf (forceList . DS.B01.lookupOMGE 39900) ds200000+ , C.bench "DS (Lens)" $ C.whnf (forceList . DS.B01.lookupOMGELens 39900) ds200000 #ifndef BENCH_DS- , C.bench "IS" $ C.nf (IS.B01.lookupOMGE 39900) is200000- , C.bench "TS" $ C.nf (TS.B01.lookupOMGE 39900) ts200000+ , C.bench "IS" $ C.whnf (forceList . IS.B01.lookupOMGE 39900) is200000+ , C.bench "TS" $ C.whnf (forceList . TS.B01.lookupOMGE 39900) ts200000 #endif ] ] , C.bgroup "lookup MM EQ (Int) 01 200000" [ C.bcompare- [ C.bench "DS" $ C.nf (DS.B01.lookupMMEQ 200) ds200000- , C.bench "DS (Lens)" $ C.nf (DS.B01.lookupMMEQLens 200) ds200000-#ifndef BENCH_DS- , C.bench "IS" $ C.nf (IS.B01.lookupMMEQ 200) is200000- , C.bench "TS" $ C.nf (TS.B01.lookupMMEQ 200) ts200000-#endif- ]- ]--- BENCH_SMALL-#endif--{--#ifndef BENCH_ESSENTIALS- -- Insert N elements into an empty store (the inserts are accumulative). No collisions.- , C.bgroup "insert-accum (Int) 01 10000"- [ C.bcompare- [ C.bench "DS" $ C.nf (insertListDS elems10000) DS.B01.empty- , C.bench "DS (Unsafe)" $ C.nf (insertListDSUnsafe elems10000) DS.B01.empty+ [ C.bench "DS" $ C.whnf (forceList . DS.B01.lookupMMEQ 200) ds200000+ , C.bench "DS (Lens)" $ C.whnf (forceList . DS.B01.lookupMMEQLens 200) ds200000 #ifndef BENCH_DS- , C.bench "TS" $ C.nf (insertListTS elems10000) TS.B01.empty-#endif- ]- ]- - -- Insert N elements into store of the same N elements (the inserts are- -- accumulative, thus we basically "overwrite" the shole store).- -- Collisions (obviously).- , C.bgroup "insert-accum-collisions (Int) 01 10000"- [ C.bcompare- [ C.bench "DS" $ C.nf (insertListDS elems10000) ds10000-#ifndef BENCH_DS - , C.bench "TS" $ C.nf (insertListTS elems10000) ts10000+ , C.bench "IS" $ C.whnf (forceList . IS.B01.lookupMMEQ 200) is200000+ , C.bench "TS" $ C.whnf (forceList . TS.B01.lookupMMEQ 200) ts200000 #endif ] ]--- ESSENTIALS-#endif--} ] @@ -314,14 +163,21 @@ insertListDS :: [C01] -> DS.B01.DS -> DS.B01.DS insertListDS xs s0 = foldl' (flip DS.B01.insert) s0 xs -insertListDSUnsafe :: [C01] -> DS.B01.DS -> DS.B01.DS-insertListDSUnsafe xs s0 = foldl' (flip DS.B01.insertUnsafe) s0 xs- insertListTS :: [C01] -> TS.B01.TS -> TS.B01.TS-insertListTS xs s0 = foldl' (flip TS.B01.insert) s0 xs+insertListTS xs s0 = snd $!+ foldl' (\(n, acc) x -> if n == t+ then rnf acc `seq` (0, TS.B01.insert x acc)+ else (n + 1, TS.B01.insert x acc)+ ) (0 :: Int, s0) xs+ where t = 10000 insertListIS :: [C01] -> IS.B01.IS -> IS.B01.IS-insertListIS xs s0 = foldl' (\s x -> IS.B01.insert x $! s) s0 xs+insertListIS xs s0 = snd $! + foldl' (\(n, acc) x -> if n == t+ then rnf acc `seq` (0, IS.B01.insert x acc)+ else (n + 1, IS.B01.insert x acc)+ ) (0 :: Int, s0) xs+ where t = 10000 insertListMap :: [C01] -> Data.Map.Map Int C01 -> Data.Map.Map Int C01 insertListMap xs s0 = foldl' (flip insertMap) s0 xs@@ -331,117 +187,33 @@ -- MAP -map10000 :: Data.Map.Map Int C01-map10000 = insertListMap elems10000 Data.Map.empty--map20000 :: Data.Map.Map Int C01-map20000 = insertListMap elems20000 Data.Map.empty--#ifndef BENCH_SMALL map100000 :: Data.Map.Map Int C01 map100000 = insertListMap elems100000 Data.Map.empty map200000 :: Data.Map.Map Int C01 map200000 = insertListMap elems200000 Data.Map.empty -map800000 :: Data.Map.Map Int C01-map800000 = insertListMap elems800000 Data.Map.empty-#endif- -- IS -is10000 :: IS.B01.IS-is10000 = insertListIS elems10000 IS.B01.empty--is20000 :: IS.B01.IS-is20000 = insertListIS elems20000 IS.B01.empty--#ifndef BENCH_SMALL is100000 :: IS.B01.IS is100000 = insertListIS elems100000 IS.B01.empty is200000 :: IS.B01.IS is200000 = insertListIS elems200000 IS.B01.empty-#endif -- DS -ds10000 :: DS.B01.DS-ds10000 = insertListDS elems10000 DS.B01.empty--ds20000 :: DS.B01.DS-ds20000 = insertListDS elems20000 DS.B01.empty--#ifndef BENCH_SMALL ds100000 :: DS.B01.DS ds100000 = insertListDS elems100000 DS.B01.empty ds200000 :: DS.B01.DS ds200000 = insertListDS elems200000 DS.B01.empty -ds400000 :: DS.B01.DS-ds400000 = insertListDS elems400000 DS.B01.empty--ds800000 :: DS.B01.DS-ds800000 = insertListDS elems800000 DS.B01.empty-#endif- -- TS -ts10000 :: TS.B01.TS-ts10000 = insertListTS elems10000 TS.B01.empty--ts20000 :: TS.B01.TS-ts20000 = insertListTS elems20000 TS.B01.empty--#ifndef BENCH_SMALL ts100000 :: TS.B01.TS ts100000 = insertListTS elems100000 TS.B01.empty ts200000 :: TS.B01.TS ts200000 = insertListTS elems200000 TS.B01.empty-#endif---- ELEM--elem9999999 :: C01-elem9999999 = head $! generate 9999999 1 --elem2500 :: C01-elem2500 = head $! generate 2500 1 --elems5000x5000 :: [C01]-elems5000x5000 = generate 5000 5000--elems10000x5000 :: [C01]-elems10000x5000 = generate 10000 5000--elems500 :: [C01]-elems500 = generate 19500 500--elems10000 :: [C01]-elems10000 = generate 0 10000--elems20000 :: [C01]-elems20000 = generate 0 20000--#ifndef BENCH_SMALL-elems100000 :: [C01]-elems100000 = generate 0 100000--elems200000 :: [C01]-elems200000 = generate 0 200000--elems400000 :: [C01]-elems400000 = generate 0 400000--elems800000 :: [C01]-elems800000 = generate 0 800000-#endif--generate :: Int -> Int -> [C01]-generate o n = map (\x -> C01 x (x `div` s) [x .. x + s]) [o .. (n + o) - 1]- where- s = 5-
benchmarks/src/Common.hs view
@@ -4,11 +4,13 @@ {-# LANGUAGE GADTs #-} {-# LANGUAGE TypeOperators #-} {-# LANGUAGE DeriveDataTypeable #-}+{-# LANGUAGE CPP #-} {-# OPTIONS_GHC -fno-warn-orphans #-} +#define BENCH_ESSENTIALS+ module Common-( C01(..)-) where+where -------------------------------------------------------------------------------- import Control.DeepSeq (NFData(..))@@ -23,4 +25,49 @@ instance NFData C01 where rnf (C01 x y z) = rnf x `seq` rnf y `seq` rnf z++elem9999999 :: C01+elem9999999 = head $! generate 9999999 1 ++elem2500 :: C01+elem2500 = head $! generate 2500 1 ++elems5000x5000 :: [C01]+elems5000x5000 = generate 5000 5000++elems10000x5000 :: [C01]+elems10000x5000 = generate 10000 5000++#ifdef BENCH_SMALL+elems10000 :: [C01]+elems10000 = generate 0 10000++elems20000 :: [C01]+elems20000 = generate 0 20000++#else+elems100000 :: [C01]+elems100000 = generate 0 100000++elems200000 :: [C01]+elems200000 = generate 0 200000++elems400000 :: [C01]+elems400000 = generate 0 400000++elems800000 :: [C01]+elems800000 = generate 0 800000+#endif++generate :: Int -> Int -> [C01]+generate o n = map (\x -> C01 x (x `div` s) [x .. x + s]) [o .. (n + o) - 1]+ where+ s = 5++forceList :: [a] -> ()+forceList ll = seq (go ll) ()+ where+ go [] = ()+ go (_:xs) = go xs+
benchmarks/src/DS/B01.hs view
@@ -9,7 +9,7 @@ import Common (C01(..)) -------------------------------------------------------------------------------- import qualified Data.Store as S-import Data.Store (M, O, (.:), (.:.), (:.)(..), (.<), (.<=), (.>), (.>=), (./=), (.==), (.&&), (.||))+import Data.Store (M, O, (.:), (.:.), (:.)(..), (.>=), (.==)) import Data.Store.Lens -------------------------------------------------------------------------------- @@ -52,32 +52,32 @@ lookupOOEQ :: Int -> DS -> [(S.RawKey DSKRS DSTS, C01)] lookupOOEQ x = S.lookup (sD1 .== x) -lookupOOEQLens :: Int -> DS -> DS-lookupOOEQLens x o = o ^. with (sD1 .== x) +lookupOOEQLens :: Int -> DS -> [C01]+lookupOOEQLens x o = S.elements (o ^. with (sD1 .== x)) lookupOOGE :: Int -> DS -> [(S.RawKey DSKRS DSTS, C01)] lookupOOGE x = S.lookup (sD1 .>= x) -lookupOOGELens :: Int -> DS -> DS-lookupOOGELens x o = o ^. with (sD1 .>= x)+lookupOOGELens :: Int -> DS -> [C01]+lookupOOGELens x o = S.elements (o ^. with (sD1 .>= x)) lookupOMEQ :: Int -> DS -> [(S.RawKey DSKRS DSTS, C01)] lookupOMEQ x = S.lookup (sD2 .== x) -lookupOMEQLens :: Int -> DS -> DS-lookupOMEQLens x o = o ^. with (sD2 .== x)+lookupOMEQLens :: Int -> DS -> [C01]+lookupOMEQLens x o = S.elements (o ^. with (sD2 .== x)) lookupOMGE :: Int -> DS -> [(S.RawKey DSKRS DSTS, C01)] lookupOMGE x = S.lookup (sD2 .>= x) -lookupOMGELens :: Int -> DS -> DS-lookupOMGELens x o = o ^. with (sD2 .>= x)+lookupOMGELens :: Int -> DS -> [C01]+lookupOMGELens x o = S.elements (o ^. with (sD2 .>= x)) lookupMMEQ :: Int -> DS -> [(S.RawKey DSKRS DSTS, C01)] lookupMMEQ x = S.lookup (sD3 .== x) -lookupMMEQLens :: Int -> DS -> DS -lookupMMEQLens x o = o ^. with (sD3 .== x)+lookupMMEQLens :: Int -> DS -> [C01] +lookupMMEQLens x o = S.elements (o ^. with (sD3 .== x)) empty :: DS empty = S.empty
benchmarks/src/TS/B01.hs view
@@ -2,6 +2,7 @@ {-# LANGUAGE TypeFamilies #-} {-# LANGUAGE DeriveDataTypeable #-} {-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE ScopedTypeVariables #-} {-# OPTIONS_GHC -fno-warn-orphans #-} module TS.B01@@ -14,6 +15,7 @@ -------------------------------------------------------------------------------- import qualified Data.IntSet import Data.Foldable (toList)+import Data.Functor.Identity -------------------------------------------------------------------------------- import Common (C01(..)) --------------------------------------------------------------------------------@@ -81,4 +83,21 @@ empty :: TS empty = T.empty++force :: TS -> ()+force T.EmptyTable = ()+force (T.Table tab) = seq go ()+ where+ go :: T.Tab C01 (T.AnIndex C01)+ go = runIdentity $! T.forTab tab (\_ i -> Identity $! case i of+ T.PrimaryMap m -> m `seq` T.PrimaryMap m+ T.CandidateMap m -> m `seq` T.CandidateMap m+ T.CandidateIntMap m -> m `seq` T.CandidateIntMap m+ T.CandidateHashMap m -> m `seq` T.CandidateHashMap m+ T.SupplementalMap m -> m `seq` T.SupplementalMap m+ T.SupplementalIntMap m -> m `seq` T.SupplementalIntMap m+ T.SupplementalHashMap m -> m `seq` T.SupplementalHashMap m+ T.InvertedMap m -> m `seq` T.InvertedMap m+ T.InvertedIntMap m -> m `seq` T.InvertedIntMap m+ T.InvertedHashMap m -> m `seq` T.InvertedHashMap m)
data-store.cabal view
@@ -1,5 +1,5 @@ name: data-store-version: 0.3.0.1+version: 0.3.0.3 synopsis: Type safe, in-memory dictionary with multidimensional keys. description: Type safe, in-memory dictionary with multidimensional keys.@@ -12,7 +12,7 @@ license-file: LICENSE author: Petr Pilař-maintainer: maintainer+the.palmik@gmail.com+maintainer: the.palmik+maintainer@gmail.com category: Data @@ -40,8 +40,8 @@ , Data.IntSet.Extra build-depends:- base >= 4.6 && < 5- , containers >= 0.4 && < 1+ base >= 4.5 && < 5+ , containers == 0.4 && < 1 , lens >= 3.9 && < 4 , transformers >= 0.2 && < 0.4 , vector >= 0.10 && < 0.11@@ -63,13 +63,16 @@ , Data.Store.Lens build-depends:- base >= 4.5- , vector >= 0.10- , containers >= 0.4- , lens >= 3.9- , transformers >= 0.2- , tagged >= 0.4+ base >= 4.5 && < 5+ , containers >= 0.4 && < 1+ , lens >= 3.9 && < 4+ , transformers >= 0.2 && < 0.4+ , vector >= 0.10 && < 0.11 + , cereal >= 0.3.5 && < 0.4+ , deepseq >= 1.3.0 && < 1.4+ , safecopy >= 0.8 && < 0.9+ , test-framework >= 0.8 , test-framework-quickcheck2 >= 0.3 , QuickCheck >= 2.4 && < 2.6@@ -86,11 +89,16 @@ build-depends:- base >= 4.5- , vector >= 0.9- , containers >= 0.4- , lens >= 3.9- , transformers >= 0.2+ base >= 4.6 && < 5+ , containers >= 0.5 && < 1+ , lens >= 3.9 && < 4+ , transformers >= 0.2 && < 0.4+ , vector >= 0.10 && < 0.11++ , cereal >= 0.3.5 && < 0.4+ , deepseq >= 1.3.0 && < 1.4+ , safecopy >= 0.8 && < 0.9+ , unordered-containers >= 0.2 , tagged >= 0.4 , mtl >= 2.1
src/Data/Map/Extra.hs view
@@ -5,7 +5,11 @@ ) where --------------------------------------------------------------------------------+#if MIN_VERSION_containers(0,5,0) import qualified Data.Map.Strict as Data.Map+#else+import qualified Data.Map+#endif -------------------------------------------------------------------------------- -- | The expression (@insertUnique k v old@)
src/Data/Store.hs view
@@ -102,19 +102,19 @@ -- * /d/ -- the (constant) number of dimensions of the store. -- -- * /k/ -- the (variable) number of key dimensions values of a key (or --- maximum of key dimension values over all keys in case of for example --- @'Data.Store.update'@). +-- maximum of the number of key dimension values over all keys in case of for example +-- @'Data.Store.updateWithKey'@). -- -- * /s/ -- the (variable) size of the output of the operation or the -- (variable) number of elements affected by the operation. This is --- of then the number of key-element pairs that correspond to a selection. +-- often the number of key-element pairs that correspond to some selection. -- -- * /s(sel)/ -- the (variable) number of key-element pairs that correspond --- to a selection /sel/ if /sel/ would otherwise be ambigious. +-- to a selection /sel/ if /s/ would otherwise be ambigious. -- -- * /c/ -- the (variable) complexity of selection. -- --- * /c/ -- the (variable) complexity of selection /sel/ if /sel/ +-- * /c(sel)/ -- the (variable) complexity of resolving the selection /sel/ if /c/ -- would otherwise be ambiguous. module Data.Store ( @@ -230,7 +230,11 @@ import Data.Monoid import Data.Maybe import Data.Functor.Identity +#if MIN_VERSION_containers(0,5,0) import qualified Data.IntMap.Strict as Data.IntMap +#else +import qualified Data.IntMap +#endif import qualified Data.List import qualified Data.Foldable -------------------------------------------------------------------------------- @@ -359,10 +363,14 @@ -- >>> insert (contentKey content) content store -- > Just (1 :. "name" :. "body" :. ["t1", "t2"] :. 0.5, <updated_store>) -- +-- Complexity: /O(min(n, W) + k * (log n + min(n, W)))/ +-- -- See also: -- -- * 'Data.Store.insert'' +-- -- * 'Data.Store.Internal.Type.Key' +-- -- * 'Data.Store.Internal.Type.RawKey' insert :: I.Key krs ts -> v @@ -378,10 +386,14 @@ -- the same key-element pairs as @old@ plus @(k, e)@. -- Any key-value pairs from @old@ colliding with @(k, e)@ are not included in @new@. -- +-- Complexity: /O(min(n, W) + k * (log n + min(n, W)))/ +-- -- See also: -- -- * 'Data.Store.insert' +-- -- * 'Data.Store.Internal.Type.Key' +-- -- * 'Data.Store.Internal.Type.RawKey' insert' :: I.Key krs ts -> e @@ -403,8 +415,11 @@ -- See also: -- -- * 'Data.Store.insert' +-- -- * 'Data.Store.insert'' +-- -- * 'Data.Store.Internal.Type.Key' +-- -- * 'Data.Store.Internal.Type.RawKey' unsafeInsert :: I.Key krs ts -> e @@ -450,13 +465,15 @@ -- selection @sel@, those are updated as follows: -- -- * If @(tr k e)@ is @Nothing@ the pair is not included in @new@. +-- -- * If @(tr k e)@ is (@Just (e', Nothing)@) the pair is replaced by pair @(k, e')@. +-- -- * If @(tr k e)@ is (@Just (e', Just k')@) the pair is replaced by pair @(k', e')@. -- -- If any of the updated key-element pairs would cause a collision, the -- result is @Nothing@. -- --- Complexity: /O(c + s * (min(n, W) + q * log n))/ +-- Complexity: /O(c + s * (min(n, W) + k * (log n + min(n, W))))/ -- -- See also: -- @@ -475,13 +492,15 @@ -- selection @sel@, those are updated as follows: -- -- * If @(tr k e)@ is @Nothing@ the pair is not included in @new@. +-- -- * If @(tr k e)@ is (@Just (e', Nothing)@) the pair is replaced by pair @(k, e')@. +-- -- * If @(tr k e)@ is (@Just (e', Just k')@) the pair is replaced by pair @(k', e')@. -- -- Any pairs of the original store @old@ that would, after the update, cause collisons -- are not included in @new@. -- --- Complexity: /O(c + d * s * (min(n, W) + q * log n))/ +-- Complexity: /O(c + s * d * (min(n, W) + k * (log n + min(n, W))))/ -- -- See also: -- @@ -642,6 +661,7 @@ -- See also: -- -- * 'Data.Store.fromList' +-- -- * 'Data.Store.fromList' unsafeFromList :: I.Empty (I.Index irs ts) => [(I.Key krs ts, v)] -> I.Store tag krs irs ts v unsafeFromList = Data.Foldable.foldl (\s (k, v) -> snd $ unsafeInsert k v s) I.empty
src/Data/Store/Internal/Function.hs view
@@ -12,8 +12,13 @@ import Data.Monoid ((<>)) import Data.Functor.Identity import qualified Data.List+#if MIN_VERSION_containers(0,5,0) import qualified Data.IntMap.Strict as Data.IntMap+import qualified Data.Map.Strict as Data.Map+#else+import qualified Data.IntMap import qualified Data.Map+#endif import qualified Data.IntSet import qualified Data.IntSet.Extra --------------------------------------------------------------------------------@@ -30,7 +35,7 @@ genericSubset ids (I.Store vs _ _) = Data.IntSet.foldr (\i acc -> case Data.IntMap.lookup i vs of- Just (ik, e) -> runIdentity $! genericInsert indexInsertID'' ik e acc+ Just (ik, e) -> runIdentity $ genericInsert indexInsertID'' ik e acc _ -> acc ) I.empty ids {-# INLINE genericSubset #-}
src/Data/Store/Internal/Type.hs view
@@ -24,9 +24,14 @@ import Data.Data (Typeable, Typeable2) import qualified Data.Data import qualified Data.List-import qualified Data.Map.Strict as Data.Map import Data.Monoid ((<>))+#if MIN_VERSION_containers(0,5,0) import qualified Data.IntMap.Strict as Data.IntMap+import qualified Data.Map.Strict as Data.Map+#else+import qualified Data.IntMap+import qualified Data.Map+#endif import qualified Data.IntSet import qualified Data.Foldable as F
src/Data/Store/Selection.hs view
@@ -30,8 +30,13 @@ import Data.Monoid ((<>)) import qualified Data.IntSet import qualified Data.List+#if MIN_VERSION_containers(0,5,0) import qualified Data.IntMap.Strict as Data.IntMap import qualified Data.Map.Strict as Data.Map+#else+import qualified Data.IntMap+import qualified Data.Map+#endif -------------------------------------------------------------------------------- import qualified Data.Store.Internal.Type as I --------------------------------------------------------------------------------
tests/Test/Data/Store01.hs view
@@ -14,7 +14,6 @@ -------------------------------------------------------------------------------- import qualified Data.List as L import Data.Maybe-import Data.Proxy import qualified Data.Foldable import qualified Data.Set import qualified Data.IntSet