Hi <div><br></div><div>I find it useful. I benchmarked it with criterion and your test file (see below) and it is a *lot* faster:</div><div><br></div><div><div>warming up</div><div>estimating clock resolution...</div><div>
mean is 3.776987 us (160001 iterations)</div><div>found 887 outliers among 159999 samples (0.6%)</div><div> 662 (0.4%) high severe</div><div>estimating cost of a clock call...</div><div>mean is 1.404134 us (27 iterations)</div>
<div>found 5 outliers among 27 samples (18.5%)</div><div> 1 (3.7%) low mild</div><div> 1 (3.7%) high mild</div><div> 3 (11.1%) high severe</div><div><br></div><div>benchmarking randAccess IndexList</div><div>mean: 2.614148 ms, lb 2.603860 ms, ub 2.642045 ms, ci 0.950</div>
<div>std dev: 79.90122 us, lb 33.73238 us, ub 165.6168 us, ci 0.950</div><div>found 13 outliers among 100 samples (13.0%)</div><div> 12 (12.0%) high severe</div><div>variance introduced by outliers: 25.781%</div><div>variance is moderately inflated by outliers</div>
<div><br></div><div>benchmarking randAccess list</div><div>mean: 42.62869 ms, lb 42.38446 ms, ub 43.48986 ms, ci 0.950</div><div>std dev: 2.088308 ms, lb 598.3515 us, ub 4.751391 ms, ci 0.950</div><div>found 3 outliers among 100 samples (3.0%)</div>
<div> 2 (2.0%) high severe</div><div>variance introduced by outliers: 47.437%</div><div>variance is moderately inflated by outliers</div><div><br></div><div>benchmarking seqAccess IndexList</div><div>mean: 6.347177 ms, lb 6.325560 ms, ub 6.369031 ms, ci 0.950</div>
<div>std dev: 111.3361 us, lb 102.5431 us, ub 123.4909 us, ci 0.950</div><div>variance introduced by outliers: 10.386%</div><div>variance is moderately inflated by outliers</div><div><br></div><div>benchmarking seqAccess list</div>
<div>collecting 100 samples, 1 iterations each, in estimated 207.9468 s</div><div>mean: 1.919024 s, lb 1.916933 s, ub 1.927423 s, ci 0.950</div><div>std dev: 19.69444 ms, lb 1.966086 ms, ub 46.74818 ms, ci 0.950</div></div>
<div><br></div><div><br></div><div>Maybe an elevator list is a nice name?</div><div><br></div><div>Greets,</div><div><br></div><div>Edgar </div><div><br></div><div><br></div><div><div>module Main where </div><div>import Criterion.Main </div>
<div>import System.Random</div><div>-- | Type of index wrapping an underlying list</div><div>data LI a = LI Int [LInode a]</div><div>data LInode a = LiNonLeaf (LInode a) (LInode a) | LiLeaf (LInode a) [a]</div><div><br></div>
<div>-- | Constructs index from specified list and fanout</div><div>fromList :: [a] -> Int -> LI a</div><div>fromList l fo =</div><div> let topLevel = mkTopLevelNode l</div><div> mkTopLevelNode l = LiLeaf (mkTopLevelNode (drop fo l)) l</div>
<div> mkLevel plv = let lv = mkMidLevelNode plv</div><div> in lv : mkLevel lv</div><div> mkMidLevelNode l = LiNonLeaf (mkMidLevelNode (nodeDrop fo l)) l</div><div> in LI fo (topLevel : mkLevel topLevel)</div>
<div><br></div><div>-- drop i nodes from a linear node stream</div><div>nodeDrop :: Int -> LInode a -> LInode a</div><div>nodeDrop 0 n = n</div><div>nodeDrop i n = let i' = i - 1</div><div> in case n of</div>
<div> LiNonLeaf n' _ -> nodeDrop i' n'</div><div> LiLeaf n' _ -> nodeDrop i' n'</div><div><br></div><div>-- | access specified element of underlying list using index to speed access</div>
<div>(!) :: LI a -> Int -> a</div><div>(!) (LI fo ns) i =</div><div> let getLevel k (n : ns) = let (q,r) = k `quotRem` fo</div><div> l = if q == 0</div><div> then n</div>
<div> else parent $ getLevel q ns</div><div> in nodeDrop r l</div><div> parent (LiNonLeaf _ p) = p</div><div> (q, r) = i `quotRem` fo</div><div> (LiLeaf _ l) = getLevel q ns</div>
<div> in l !! r</div><div><br></div><div>a = [1 :: Int ..]</div><div>b = fromList a 4</div><div><br></div><div>testSequential hi = [(!) b n | n <- [1,3..hi :: Int]]</div><div>testSequentialList hi = [a!!n | n <- [1,3..hi :: Int]]</div>
<div><br></div><div>randAccess hi = </div><div> let seed = 12345813</div><div> g = mkStdGen seed</div><div> lst = [1,3..hi]</div><div> lst' = fromList lst 32</div>
<div> nIter = 1000</div><div> randR _ 0 = []</div><div> randR g n = let (a,g') = randomR (0, hi `div` 2 - 1) g </div><div> n' = n - 1</div>
<div> --in (lst!!a) : randR g' n'</div><div> in (lst'!a) : randR g' n'</div><div> in sum $ randR g nIter</div><div>-- main = putStrLn $ show $ randAccess</div>
<div><br></div><div>randAccessList hi = </div><div> let seed = 12345813</div><div> g = mkStdGen seed</div><div> lst = [1,3..hi]</div><div> nIter = 1000</div><div>
randR _ 0 = []</div><div> randR g n = let (a,g') = randomR (0, hi `div` 2 - 1) g </div><div> n' = n - 1</div><div> in (lst!!a) : randR g' n'</div>
<div> in sum $ randR g nIter</div><div><br></div><div>main = let hi = 50000 in defaultMain [ bench "randAccess IndexList" (nf (randAccess) hi),</div><div> bench "randAccess list" (nf (randAccessList) hi),</div>
<div> bench "seqAccess IndexList" (nf (testSequential) hi),</div><div> bench "seqAccess list" (nf (testSequentialList) hi)</div><div> ]</div>
<div>
<br></div></div><div><br><div class="gmail_quote">On Sat, Sep 8, 2012 at 8:55 AM, Alex Stangl <span dir="ltr"><<a href="mailto:alex@stangl.us" target="_blank">alex@stangl.us</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi,<br>
<br>
I have written a small "wrapper" to speed random-access to a list. The<br>
usage scenario I have in mind is a "stream" computation yielding an<br>
infinite list, and I want to randomly access elements w/o having to<br>
traverse the entire list from the beginning for each access.<br>
<br>
I suspected something similar must already exist, but nothing I looked<br>
at seemed to do the trick. IntMap seems to want a finite input list.<br>
Ditto for the various array types, except possibly dynamic array.<br>
<br>
Attached is the list indexer I came up with, and a small test program<br>
(I swap the commented-out lines to switch btw. list & list index tests).<br>
I am interested to hear any feedback on this -- whether it duplicates<br>
something that already exists, or whether there's a better approach, and<br>
comments on the code, etc. Also if somebody can suggest a better name<br>
(so as not to overlay the word index too much.) I'll publish it on<br>
hackage (or at least github) if people think it's useful. It sped up<br>
the program I initally wrote it for enormously.<br>
<br>
Thanks,<br>
<br>
Alex<br>
<br>
<br>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br></div>