Haskell에서 사각형 데이터를 저장하고 정렬하는 가장 좋은 방법은 무엇입니까?

Question

나는 총 1700 만 줄을 포함하는 소수의 ASCII 파일을 가지고 있으며, 각/대부분의 줄에는 고정 된 36 바이트 식별자가있다. 그래서 내 데이터는 직사각형입니다. 고정 폭의 행이 많습니다. 하스켈을 사용하여 모든 라인을 읽고 싶습니다. 정규 표현식을 사용하여 식별자를 추출한 다음 정렬하고 고유 식별자 수를 계산합니다 (매우 가까운 숫자는 grep | sort | uniq). (나는 이미 각 파일을 병렬로 읽음으로써 평행을 이루고있다.) 간단한 문제처럼 들리지만, ...

나는 정렬 단계 이전에도이 문제를 해결하기가 어렵다. 여기까지 내가 가진 것입니다. String은 36 바이트 ASCII에 대한 과잉 공격이므로 ByteString을 사용하는 것으로 나타났습니다. 그러나 1,700 만 개 (링크 된) 목록은 나쁜 생각처럼 보였으므로 IOVector ByteString을 시도했습니다. 그러나 이것은 아주 느린 것 같습니다. 나는 벡터에서 작은 ByteStrings 수백만을 유지하면서 쓰레기 수거가 어려움을 겪고 있다고 생각한다 : GC는 코드 (+RTS -s에 따른)보다 적어도 3 배 길다. 프로그램이 계속 실행되면서 더 나빠질 것이라고 생각한다.

나는 어쩌면 바디 수리 또는 하나의 거대한 어떤 종류를 사용해야한다는 생각 ByteString/IOVector Char8/어떤 각 스레드에 대해 하나 개의 거대한 직사각형 배열에 데이터를 저장하기 (I 각 행의 정확한 폭이 36 알고 있기 때문에) 이는 GC 문제를 완화시켜야한다. 그러나 나중에 행을 정렬해야하며 Repa는 정렬을 지원하지 않는 것 같으며 정렬 알고리즘을 직접 작성하고 싶지 않습니다. 그래서 저는 거대한 직사각형 배열을 갖는 방법을 알지 못하고 여전히 그것을 정렬합니다.

사용할 라이브러리, 설정할 GC 플래그 또는 그 밖의 것이 있습니까? 이 머신에는 24 개의 코어와 24GB의 RAM이 있으므로 하드웨어에는 제약이 없습니다. 하스켈에 남아 있기를 원한다. (같은 파일을 파싱하고 요약 통계를 작성하는) 관련 코드가 많아서 잘 작동하고 있으며, 다시 작성하고 싶지 않기 때문이다.

Answer 1

Array 패밀리 유형에는 다차원 배열이 내장되어 있습니다. 색인은 Ix 인스턴스가있는 항목 일 수 있으며 특히 케이스 (Int, Int)에 해당됩니다. 불행히도 정렬을 지원하지 않습니다.

하지만 사용 사례에 따라 분류가 필요합니까? 식별자에서 Int까지의지도가 있다면 숫자를 늘리거나 값 1 인 모든 키를 나중에 선택하면됩니다. 사용 사례에 따라 hashmap을 사용하는 것이 좋습니다. bytestring-trie 패키지를 확인할 수 있습니다.

또 다른 알고리즘은 두 세트 (예 : HashSet), 식별자가 정확히 한 번 표시된 식별자 하나, 식별자가 두 번 이상 표시된 식별자 하나를 전달하는 것이고 목록을 살펴 보는 동안이 세트를 업데이트합니다.

또한 어떻게 파일을 읽습니까? 하나의 큰 ByteString으로 읽고 작은 ByteString 개체를 신중하게 구성하면 실제로는 큰 파일이있는 큰 메모리 덩어리에 대한 포인터가됩니다. GC 문제. 그러나 우리가 당신의 코드를 볼 필요가 있는지 평가하십시오.

Answer 2

은 내가

의심스러운 벡터 작은 ByteStrings의 수백만을 유지으로 가비지 콜렉션이 고통 생각합니다. Retaining ByteStrings은 수집되어서는 안됩니다. 어쩌면 코드의 어딘가에 과도한 데이터 복사가있을 수 있습니까?

• ByteString

  은 헤더 (8 바이트) + ForeignPtr Word8 REF (8 바이트) + Int 오프셋 (4 바이트) + Int 길이 (4 바이트)

• ForeignPtr은 헤더 (8 바이트) + Addr# (8 바이트) + PlainPtr REF (8 바이트)

• PlainPtr는 헤더 (8 바이트) + MutableByteArray# REF (8 바이트)

모두 ( https://stackoverflow.com/a/3256825/648955에 따라 개정) 53,691,363,210

모두, ByteString 오버 헤드는 적어도 64 바이트 (일부 필드가 공유의 날 정정)이다. 큰 평면 Word8 배열 Ord 인스턴스

newtype ByteId = ByteId { offset :: Word64 } 

애드혹 오프셋 래퍼 :

은 자신의 데이터 관리를 작성합니다.

오버 헤드는 식별자 당 8 바이트이됩니다. 박스 안의 Vector에 오프셋을 저장하십시오. http://hackage.haskell.org/packages/archive/vector-algorithms/0.5.4.2/doc/html/Data-Vector-Algorithms-Intro.html#v:sort

Answer 3

파일에있는 Ptrs 또는 큰 ByteString을 제공 할 수있는 mmap 주위에 몇 개의 래퍼가 있습니다. ByteString은 실제로 포인터, offset, length tuple입니다. 그 큰 ByteString을 작은 것들로 나누는 것은 실제로 큰 튜토리얼의 부분 집합을 가리키는 새로운 튜플을 만드는 것입니다. 각 레코드가 파일의 고정 오프셋에 있다고 말하면 실제로 ByteString의 take을 통해 파일에 액세스하지 않고도 새 레코드를 만들 수 있습니다.

문제의 정렬 부분에 대한 좋은 제안은 없지만 처음부터 파일 데이터를 복사하지 않는 것이 좋은 출발점이되어야합니다.

Answer 4

트라이가 작동해야합니다. 이 코드는 4 기가 RAM과 듀얼 코어 노트북 18 만 개 라인, 600 만 고유 키의 파일에 45 분 소요 : 여기

--invoked: test.exe +RTS -K3.9G -c -h 
import qualified Data.ByteString.Char8 as B 
import qualified Data.Trie as T 

file = "data.txt" 
main = ret >>= print 
ret = do -- retreive the data 
    ls <- B.readFile file >>= return.B.lines 
    trie <- return $ tupleUp ls 
    return $ T.size trie 
tupleUp:: [B.ByteString] -> T.Trie Int 
tupleUp l = foldl f T.empty l 
f acc str = case T.lookup str acc 
      of Nothing -> T.insert str 1 acc 
       Just n -> T.adjust (+1) str acc 

다음, (6MM 키를 데이터 파일을 생성하는 데 사용되는 코드입니다 1 개 파일에 3 복사본은 18MM 키를 얻을 수 있습니다 :?.

import qualified Data.ByteString.Char8 as BS 
import System.Random 
import Data.List.Split 

file = "data.txt" 
numLines = 6e6 --17e6 
chunkSize = 36 
charSet = ['a'..'z'] ++ ['A'..'Z'] ++ ['0'..'9'] 

-- generate the file 
gen = do 
    randgen <- getStdGen 
    dat <- return $ t randgen 
    writeFile file (unlines dat) 

t gen = take (ceiling numLines) $ charChunks 
    where 
     charChunks = chunksOf chunkSize chars 
     chars = map (charSet!!) rands 
     rands = randomRs (0,(length charSet) -1) gen 

main = gen 

Answer 5

그래서, 얼마나 빨리 우리가 할 수있는의는 @ JA에 의해 생성 된 파일을 몇 가지 검사를하자의 코드 :

cat data.txt > /dev/null 
    --> 0.17 seconds 

하스켈에서 동일합니까?

import qualified Data.ByteString as B 

f = id 

main = B.readFile "data.txt" >>= return . f >>= B.putStr 

타이밍?

time ./Test > /dev/null 
    --> 0.32 seconds 

두 배의 시간이 걸리지 만 나쁘지는 않습니다. 때문에 엄격한 bytestring을 사용하여 우리는 그것을 1 초 안에 청크하고 싶습니다.

다음으로 Vector을 사용할 수 있습니까? 아니면 너무 느린가요? Vector 개의 덩어리를 만들어 다시 다시 붙이자. 최적화 된 출력을 위해 blaze-builder 패키지를 사용합니다.

import qualified Data.ByteString as B 
import qualified Data.ByteString.Lazy as L 
import qualified Data.Vector as V 
import qualified Blaze.ByteString.Builder as BB 
import Data.Monoid 

recordLen = 36 
lineEndingLen = 2 -- Windows! change to 1 for Unix 
numRecords = (`div` (recordLen + lineEndingLen)) . B.length 

substr idx len = B.take len . B.drop idx 
recordByIdx idx = substr (idx*(recordLen+lineEndingLen)) recordLen 

mkVector :: B.ByteString -> V.Vector (B.ByteString) 
mkVector bs = V.generate (numRecords bs) (\i -> recordByIdx i bs) 

mkBS :: V.Vector (B.ByteString) -> L.ByteString 
mkBS = BB.toLazyByteString . V.foldr foldToBS mempty 
    where foldToBS :: B.ByteString -> BB.Builder -> BB.Builder 
      foldToBS = mappend . BB.fromWrite . BB.writeByteString 

main = B.readFile "data.txt" >>= return . mkBS . mkVector >>= L.putStr 

얼마나 걸리나요?

time ./Test2 > /dev/null 
    --> 1.06 seconds 

전혀 나쁘지 않습니다! 고정 된 청크 위치 대신에 라인을 읽는 정규 표현식을 사용하더라도, 우리는 여전히 심각한 성능 히트없이 Vector에 청크를 넣을 수 있다고 결론을 내릴 수 있습니다.

남은 항목은 무엇입니까? 정렬. 이론적으로 버킷 정렬은 이러한 종류의 문제에 대한 이상적인 알고리즘이어야합니다. 나는 하나를 자신을 구현하는 시도 :

import qualified Data.ByteString as B 
import qualified Data.ByteString.Lazy as L 
import qualified Data.Vector as V 
import qualified Data.Vector.Generic.Mutable as MV 
import qualified Blaze.ByteString.Builder as BB 
import Data.Monoid 
import Control.Monad.ST 
import Control.Monad.Primitive 

recordLen = 36 
lineEndingLen = 2 -- Windows! change to 1 for Unix 
numRecords = (`div` (recordLen + lineEndingLen)) . B.length 

substr idx len = B.take len . B.drop idx 
recordByIdx idx = substr (idx*(recordLen+lineEndingLen)) (recordLen+lineEndingLen) 

mkVector :: B.ByteString -> V.Vector (B.ByteString) 
mkVector bs = V.generate (numRecords bs) (\i -> recordByIdx i bs) 

mkBS :: V.Vector (B.ByteString) -> L.ByteString 
mkBS = BB.toLazyByteString . V.foldr foldToBS mempty 
    where foldToBS :: B.ByteString -> BB.Builder -> BB.Builder 
      foldToBS = mappend . BB.fromWrite . BB.writeByteString 

bucketSort :: Int -> V.Vector B.ByteString -> V.Vector B.ByteString 
bucketSort chunkSize v = runST $ emptyBuckets >>= \bs -> 
           go v bs lastIdx (chunkSize - 1) 
      where lastIdx = V.length v - 1 

       emptyBuckets :: ST s (V.MVector (PrimState (ST s)) [B.ByteString]) 
       emptyBuckets = V.thaw $ V.generate 256 (const []) 

       go :: V.Vector B.ByteString -> 
         V.MVector (PrimState (ST s)) [B.ByteString] -> 
         Int -> Int -> ST s (V.Vector B.ByteString) 
       go v _ _ (-1) = return v 
       go _ buckets (-1) testIdx = do 
        v' <- unbucket buckets 
        bs <- emptyBuckets 
        go v' bs lastIdx (testIdx - 1) 
       go v buckets idx testIdx = do 
        let testChunk = v V.! idx 
         testByte = fromIntegral $ testChunk `B.index` testIdx 
        b <- MV.read buckets testByte 
        MV.write buckets testByte (testChunk:b) 
        go v buckets (idx-1) testIdx 

       unbucket :: V.MVector (PrimState (ST s)) [B.ByteString] -> 
          ST s (V.Vector B.ByteString) 
       unbucket v = do 
          v' <- V.freeze v 
          return . V.fromList . concat . V.toList $ v' 

main = B.readFile "data.txt" >>= return . process >>= L.putStr 
    where process = mkBS . 
         bucketSort (recordLen) . 
         mkVector 

테스트는 아마 허용에 대한 1시 50분 분의 시간을 주었다. 우리는 몇 백만의 범위에서 n을위한 O (c * n) 알고리즘과 36 * 무언가의 상수 c를 이야기하고 있습니다. 그러나 당신이 그것을 더 이상 최적화 할 수 있다고 확신합니다.

vector-algorithms 패키지를 사용해도됩니다. 힙 정렬로 테스트하면 :

import qualified Data.ByteString as B 
import qualified Data.ByteString.Lazy as L 
import qualified Data.Vector as V 
import qualified Blaze.ByteString.Builder as BB 
import Data.Vector.Algorithms.Heap (sort) 
import Data.Monoid 
import Control.Monad.ST 

recordLen = 36 
lineEndingLen = 2 -- Windows! change to 1 for Unix 
numRecords = (`div` (recordLen + lineEndingLen)) . B.length 

substr idx len = B.take len . B.drop idx 
recordByIdx idx = substr (idx*(recordLen+lineEndingLen)) (recordLen+lineEndingLen) 

mkVector :: B.ByteString -> V.Vector (B.ByteString) 
mkVector bs = V.generate (numRecords bs) (\i -> recordByIdx i bs) 

mkBS :: V.Vector (B.ByteString) -> L.ByteString 
mkBS = BB.toLazyByteString . V.foldr foldToBS mempty 
    where foldToBS :: B.ByteString -> BB.Builder -> BB.Builder 
      foldToBS = mappend . BB.fromWrite . BB.writeByteString 

sortIt v = runST $ do 
     mv <- V.thaw v 
     sort mv 
     V.freeze mv 

main = B.readFile "data.txt" >>= return . process >>= L.putStr 
    where process = mkBS . 
         sortIt . 
         mkVector 

이 내 컴퓨터에 대한 1시 20분 분의 일을한다, 그래서 지금 나의 버킷 정렬보다 더 빠르다. 두 가지 최종 솔루션 모두 1 ~ 2GB의 RAM 범위에서 무언가를 소비합니다.

충분하니?