Hi,
I have written a small "wrapper" to speed random-access to a list. The
usage scenario I have in mind is a "stream" computation yielding an
infinite list, and I want to randomly access elements w/o having to
traverse the entire list from the beginning for each access.
I suspected something similar must already exist, but nothing I looked
at seemed to do the trick. IntMap seems to want a finite input list.
Ditto for the various array types, except possibly dynamic array.
Attached is the list indexer I came up with, and a small test program
(I swap the commented-out lines to switch btw. list & list index tests).
I am interested to hear any feedback on this -- whether it duplicates
something that already exists, or whether there's a better approach, and
comments on the code, etc. Also if somebody can suggest a better name
(so as not to overlay the word index too much.) I'll publish it on
hackage (or at least github) if people think it's useful. It sped up
the program I initally wrote it for enormously.
Thanks,
Alex
{- |
Module : ListIndex
Description : list indexer, providing fast random list lookup
Copyright : (c) Alex Stangl 2012
License : BSD3
Maintainer : [email protected]
Stability : unstable
Portability : portable
Wrap a list, providing faster access, like a skip-list. This was primarily
written to wrap an infinite list, lazily building the index as the list is
accessed. For finite lists, an array is probably a better choice.
Fanout controls how much each level of the index jumps, or "fans out" from
the previous level. 4, 8, 16, or 32 would be a good default choice for this,
but feel free to experiment. Memory usage should be roughly proportional to
accessed list size / (fanout - 1)
-}
module ListIndex (fromList, (!), LI) where
-- | Type of index wrapping an underlying list
data LI a = LI Int [LInode a]
data LInode a = LiNonLeaf (LInode a) (LInode a) | LiLeaf (LInode a) [a]
-- | Constructs index from specified list and fanout
fromList :: [a] -> Int -> LI a
fromList l fo =
let topLevel = mkTopLevelNode l
mkTopLevelNode l = LiLeaf (mkTopLevelNode (drop fo l)) l
mkLevel plv = let lv = mkMidLevelNode plv
in lv : mkLevel lv
mkMidLevelNode l = LiNonLeaf (mkMidLevelNode (nodeDrop fo l)) l
in LI fo (topLevel : mkLevel topLevel)
-- drop i nodes from a linear node stream
nodeDrop :: Int -> LInode a -> LInode a
nodeDrop 0 n = n
nodeDrop i n = let i' = i - 1
in case n of
LiNonLeaf n' _ -> nodeDrop i' n'
LiLeaf n' _ -> nodeDrop i' n'
-- | access specified element of underlying list using index to speed access
(!) :: LI a -> Int -> a
(!) (LI fo ns) i =
let getLevel k (n : ns) = let (q,r) = k `quotRem` fo
l = if q == 0
then n
else parent $ getLevel q ns
in nodeDrop r l
parent (LiNonLeaf _ p) = p
(q, r) = i `quotRem` fo
(LiLeaf _ l) = getLevel q ns
in l !! r
-- Simple tests to check efficiency of ListIndex vs. direct
-- list access for sequential access (via !!) and pseudorandom
-- access.
--
-- Alex Stangl
import System.Random
import ListIndex
a = [1..]
b = fromList a 4
testSequential = [(!) b n | n <- [1,3..100000]]
--testSequential = [a!!n | n <- [1,3..100000]]
randAccess = let seed = 12345813
g = mkStdGen seed
hi = 10000000
lst = [1,3..hi]
lst' = fromList lst 32
nIter = 1000
randR _ 0 = []
randR g n = let (a,g') = randomR (0, hi `div` 2 - 1) g
n' = n - 1
--in (lst!!a) : randR g' n'
in (lst'!a) : randR g' n'
in sum $ randR g nIter
main = putStrLn $ show $ randAccess
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
