Data.Judy

Very fast, mutable associative data types based on Judy arrays.

A good imperative, mutable replacement for IntMap.

Judy arrays are both speed- and memory-efficient, with no tuning or configuration required, across a wide range of index set types (sequential, periodic, clustered, random). Judy's speed and memory usage are typically better than other data storage models such as skiplists, linked lists, binary, ternary, b-trees, or even hashing, and improves with very large data sets.

The memory used by a Judy array is nearly proportional to the population (number of elements).

For further references to the implementation, see:

• http://en.wikipedia.org/wiki/Judy_array

Building a simple word-index table. About 4x faster than using an IntMap

 import Control.Monad
 import qualified Data.Judy as J

 main = do
    j <- J.new :: IO (J.JudyL Int)
    forM_ [1..10000000] $ \n -> J.insert n (fromIntegral n :: Int) j
    v <- J.lookup 100 j
    print v

Running this:

 $ ghc -O2 --make A.hs
 [1 of 1] Compiling Main             ( A.hs, A.o )
 Linking A ...

 $ time ./A
 Just 100
 ./A  1.95s user 0.08s system 99% cpu 2.028 total

Basic types

data JudyL a

A JudyL array is a finite map from Word to Word values. A value is addressed by a key (Key). The array may be sparse, and the key may be any word-sized value. There are no duplicate keys.

Instances

Show (JudyL a)

type Key = Word

The type of keys in the JudyL arrays. A word-sized type (64 or 32 bits)

Operations

new :: JA a => IO (JudyL a)

Allocate a new empty JudyL array. A finalizer is associated with the JudyL array, that will free it automatically once the last reference has been dropped.

insert :: JA a => Key -> a -> JudyL a -> IO ()

Insert a key and value pair into the JudyL array. *If the key is already present in the map, the value is not modified*

lookup :: JA a => Key -> JudyL a -> IO (Maybe a)

Lookup a value associated with a key in the JudyL array.

delete :: Key -> JudyL a -> IO ()

Delete the Index/Value pair from the JudyL array.

Judy-storable types

class JA a where

Class of things that can be stored in the JudyL array. You need to be able to convert the structure to a Word value, or a word-sized pointer.

Methods

toWord :: a -> IO Word

fromWord :: Word -> IO a

Instances

JA Bool

JA Int

JA Int8

JA Int16

JA Int32

JA Word

JA Word8

JA Word16

JA Word32

JA ()