Vektörlerin zaman uyumlulaştırılması için O (n) amortize edilmeye çalışıyorum. Çalışıyor gibi görünüyor, ancak kutulu değerleri (vektörler gibi) saklamak gerekirse, sonuç hala çok yavaş. Bu örnekte Kutulu vektörler neden bu kadar yavaş?
import qualified Data.Vector as V
import qualified Data.Vector.Generic.Mutable as GM
import Data.Vector(Vector)
import Control.Monad.State.Strict
import Control.Monad.ST
data App = S !(Vector Int) !Int deriving (Show)
main = do
x <- liftM (map read . words) getContents
print $ execState (mapM_ (add . V.singleton) x) (S V.empty 0)
add :: Vector Int -> State App()
add v1 = do
S v2 n <- get
let v3 = vectorGrowAdd v1 v2 n
put (S v3 (n + V.length v1))
vectorGrowAdd v1 v2 n = runST $ do
m1 <- V.unsafeThaw v1
m2 <- V.unsafeThaw v2
m3 <- if GM.length m2 > (GM.length m1 + n)
then do
return m2
else do
GM.unsafeGrow m2 (GM.length m1 + 2*(GM.length m2))
let copyTo = GM.unsafeSlice n (GM.length m1) m3
GM.unsafeCopy copyTo m1
V.freeze m3
,
testVals
100000 tamsayılar olan bir metin dosyasıdır,
Boxed.hs
Yukarıdaki kod olup
Unboxed.hs
Data.Vector
ait
Data.Vector.Unboxed
instaid ithal hariç
Boxed.hs
aynıdır.
> ghc -v
Glasgow Haskell Compiler, Version 7.0.3
> ghc --make -O2 Boxed.hs
> time (cat testVals | ./Boxed.hs)
...
real 1m39.855s
user 1m39.282s
sys 0m0.252s
> ghc --make -O2 Unboxed.hs
> time (cat testVals | ./Unboxed.hs)
...
real 0m4.372s
user 0m4.268s
sys 0m0.088s
Soruma Soru: Neden Kutusuz ve Kutulu arasında büyük bir fark var? Kutusuz durumda olmayan değerleri saklamak gerekirse hızını artırmak için yapabileceğim bir şey var mı?
http://stackoverflow.com/q/7913934/283240 – HaskellElephant