[Haskell-beginners] vector indexing time

[Nick Vanderweit]

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 at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners