5
하스켈에서 큰 정수 행렬을 정렬해야하고 임의의 데이터로 벤치마킹을 시작했습니다. 나는 하스켈이 C++보다 3 배 느리다는 것을 발견했다.하스켈 : 벡터 정렬보다 훨씬 느린 행렬 정렬
임의성 때문에 줄 비교가 항상 첫 번째 열 (중복이 없어야 함)에서 끝나기를 기대합니다. 그래서 행렬을 Vector (Unboxed.Vector Int)로 구현 된 단일 열로 축소하고 일반적인 Vector Int와 비교했습니다.
벡터 Int는 C++만큼 빨리 정렬하지만 좋은 결과입니다. 그러나 다시 열 매트릭스는 3 배 느립니다. 왜 그런 생각이 드나요? 아래 코드를 찾으십시오. 들어
import Control.Monad.Primitive
import Data.Primitive.ByteArray
import qualified Data.Vector.Generic.Mutable.Base as GM(MVector(..))
import GHC.Prim
data MutableArrayArray s a = MutableArrayArray (MutableArrayArray# s)
instance GM.MVector MutableArrayArray ByteArray where
{-# INLINE basicLength #-}
basicLength (MutableArrayArray marr) = I# (sizeofMutableArrayArray# marr)
{-# INLINE basicUnsafeRead #-}
basicUnsafeRead (MutableArrayArray marr) (I# i) = primitive $ \s -> case readByteArrayArray# marr i s of
(# s1, bar #) -> (# s1, ByteArray bar #)
{-# INLINE basicUnsafeWrite #-}
basicUnsafeWrite (MutableArrayArray marr) (I# i) (ByteArray bar) = primitive $ \s ->
(# writeByteArrayArray# marr i bar s,() #)
: ArrayArray#로 벡터의 벡터를 구현 dfeuer의 조언에 따라
import qualified Data.Vector.Unboxed as UV(Vector, fromList)
import qualified Data.Vector as V(Vector, fromList, modify)
import Criterion.Main(env, bench, nf, defaultMain)
import System.Random(randomIO)
import qualified Data.Vector.Algorithms.Intro as Alg(sort)
randomVector :: Int -> IO (V.Vector Int)
randomVector count = V.fromList <$> mapM (\_ -> randomIO) [1..count]
randomVVector :: Int -> IO (V.Vector (UV.Vector Int))
randomVVector count = V.fromList <$> mapM (\_ -> do
x <- randomIO
return $ UV.fromList [x]) [1..count]
benchSort :: IO()
benchSort = do
let bVVect = env (randomVVector 300000) $ bench "sortVVector" . nf (V.modify Alg.sort)
bVect = env (randomVector 300000) $ bench "sortVector" . nf (V.modify Alg.sort)
defaultMain [bVect, bVVect]
main = benchSort
권투 일 수도 있습니다. C++에서 다차원 배열보다는 개별적으로 할당 된 행에 대한 포인터의 배열로 사용해보십시오 (필자는 여기 있습니다). 나는 다차원 벡터가 지원된다고 생각하지 않습니다, 그래서 이것이 진행된다면 행렬을 크기 n * m의 벡터로 표현하기 위해 약간의 추상화 작업을해야 할 것입니다. – luqui
@luqui를 기반으로 작성된 C++ 다차원 배열은 메모리에서 하나의 연속 블록이지만 여기에는 unboxed 벡터에 대한 참조 벡터가 있습니다. ['array'] (https://hackage.haskell.org/package/array) 또는 ['repa'] (https://hackage.haskell.org/package)를 사용하면 성능이 상당히 향상 될 것으로 기대합니다./repa). – Alec
나는 std :: vector>을 C++로 비교 했으므로 Haskell의 Vector (Vector Int)와 동일하다. 즉 벡터에 대한 포인터 벡터이다. 내 Matrix를 크기가 n * m 인 Vector Int로 패킹하려고 생각했지만 그때 Ints 블록을 한 번에 바꿀 수있는 정렬이 없습니다. 그리고 블록 스왑을 사용했다하더라도 벡터에 대한 포인터를 정렬하는 것보다 효율적이지는 않습니다 (메모리에 너무 많은 쓰기가 있음). –