在Haskell中存儲和排序矩形數據的最佳方式是什麼？

Question

我有幾個ASCII文件，總共包含大約1700萬行，每行/最多行中有一個固定的36字節標識符。所以我的數據是矩形的：我有很多固定寬度的行。使用Haskell，我想讀取所有行，使用正則表達式提取標識符（我很好），然後對它們進行排序並計算唯一標識符的數量（非常接近grep | sort | uniq）。 （我已經通過平行讀取每個文件並行化了。）聽起來像是一個簡單的問題，但...

即使在排序階段之前，我也很難獲得體面的表現。這就是我所知道的。 String對於36字節的ASCII是過度的，所以我想通過使用ByteString。但一個1700萬的（鏈接）名單似乎是一個壞主意，所以我嘗試了IOVector ByteString。但這似乎相當緩慢。我相信垃圾收集會受到影響，因爲我保留了數百萬個小型ByteStrings：GC至少需要3倍於代碼（根據+RTS -s），並且我認爲隨着程序繼續運行它只會變得更糟。

我在想，我應該使用Repa或某種單一巨人ByteString/IOVector Char8 /任何（因爲我知道每行的確切寬度是36）將數據存儲在每個線程的一個大型矩形數組中，這應該可以緩解GC問題。不過，我仍然需要對行進行排序，而且Repa似乎不支持排序，我不想自己編寫排序算法。所以我不知道如何有一個巨大的矩形陣列，但仍然可以分類。

建議圖書館使用，GC標誌設置，或其他任何東西？該機器有24個內核和24GB的RAM，所以我不受硬件限制。我想留在Haskell中，因爲我有很多相關的代碼（也是解析相同的文件並生成彙總統計信息）工作正常，我不想重寫它。

Answer 1

Array系列類型內置支持多維數組。索引可以是任何具有Ix實例的內容，特別是對於您的案例(Int, Int)。不幸的是，它也不支持排序。

但是對於你的用例，你真的需要排序嗎？如果您有從標識符到Int的地圖，則可以隨時增加計數，然後選擇值爲1的所有鍵。您可以查看bytestring-trie程序包，但對於您的使用情況，建議使用hashmap。

另一種算法是攜帶兩個集合（例如HashSet），其中一個標識符只出現一次，另一個標識符出現一次以上，並且您在遍歷列表時更新這些集合。

另外，你如何閱讀你的文件：如果你把它看作一個大的ByteString並仔細地構造它的小ByteString對象，它們實際上只是指向大文件的大塊內存，可能會消除你的GC問題。但爲了評估我們需要查看您的代碼。

Answer 2

我相信我保留百萬計的小字節串的矢量

可疑垃圾收集是痛苦。不應收集保留字節串。也許在代碼中的某處存在過多的數據複製？

• 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修訂本）

總而言之，ByteString開銷至少64字節（指正，一些字段共享）。

寫自己的數據管理：大平Word8陣列和即席偏移包裝

newtype ByteId = ByteId { offset :: Word64 } 

與Ord實例。

開銷將是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

有一些圍繞mmap可用的包裝，可以讓你Ptrs到您的文件中的數據或一個大的ByteString。 ByteString實際上只是一個指針，偏移量和長度元組;把那個大的ByteString分成一堆小的實際上就是製造一大堆指向大的子集的新元組。既然你說每個記錄在文件中的固定偏移量，你應該可以創建一堆新的文件，而不用通過ByteString的take實際訪問任何文件。

對於問題的排序部分，我沒有任何好的建議，但是避免首先複製文件數據應該是一個好的開始。

Answer 4

一個特里應該工作。此代碼需要45分鐘對18萬線，6000000個唯一的密鑰文件，在雙核筆記本電腦4演出RAM：

--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 

下面是用於生成數據文件（6毫米的鍵碼，然後3份至1個文件，以獲得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 

的同樣在Haskell？

import qualified Data.ByteString as B 

f = id 

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

時間？

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

花了兩倍的時間，但我想這不是太糟糕。使用嚴格的字節串，因爲 我們想要在一秒鐘內完成。

接下來，我們可以使用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秒的時間，這可能是可以接受的。我們正在討論一個O（c * n）算法，其中n是在幾百萬的範圍內，而一個常數c是36 *的東西。但我相信你可以進一步優化它。可以使用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-1.2 GB RAM的範圍。

夠好嗎？