data-sketches 0.1.0.2 → 0.2.0.0

raw patch · 4 files changed

+104/−62 lines, 4 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• data-sketches.cabal +1/−1
• src/DataSketches/Quantiles/RelativeErrorQuantile.hs +82/−40
• test/ProofCheckSpec.hs +2/−2
• test/RelativeErrorQuantileSpec.hs +19/−19

@@ -5,7 +5,7 @@ -- see: https://github.com/sol/hpack  name:           data-sketches-version:        0.1.0.2+version:        0.2.0.0 description:    Please see the README on GitHub at <https://github.com/iand675/datasketches-haskell#readme> homepage:       https://github.com/iand675/datasketches-haskell#readme bug-reports:    https://github.com/iand675/datasketches-haskell/issues

@@ -24,22 +24,23 @@ {-# LANGUAGE ConstraintKinds #-} {-# LANGUAGE TypeApplications #-} {-# LANGUAGE DeriveGeneric #-}-module DataSketches.Quantiles.RelativeErrorQuantile-  ( ReqSketch (..)+module DataSketches.Quantiles.RelativeErrorQuantile ( +  -- * Construction+    ReqSketch (criterion)    , ValidK   , mkReqSketch-  , getN-  , getSum-  , getCompactors-  , getNumLevels-  , getRetainedItems-  , computeTotalRetainedItems-  , cumulativeDistributionFunction+  -- ** Configuration settings   , RankAccuracy(..)-  , rankAccuracy-  , relativeStandardError-  , maximum+  , Criterion(..)+  -- * Sketch summaries   , count+  , null+  , sum+  , maximum+  , minimum+  , retainedItemCount+  , relativeStandardError+  , countWithCriterion   , probabilityMassFunction   , quantile   , quantiles@@ -47,14 +48,18 @@   , rankLowerBound   , ranks   , rankUpperBound-  , null+  , cumulativeDistributionFunction+  -- * Updating the sketch+  , merge+  , insert+  , rankAccuracy   , isEstimationMode   , isLessThanOrEqual-  , merge-  , update+  -- * Internals used in test. DO NOT USE.+  -- | If you see this error, please file an issue in the GitHub repository.   , CumulativeDistributionInvariants(..)-  -- Test only?   , mkAuxiliaryFromReqSketch+  , computeTotalRetainedItems   ) where  import Control.DeepSeq@@ -76,7 +81,6 @@ import qualified DataSketches.Quantiles.RelativeErrorQuantile.Internal.DoubleBuffer as DoubleBuffer import DataSketches.Quantiles.RelativeErrorQuantile.Internal.URef import GHC.TypeLits-import Prelude hiding (null, minimum, maximum) import Data.Maybe (isNothing) import qualified Data.Foldable import qualified Data.List@@ -85,7 +89,41 @@ import GHC.Generics import System.Random.MWC (Gen, create) import qualified Data.Vector.Generic.Mutable as MG+import Prelude hiding (sum, minimum, maximum, null)+{- |+This Relative Error Quantiles Sketch is the Haskell implementation based on the paper+"Relative Error Streaming Quantiles", https://arxiv.org/abs/2004.01668, and loosely derived from+a Python prototype written by Pavel Vesely, ported from the Java equivalent. +This implementation differs from the algorithm described in the paper in the following:++The algorithm requires no upper bound on the stream length.+Instead, each relative-compactor counts the number of compaction operations performed+so far (via variable state). Initially, the relative-compactor starts with INIT_NUMBER_OF_SECTIONS.+Each time the number of compactions (variable state) exceeds 2^{numSections - 1}, we double+numSections. Note that after merging the sketch with another one variable state may not correspond+to the number of compactions performed at a particular level, however, since the state variable+never exceeds the number of compactions, the guarantees of the sketch remain valid.++The size of each section (variable k and sectionSize in the code and parameter k in+the paper) is initialized with a value set by the user via variable k.+When the number of sections doubles, we decrease sectionSize by a factor of sqrt(2).+This is applied at each level separately. Thus, when we double the number of sections, the+nominal compactor size increases by a factor of approx. sqrt(2) (+/- rounding).++The merge operation here does not perform "special compactions", which are used in the paper+to allow for a tight mathematical analysis of the sketch.++This implementation provides a number of capabilities not discussed in the paper or provided+in the Python prototype.++The Python prototype only implemented high accuracy for low ranks. This implementation+provides the user with the ability to choose either high rank accuracy or low rank accuracy at+the time of sketch construction.++- The Python prototype only implemented a comparison criterion of "<". This implementation+allows the user to switch back and forth between the "<=" criterion and the "<=" criterion.+-} data ReqSketch (k :: Nat) s = ReqSketch   { rankAccuracySetting :: !RankAccuracy   , criterion :: !Criterion@@ -125,6 +163,8 @@  deriving instance Show (Snapshot (ReqSketch k)) +-- | The K parameter can be increased to trade increased space efficiency for higher accuracy in rank and quantile+-- calculations. Due to the way the compaction algorithm works, it must be an even number between 4 and 1024. type ValidK k = (4 <= k, k <= 1024, (k `Mod` 2) ~ 0)  mkReqSketch :: forall k m. (PrimMonad m, ValidK k, KnownNat k) => RankAccuracy -> m (ReqSketch k (PrimState m))@@ -144,8 +184,8 @@  mkAuxiliaryFromReqSketch :: PrimMonad m => ReqSketch k (PrimState m) -> m ReqAuxiliary mkAuxiliaryFromReqSketch this = do-  total <- getN this-  retainedItems <- getRetainedItems this+  total <- count this+  retainedItems <- retainedItemCount this   compactors <- getCompactors this   Auxiliary.mkAuxiliary (rankAccuracySetting this) total retainedItems compactors @@ -161,14 +201,11 @@ getIsEmpty :: PrimMonad m => ReqSketch k (PrimState m) -> m Bool getIsEmpty = fmap (== 0) . readURef . totalN -getN :: PrimMonad m => ReqSketch k (PrimState m) -> m Word64-getN = readURef . totalN- getK :: forall k s. KnownNat k => ReqSketch k s -> Word32 getK _ = fromIntegral (natVal (Proxy :: Proxy k)) -getRetainedItems :: PrimMonad m => ReqSketch k (PrimState m) -> m Int-getRetainedItems = readURef . retainedItems+retainedItemCount :: PrimMonad m => ReqSketch k (PrimState m) -> m Int+retainedItemCount = readURef . retainedItems  getMaxNominalCapacity :: PrimMonad m => ReqSketch k (PrimState m) -> m Int getMaxNominalCapacity = readURef . maxNominalCapacitiesSize@@ -215,7 +252,7 @@   let numSplits = length splits       numBuckets = numSplits -- + 1   splitCounts <- getCounts this splits-  n <- getN this+  n <- count this   pure $ (++ [n]) $ take numBuckets splitCounts  -- | Returns an approximation to the Cumulative Distribution Function (CDF), which is the cumulative analog of the PMF, @@ -240,7 +277,7 @@     then pure Nothing     else do       let numBuckets = length splitPoints + 1-      n <- getN this+      n <- count this       pure $ Just $ (/ fromIntegral n) . fromIntegral <$> buckets  rankAccuracy :: ReqSketch s k -> RankAccuracy@@ -268,8 +305,13 @@ maximum :: PrimMonad m => ReqSketch k (PrimState m) -> m Double maximum = readURef . maxValue -count :: (PrimMonad m, s ~ PrimState m, KnownNat k) => ReqSketch k s -> Double -> m Word64-count s value = fromIntegral <$> do+-- | Get the total number of items inserted into the sketch+count :: PrimMonad m => ReqSketch k (PrimState m) -> m Word64+count = readURef . totalN++-- | Returns the approximate count of items satisfying the criterion set in the ReqSketch 'criterion' field.+countWithCriterion :: (PrimMonad m, s ~ PrimState m, KnownNat k) => ReqSketch k s -> Double -> m Word64+countWithCriterion s value = fromIntegral <$> do   empty <- null s   if empty     then pure 0@@ -282,8 +324,8 @@             pure (accum + (fromIntegral count_ * wt))       Vector.foldM go 0 compactors -getSum :: (PrimMonad m) => ReqSketch k (PrimState m) -> m Double-getSum = readURef . sumValue+sum :: (PrimMonad m) => ReqSketch k (PrimState m) -> m Double+sum = readURef . sumValue  -- | Returns an approximation to the Probability Mass Function (PMF) of the input stream given a set of splitPoints (values). -- The resulting approximations have a probabilistic guarantee that be obtained, a priori, from the getRSE(int, double, boolean, long) function.@@ -311,7 +353,7 @@      else do        let numBuckets = length splitPoints + 1        buckets <- fmap fromIntegral <$> getPMForCDF this splitPoints-       total <- fromIntegral <$> getN this+       total <- fromIntegral <$> count this        let computeProb (0, bucket) = bucket / total            computeProb (i, bucket) = (prevBucket + bucket) / total              where prevBucket = buckets !! i - 1@@ -335,8 +377,8 @@          error $ "Normalized rank must be in the range [0.0, 1.0]: " ++ show normRank        currAuxiliary <- getAux this        when (isNothing currAuxiliary) $ do-         total <- getN this-         retainedItems <- getRetainedItems this+         total <- count this+         retainedItems <- retainedItemCount this          compactors <- getCompactors this          newAuxiliary <- Auxiliary.mkAuxiliary (rankAccuracySetting this) total retainedItems compactors          writeMutVar (aux this) (Just newAuxiliary)@@ -371,7 +413,7 @@   if isEmpty     then pure (0 / 0) -- NaN     else do-      nnCount <- count s value+      nnCount <- countWithCriterion s value       total <- readURef $ totalN s       pure (fromIntegral nnCount / fromIntegral total) @@ -391,7 +433,7 @@ rankLowerBound this rank numStdDev = do   numLevels <- getNumLevels this   let k = fromIntegral $ getK this-  total <- getN this+  total <- count this   pure $ getRankLB k numLevels rank numStdDev (rankAccuracySetting this == HighRanksAreAccurate) total  -- | Gets an array of normalized ranks that correspond to the given array of values.@@ -412,7 +454,7 @@ rankUpperBound this rank numStdDev= do   numLevels <- getNumLevels this   let k = fromIntegral $ getK this-  total <- getN this+  total <- count this   pure $ getRankUB k numLevels rank numStdDev (rankAccuracySetting this == HighRanksAreAccurate) total  -- | Returns true if this sketch is empty.@@ -492,7 +534,7 @@     when (rankAccuracy /= otherRankAccuracy) $       error "Both sketches must have the same HighRankAccuracy setting."     -- update total-    otherN <- getN other+    otherN <- count other     modifyURef (totalN this) (+ otherN)     -- update the min and max values     thisMin <- minimum this@@ -530,8 +572,8 @@         grow this  -- | Updates this sketch with the given item.-update :: (PrimMonad m, KnownNat k) => ReqSketch k (PrimState m) -> Double -> m ()-update this item = do+insert :: (PrimMonad m, KnownNat k) => ReqSketch k (PrimState m) -> Double -> m ()+insert this item = do   unless (isNaN item) $ do     isEmpty <- getIsEmpty this     if isEmpty@@ -549,7 +591,7 @@     modifyURef (retainedItems this) (+1)     modifyURef (totalN this) (+1)     modifyURef (sumValue this) (+ item)-    retItems <- getRetainedItems this+    retItems <- retainedItemCount this     maxNominalCapacity <- getMaxNominalCapacity this     when (retItems >= maxNominalCapacity) $ do       DoubleBuffer.sort buff

@@ -4,7 +4,7 @@ import Statistics.Quantile import Test.Hspec import qualified Data.Vector as V-import DataSketches.Quantiles.RelativeErrorQuantile (mkReqSketch, RankAccuracy (HighRanksAreAccurate), update)+import DataSketches.Quantiles.RelativeErrorQuantile (mkReqSketch, RankAccuracy (HighRanksAreAccurate), insert) import qualified DataSketches.Quantiles.RelativeErrorQuantile as SK import Test.QuickCheck import Control.Monad.ST@@ -47,7 +47,7 @@     property $ forAll sampleInputGen $ \(NonEmpty doubles) -> runST $ do       let sampleData = V.fromList doubles       sk <- mkReqSketch @6 HighRanksAreAccurate-      mapM_ (update sk) sampleData+      mapM_ (insert sk) sampleData       let ranks = [0.01, 0.02 .. 0.99]           rankInts = map (floor . (* 100)) ranks       upperLowerBounds <- mapM (upperAndLowerBound sk) ranks

@@ -9,7 +9,7 @@ import DataSketches.Quantiles.RelativeErrorQuantile import DataSketches.Quantiles.RelativeErrorQuantile.Types import DataSketches.Quantiles.RelativeErrorQuantile.Internal.Auxiliary-import Data.List+import Data.List hiding (insert) import Data.Maybe (fromJust, isJust) import Data.Proxy import GHC.TypeLits@@ -21,30 +21,30 @@ spec = do   specify "non finite PMF/CDF should throw" $ asIO $ do     sk <- mkReqSketch @6 HighRanksAreAccurate-    update sk 1+    insert sk 1     cumulativeDistributionFunction sk [0 / 0] `shouldThrow` (== CumulativeDistributionInvariantsSplitsAreNotFinite)   specify "updating a sketch with NaN should ignore it" $ asIO $ do     sk <- mkReqSketch @6 HighRanksAreAccurate-    update sk (0 / 0)+    insert sk (0 / 0)     isEmpty <- DataSketches.Quantiles.RelativeErrorQuantile.null sk     isEmpty `shouldBe` True   specify "non finite rank should throw" $ asIO $ do     let infinity = read "Infinity"::Double     sk <- mkReqSketch @6 HighRanksAreAccurate-    update sk 1+    insert sk 1     (rank sk infinity >>= print) `shouldThrow` (\(DoubleIsNonFiniteException _) -> True)   specify "big merge doesn't explode" $ asIO $ do     sk1 <- mkReqSketch @6 HighRanksAreAccurate-    mapM_ (update sk1) [5..10]+    mapM_ (insert sk1) [5..10]     sk2 <- mkReqSketch @6 HighRanksAreAccurate     merge sk1 sk2-    mapM_ (update sk2) [1..15]+    mapM_ (insert sk2) [1..15]     merge sk1 sk2-    n <- getN sk1+    n <- count sk1     n `shouldBe` 21-    mapM_ (update sk2) [16..300]+    mapM_ (insert sk2) [16..300]     merge sk1 sk2-    n <- getN sk1+    n <- count sk1     n `shouldBe` 321   describe "property tests" $ do     specify "ReqSketch quantile estimates are within ε bounds compared to real quantile calculations" $ print ()@@ -55,12 +55,12 @@   let lessThanEqRs = [0.3, 0.3, 0.3, 0.6, 0.6, 0.6, 0.7, 1.0, 1.0, 1.0]   let simpleTestSetup = do         sk <- mkReqSketch @50 HighRanksAreAccurate-        mapM_ (update sk) simpleTestValues+        mapM_ (insert sk) simpleTestValues         pure sk   specify "lots of repeat values should work" $ asIO $ do     sk <- mkReqSketch @6 HighRanksAreAccurate-    replicateM_ 10_000 (update sk 1 >> getRetainedItems sk)-    print =<< getRetainedItems sk+    replicateM_ 10_000 (insert sk 1 >> retainedItemCount sk)+    print =<< retainedItemCount sk    describe "simple test" $ before simpleTestSetup $ do     describe "<" $ do@@ -98,9 +98,9 @@   describe "quantiles" $ do     it "should be reasonable" $ asIO $ do       sk <- mkReqSketch @6 HighRanksAreAccurate-      update sk 1-      update sk 1-      update sk 1+      insert sk 1+      insert sk 1+      insert sk 1       r <- quantile sk 0.5             r `shouldBe` 1.0 @@ -133,11 +133,11 @@ mergeSpec :: Spec mergeSpec = specify "merge works" $ asIO $ do   s1 <- mkReqSketch HighRanksAreAccurate :: IO (ReqSketch 12 (PrimState IO))-  mapM_ (update s1) [0..40]+  mapM_ (insert s1) [0..40]   s2 <- mkReqSketch HighRanksAreAccurate :: IO (ReqSketch 12 (PrimState IO))-  mapM_ (update s2) [0..40]+  mapM_ (insert s2) [0..40]   s3 <- mkReqSketch HighRanksAreAccurate :: IO (ReqSketch 12 (PrimState IO))-  mapM_ (update s3) [0..40]+  mapM_ (insert s3) [0..40]   s <- mkReqSketch HighRanksAreAccurate :: IO (ReqSketch 12 (PrimState IO))   s `merge` s1   s `merge` s2@@ -148,7 +148,7 @@ loadSketch k min_ max_ hra ltEq up = do   sk <- mkReqSketch hra :: IO (ReqSketch n (PrimState IO))   -- This just seems geared at making sure that ranks come out right regardless of order-  mapM_ (update sk . fromIntegral) $ if up+  mapM_ (insert sk . fromIntegral) $ if up     then [min_ .. max_]     else reverse [min_ .. max_ {- + 1 -}]   pure sk