3

合計で約 1,700 万行を含む少数の ASCII ファイルがあり、各行またはほとんどの行に 36 バイトの固定識別子があります。したがって、私のデータは長方形です。固定幅の行がたくさんあります。Haskell を使用して、すべての行を読み取り、正規表現を使用して識別子を抽出し (そこまでは問題ありません)、それらを並べ替えて一意の識別子の数をカウントします (に非常に近いgrep | sort | uniq)。（各ファイルから並列に読み取ることで、すでに並列化しています。）単純な問題のように聞こえますが...

ソート段階の前であっても、この問題からまともなパフォーマンスを引き出すのは難しいと思います。これが私が持っている限りです。 String36 バイトの ASCII ではやり過ぎなので、ByteString. しかし、サイズが 1700 万の (リンクされた) リストは悪い考えのように思えるので、試してみIOVector ByteStringました。しかし、これはかなり遅いようです。ベクトルに何百万もの小さな ByteString を保持しているため、ガベージ コレクションに問題がある+RTS -sと思います。

Repa またはある種の単一の巨大なByteString/ IOVector Char8/whatever を使用して (各行の正確な幅が 36 であることを知っているため)、スレッドごとに 1 つの巨大な長方形配列にデータを格納する必要があると考えていました。これにより、GC の問題が軽減されます。 . ただし、後で行を並べ替える必要はあります。Repa は並べ替えをサポートしていないようで、自分で並べ替えアルゴリズムを作成したくありません。そのため、巨大な長方形の配列を持ちながら、それを並べ替える方法がわかりません。

使用するライブラリ、設定する GC フラグ、またはその他の提案はありますか? マシンには 24 個のコアと 24 GB の RAM があるため、ハードウェアの制約はありません。Haskell に残りたいのは、問題なく動作している関連コード (同じファイルを解析し、要約統計を生成している) がたくさんあり、それを書き直したくはないからです。

4

5 に答える 5

1

ベクトルに何百万もの小さなByteStringを保持しているため、ガベージコレクションが苦しんでいると思います

疑わしい。保持する ByteString は収集しないでください。コードのどこかに過剰なデータ コピーがあるのではないでしょうか?

  • ByteStringヘッダー (8 バイト) + ForeignPtr Word8ref (8 バイト) +Intオフセット (4 バイト) +Int長さ (4 バイト)

  • ForeignPtrヘッダー (8 バイト) + Addr#(8 バイト) + PlainPtrref (8 バイト)です。

  • PlainPtrヘッダー (8 バイト) + MutableByteArray#ref (8 バイト)です。

( https://stackoverflow.com/a/3256825/648955に従って改訂)

全体として、ByteStringオーバーヘッドは少なくとも64 バイトです (一部のフィールドは共有されています)。

独自のデータ管理を作成する: 大きなフラットWord8配列とアドホック オフセット ラッパー

newtype ByteId = ByteId { offset :: Word64 }

Ordインスタンス付き。

オーバーヘッドは、識別子ごとに8 バイトになります。unboxed にオフセットを格納しVectorます。次のように並べ替えます: http://hackage.haskell.org/packages/archive/vector-algorithms/0.5.4.2/doc/html/Data-Vector-Algorithms-Intro.html#v:sort

于 2013-08-22T15:12:04.083 に答える
0

では、どれくらい速く走れるでしょうか？@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

2 倍の時間がかかりますが、それほど悪くはないと思います。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 と 36* 程度の定数 c の O(c*n) アルゴリズムについて話しています。しかし、さらに最適化できると確信しています。

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 を消費します。

十分ですか？

于 2013-08-24T09:58:01.347 に答える
0

ファイル内のデータへの Ptr または大きな ByteString を提供できる、利用可能な mmap の周りにいくつかのラッパーがあります。ByteString は、実際には単なるポインター、オフセット、長さのタプルです。その大きな ByteString を小さなものの束に分割することは、実際には大きなもののサブセットを指す新しいタプルの束を作るだけです。各レコードはファイル内の固定オフセットにあると言うので、ByteString を介して実際にファイルにアクセスすることなく、一連の新しいレコードを作成できるはずですtake。

問題のソート部分については良い提案はありませんが、最初にファイル データのコピーを回避することは良いスタートになるはずです。

于 2013-08-22T15:55:22.093 に答える
0

試してみるとうまくいくはずです。このコードは、1800 万行、600 万個の一意のキーのファイルで、4 ギガ RAM を搭載したデュアルコア ラップトップで 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 キー、次に 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
于 2013-08-23T19:35:44.037 に答える