The vector indexing using (!) should run in constant time. However, as the Data.Vector.Unboxed haddock documentation states, enumFromN allocates and populates the vector in linear time using its stream code. I'm not familiar with the stream code, but it looks to be of similar nature to the basic list type. Nick On Friday, August 03, 2012 04:45:38 AM Ivan Vyalov wrote:
Hi everyone!
I have a question about time complexity of vector indexing. Obviously, it should be constant, but if I do the following naive tests it looks linear. What do I do wrong?
Ivan
$ for i in 10000000 20000000 40000000 80000000 ; do cat vec_in_"$i".hs; ghc -fforce-recomp -O2 --make vec_in_"$i".hs && time ./vec_in_"$i"; done import Data.Vector.Unboxed main = do let a = enumFromN 1 100000001 :: Vector Int print $ a ! 10000000
[1 of 1] Compiling Main ( vec_in_10000000.hs, vec_in_10000000.o ) Linking vec_in_10000000 ... 10000001
real 0m0.033s user 0m0.032s sys 0m0.000s import Data.Vector.Unboxed main = do let a = enumFromN 1 100000001 :: Vector Int print $ a ! 20000000
[1 of 1] Compiling Main ( vec_in_20000000.hs, vec_in_20000000.o ) Linking vec_in_20000000 ... 20000001
real 0m0.062s user 0m0.060s sys 0m0.000s import Data.Vector.Unboxed main = do let a = enumFromN 1 100000001 :: Vector Int print $ a ! 40000000
[1 of 1] Compiling Main ( vec_in_40000000.hs, vec_in_40000000.o ) Linking vec_in_40000000 ... 40000001
real 0m0.125s user 0m0.120s sys 0m0.004s import Data.Vector.Unboxed main = do let a = enumFromN 1 100000001 :: Vector Int print $ a ! 80000000
[1 of 1] Compiling Main ( vec_in_80000000.hs, vec_in_80000000.o ) Linking vec_in_80000000 ... 80000001
real 0m0.244s user 0m0.240s sys 0m0.000s
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners