[Haskell-beginners] vector indexing time
Nick Vanderweit
nick.vanderweit at gmail.com
Fri Aug 3 05:20:29 CEST 2012
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
More information about the Beginners
mailing list