cuckoo 0.2.0.0 → 0.2.0.1

raw patch · 4 files changed

+40/−22 lines, 4 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• CHANGELOG.md +5/−1
• README.md +20/−12
• cuckoo.cabal +1/−1
• src/Data/Cuckoo.hs +14/−8

@@ -1,5 +1,9 @@ # Revision history for cuckoo +## 0.2.0.1 -- 2019-08-20++* Fixed and improved example.+ ## 0.2.0.0 -- 2019-08-20  * The PRNG from the random package is new the default. Added cabal flags for@@ -8,7 +12,7 @@ * Changed order of type parameters for `newCuckooHash`. The type of the monad is   moved to the end, because its usually inferred from the context. -* Minimum capacity (in items) parameter is now 64.+* Capacity (in items) parameter must be at least 64.  * Fixed the result of `sizeInAllocatedBytes`. 

@@ -46,6 +46,7 @@ {-# LANGUAGE DataKinds #-} {-# LANGUAGE TypeApplications #-} {-# LANGUAGE TypeFamilies #-}+{-# OPTIONS_GHC -fno-warn-orphans #-}  import Control.Monad (filterM) import Data.Cuckoo@@ -60,25 +61,30 @@     f <- newCuckooFilter @4 @8 @Int 0 500000      -- Insert 450000 items-    failed <- filterM (fmap not . insert f) [0..450000]+    failed <- filterM (fmap not . insert f) [0..500000-1]      -- Query inserted items-    missing <- filterM (fmap not . member f) [0..450000]+    missing <- filterM (fmap not . member f) [0..500000-1] +    -- Test for false positives+    false <- filterM (member f) [500000..1000000 - 1]+     -- Report results     putStrLn $ "failed inserts: " <> show (length failed)-    putStrLn $ "false positives: " <> show (length $ failed \\ missing)-    putStrLn $ "missing: " <> show (length $ missing \\ failed)-    c <- itemCount f+    putStrLn $ "false positives: " <> show (length false)+    putStrLn $ "false positive rate (%): " <> show @Double (fromIntegral (length false) * 100 / 500000)+    putStrLn $ "missing (must be 0): " <> show (length $ missing \\ failed) -    -- some properties of the filter+    -- Filter properties     putStrLn $ "capacity: " <> show (capacityInItems f)     putStrLn $ "size in allocated bytes: " <> show (sizeInAllocatedBytes f) -    -- computing the following is slow+    -- computing the following is a bit slow+    c <- itemCount f     putStrLn $ "item count: " <> show c     lf <- loadFactor f-    putStrLn $ "load factor: " <> show lf+    putStrLn $ "load factor (%): " <> show lf+    putStrLn $ "bits per item: " <> show @Double (fromIntegral (sizeInAllocatedBytes f) * 8 / fromIntegral c) ```  Which produces the following results:@@ -89,12 +95,14 @@ Linking main ... $ ./main failed inserts: 0-false positives: 0-missing: 0+false positives: 14796+false postive rate (%): 2.9592+missing (must be 0): 0 capacity: 524288 size in allocated bytes: 524292-item count: 450001-load factor: 85.83087921142578+item count: 500000+load factor (%): 95.367431640625+bits per item: 8.388672 ```  Another example can be found in the file

@@ -1,6 +1,6 @@ cabal-version: 2.2 name: cuckoo-version: 0.2.0.0+version: 0.2.0.1 synopsis: Haskell Implementation of Cuckoo Filters Description:     Haskell implementation of Cuckoo filters as described in

@@ -35,6 +35,7 @@ -- > {-# LANGUAGE DataKinds #-} -- > {-# LANGUAGE TypeApplications #-} -- > {-# LANGUAGE TypeFamilies #-}+-- > {-# OPTIONS_GHC -fno-warn-orphans #-} -- > -- > import Control.Monad (filterM) -- > import Data.Cuckoo@@ -49,25 +50,30 @@ -- >     f <- newCuckooFilter @4 @8 @Int 0 500000 -- > -- >     -- Insert 450000 items--- >     failed <- filterM (fmap not . insert f) [0..450000]+-- >     failed <- filterM (fmap not . insert f) [0..500000-1] -- > -- >     -- Query inserted items--- >     missing <- filterM (fmap not . member f) [0..450000]+-- >     missing <- filterM (fmap not . member f) [0..500000-1] -- >+-- >     -- Test for false positives+-- >     false <- filterM (member f) [500000..1000000 - 1]+-- > -- >     -- Report results -- >     putStrLn $ "failed inserts: " <> show (length failed)--- >     putStrLn $ "false positives: " <> show (length $ failed \\ missing)--- >     putStrLn $ "missing: " <> show (length $ missing \\ failed)--- >     c <- itemCount f+-- >     putStrLn $ "false positives: " <> show (length false)+-- >     putStrLn $ "false positive rate (%): " <> show @Double (fromIntegral (length false) * 100 / 500000)+-- >     putStrLn $ "missing (must be 0): " <> show (length $ missing \\ failed) -- >--- >     -- some properties of the filter+-- >     -- Filter properties -- >     putStrLn $ "capacity: " <> show (capacityInItems f) -- >     putStrLn $ "size in allocated bytes: " <> show (sizeInAllocatedBytes f) -- >--- >     -- computing the following is slow+-- >     -- computing the following is a bit slow+-- >     c <- itemCount f -- >     putStrLn $ "item count: " <> show c -- >     lf <- loadFactor f--- >     putStrLn $ "load factor: " <> show lf+-- >     putStrLn $ "load factor (%): " <> show lf+-- >     putStrLn $ "bits per item: " <> show @Double (fromIntegral (sizeInAllocatedBytes f) * 8 / fromIntegral c) -- module Data.Cuckoo (