quickIndex.hs

import System.Environment

quickIndex :: [a] -> Int -> a
quickIndex xs = \n -> if n < blockSize then xs !! n else (nextLevel (n `div` blockSize)) !! (n `mod` blockSize)
  where
    blockSize = 32
    skipList ys = ys : skipList (drop blockSize ys)
    nextLevel = quickIndex $ skipList xs

example :: Integer -> Integer
example n = sum [ vs i | i <- [0..fromInteger n] ] where vs = quickIndex [0..]

main = getArgs >>= print . example . read . head

-- [~]$ for N in {5,6,7,8}; do echo $[10**N]; /usr/bin/time ./quickIndex $[10**N]; done
-- 100000
-- 5000050000
-- 0.04user 0.00system 0:00.04elapsed 97%CPU (0avgtext+0avgdata 12084maxresident)k
-- 0inputs+0outputs (0major+2350minor)pagefaults 0swaps
-- 1000000
-- 500000500000
-- 0.35user 0.04system 0:00.40elapsed 100%CPU (0avgtext+0avgdata 74120maxresident)k
-- 0inputs+0outputs (0major+17809minor)pagefaults 0swaps
-- 10000000
-- 50000005000000
-- 4.48user 0.18system 0:04.66elapsed 99%CPU (0avgtext+0avgdata 560456maxresident)k
-- 0inputs+0outputs (0major+139410minor)pagefaults 0swaps
-- 100000000
-- 5000000050000000
-- 49.17user 1.45system 0:50.64elapsed 99%CPU (0avgtext+0avgdata 4390148maxresident)k
-- 0inputs+0outputs (0major+1096848minor)pagefaults 0swaps