cuckoo-filter 0.1.0.0 → 0.1.0.1
raw patch · 4 files changed
+5/−6 lines, 4 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
Files
- README.md +2/−2
- cuckoo-filter.cabal +2/−2
- src/Data/CuckooFilter/Internal.hs +0/−1
- test/Spec.hs +1/−1
README.md view
@@ -1,6 +1,6 @@ # cuckoo-filter -[](https://travis-ci.org/ChrisCoffey/cuckoo-filter)+[](https://hackage.haskell.org/package/cuckoo-filter)[](https://travis-ci.org/ChrisCoffey/cuckoo-filter) Cuckoo filters are a probabilistic data structure used to answer questions like "Have I already seen this user" or "Is this word in the English language?". They're _probabilistic_ because each membership operation has a false positive probability. It guarnatees that there will never be a false negative, but may have a low chance of false positives. @@ -15,7 +15,7 @@ For more details about how Cuckoo filters work, I recommend you read Fan et. al.'s 2016 paper https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf. ### Usage-Cuckoo filters support three operations: `insert`, `member`, and `delete`. See the [haddocks]() for details.+Cuckoo filters support three operations: `insert`, `member`, and `delete`. See the [haddocks](https://hackage.haskell.org/package/cuckoo-filter) for details. ### Performance As you'll find in the criterion results, the pure version of the filter can handle ~1.6 million insertions/s. From memory profiles, the vast majority of the memory is taken up by the underlying implementation of `Filter`, so this is an obvious area for improvement.
cuckoo-filter.cabal view
@@ -4,10 +4,10 @@ -- -- see: https://github.com/sol/hpack ----- hash: 39f661e082b0630ac91c43d1adf7e2cfb00d6a9e2983e9223a63e7ea8433c78f+-- hash: 0ebb44bfcf7104adcb38947b3420f70be3728a604ef7b442ab103b8815b32630 name: cuckoo-filter-version: 0.1.0.0+version: 0.1.0.1 synopsis: Pure and impure Cuckoo Filter description: Please see the README on Github at <https://github.com/ChrisCoffey/cuckoo-filter#readme> category: Data
src/Data/CuckooFilter/Internal.hs view
@@ -144,7 +144,6 @@ size = Size s } where- addBucket rawFilt n = IM.insert (fromIntegral n) emptyBucket rawFilt numBuckets = s `div` 4 --
test/Spec.hs view
@@ -21,7 +21,7 @@ testProperty "insert x >> delete x is idempotent" $ \s -> let Just f = insert defaultFilter s f' = delete f s- in defaultFilter == f'+ in not (member s f') ,testProperty "inserts into a full filter will fail" $ \s n -> let f = insertNTimes (100000 + abs n) s defaultFilter