perfect-hash-generator 0.1.0.3 → 0.1.0.4
raw patch · 6 files changed
+110/−114 lines, 6 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
Files
- demo-ints/Main.hs +71/−0
- demo-strings/Main.hs +33/−0
- demo/Ints/Main.hs +0/−71
- demo/Strings/Main.hs +0/−33
- perfect-hash-generator.cabal +5/−9
- src/Data/PerfectHash/Lookup.hs +1/−1
+ demo-ints/Main.hs view
@@ -0,0 +1,71 @@+module Main where++import System.Random (RandomGen, mkStdGen, randomR)++import Data.IntSet (IntSet)+import qualified Data.IntSet as IntSet+import qualified Data.PerfectHash.Construction as Construction+import qualified Data.PerfectHash.Hashing as Hashing+import qualified Data.PerfectHash.Lookup as Lookup+import qualified Data.Vector.Unboxed as Vector+import Exercise (Atom (Atom))+import qualified Exercise+++valueCount = 500000++randomRange = (0, Hashing.mask32bits)+++data RandIntAccum t = RandIntAccum+ t -- ^ random number generator+ Int -- ^ max count+ IntSet -- ^ accumulated unique random numbers+++-- | Since computing the size of the set is O(N), we+-- maintain the count separately.+getUniqueRandomIntegers :: RandomGen t => RandIntAccum t -> IntSet+getUniqueRandomIntegers (RandIntAccum std_gen count current_set) =++ if count == 0+ then current_set+ else getUniqueRandomIntegers newstate++ where+ (next_int, next_std_gen) = randomR randomRange std_gen++ a = RandIntAccum next_std_gen+ newstate = if IntSet.member next_int current_set+ then a count current_set+ else a (count - 1) (IntSet.insert next_int current_set)+++intMapTuples :: [(Atom Int, Int)]+intMapTuples = zip (map Atom random_ints) [1..]+ where+ seed_value = RandIntAccum (mkStdGen 0) valueCount IntSet.empty+ random_ints = IntSet.toList $ getUniqueRandomIntegers seed_value+++main = do++ putStrLn $ unwords ["Keys size:", show $ length intMapTuples]++ let lookup_table = Construction.createMinimalPerfectHash intMapTuples++ putStrLn $ unwords [+ "Finished computing lookup table with"+ , show $ Lookup.size lookup_table+ , "entries."+ ]++ let direct_mapping_nonces = Vector.filter (< 0) $ Lookup.nonces lookup_table++ putStrLn $ unwords [+ "There were"+ , show $ Vector.length direct_mapping_nonces+ , "lookup entries with direct mappings."+ ]++ Exercise.eitherExit $ Exercise.testLookups lookup_table intMapTuples
+ demo-strings/Main.hs view
@@ -0,0 +1,33 @@+module Main where++import Control.Monad (when)++import qualified Data.PerfectHash.Construction as Construction+import qualified Data.PerfectHash.Lookup as Lookup+import qualified Exercise+++enableDebug = False++dictionaryPath = "/usr/share/dict/words"+++main = do++ word_index_tuples <- Exercise.wordsFromFile dictionaryPath++ putStrLn $ unwords ["Words size:", show $ length word_index_tuples]++ let lookup_table = Construction.createMinimalPerfectHash word_index_tuples++ putStrLn $ unwords [+ "Finished computing lookup table with"+ , show $ Lookup.size lookup_table+ , "entries."+ ]++ when enableDebug $ do+ putStrLn $ unwords ["Vector G:", show $ Lookup.nonces lookup_table]+ putStrLn $ unwords ["Vector V:", show $ Lookup.values lookup_table]++ Exercise.eitherExit $ Exercise.testLookups lookup_table word_index_tuples
− demo/Ints/Main.hs
@@ -1,71 +0,0 @@-module Main where--import System.Random (RandomGen, mkStdGen, randomR)--import Data.IntSet (IntSet)-import qualified Data.IntSet as IntSet-import qualified Data.PerfectHash.Construction as Construction-import qualified Data.PerfectHash.Hashing as Hashing-import qualified Data.PerfectHash.Lookup as Lookup-import qualified Data.Vector.Unboxed as Vector-import Exercise (Atom (Atom))-import qualified Exercise---valueCount = 500000--randomRange = (0, Hashing.mask32bits)---data RandIntAccum t = RandIntAccum- t -- ^ random number generator- Int -- ^ max count- IntSet -- ^ accumulated unique random numbers----- | Since computing the size of the set is O(N), we--- maintain the count separately.-getUniqueRandomIntegers :: RandomGen t => RandIntAccum t -> IntSet-getUniqueRandomIntegers (RandIntAccum std_gen count current_set) =-- if count == 0- then current_set- else getUniqueRandomIntegers newstate-- where- (next_int, next_std_gen) = randomR randomRange std_gen-- a = RandIntAccum next_std_gen- newstate = if IntSet.member next_int current_set- then a count current_set- else a (count - 1) (IntSet.insert next_int current_set)---intMapTuples :: [(Atom Int, Int)]-intMapTuples = zip (map Atom random_ints) [1..]- where- seed_value = RandIntAccum (mkStdGen 0) valueCount IntSet.empty- random_ints = IntSet.toList $ getUniqueRandomIntegers seed_value---main = do-- putStrLn $ unwords ["Keys size:", show $ length intMapTuples]-- let lookup_table = Construction.createMinimalPerfectHash intMapTuples-- putStrLn $ unwords [- "Finished computing lookup table with"- , show $ Lookup.size lookup_table- , "entries."- ]-- let direct_mapping_nonces = Vector.filter (< 0) $ Lookup.nonces lookup_table-- putStrLn $ unwords [- "There were"- , show $ Vector.length direct_mapping_nonces- , "lookup entries with direct mappings."- ]-- Exercise.eitherExit $ Exercise.testLookups lookup_table intMapTuples
− demo/Strings/Main.hs
@@ -1,33 +0,0 @@-module Main where--import Control.Monad (when)--import qualified Data.PerfectHash.Construction as Construction-import qualified Data.PerfectHash.Lookup as Lookup-import qualified Exercise---enableDebug = False--dictionaryPath = "/usr/share/dict/words"---main = do-- word_index_tuples <- Exercise.wordsFromFile dictionaryPath-- putStrLn $ unwords ["Words size:", show $ length word_index_tuples]-- let lookup_table = Construction.createMinimalPerfectHash word_index_tuples-- putStrLn $ unwords [- "Finished computing lookup table with"- , show $ Lookup.size lookup_table- , "entries."- ]-- when enableDebug $ do- putStrLn $ unwords ["Vector G:", show $ Lookup.nonces lookup_table]- putStrLn $ unwords ["Vector V:", show $ Lookup.values lookup_table]-- Exercise.eitherExit $ Exercise.testLookups lookup_table word_index_tuples
perfect-hash-generator.cabal view
@@ -3,7 +3,7 @@ -- see: https://github.com/sol/hpack name: perfect-hash-generator-version: 0.1.0.3+version: 0.1.0.4 synopsis: Perfect minimal hashing implementation in native Haskell description: A <https://en.wikipedia.org/wiki/Perfect_hash_function perfect hash function> for a set @S@ is a hash function that maps distinct elements in @S@ to a set of integers, with __no collisions__. A <https://en.wikipedia.org/wiki/Perfect_hash_function#Minimal_perfect_hash_function minimal perfect hash function> is a perfect hash function that maps @n@ keys to @n@ __consecutive__ integers, e.g. the numbers from @0@ to @n-1@. .@@ -71,9 +71,9 @@ default-language: Haskell2010 executable hash-perfectly-ints-demo- main-is: Ints/Main.hs+ main-is: Main.hs hs-source-dirs:- demo+ demo-ints test ghc-options: -fwarn-tabs -W build-depends:@@ -86,15 +86,13 @@ , hashable , containers other-modules:- Strings.Main Exercise- Main default-language: Haskell2010 executable hash-perfectly-strings-demo- main-is: Strings/Main.hs+ main-is: Main.hs hs-source-dirs:- demo+ demo-strings test ghc-options: -fwarn-tabs -W build-depends:@@ -106,9 +104,7 @@ , vector , hashable other-modules:- Ints.Main Exercise- Main default-language: Haskell2010 test-suite regression-tests
src/Data/PerfectHash/Lookup.hs view
@@ -1,7 +1,7 @@ {-# OPTIONS_HADDOCK prune #-} -- | Note that what is referred to as a \"nonce\" in this library may be--- equivalently described as a \"salt\" by some.+-- referred to by some as a \"salt\". module Data.PerfectHash.Lookup ( LookupTable (LookupTable) , nonces