続・ファイル内の重複行削除
Posted feedbacks - Haskell
200K行ごとにチャンクファイルに出力しながら計算をするめるようにした．
このコードではチャンクファイルの行数を200kに固定してあるので，
入力ファイルの大きさによってメモリ使用量を調整できないプログラムになっている．
1行61バイト200K行で12.2MBになる．このプログラムでは1行61バイトのデータなら
200K行以上では常に一定のメモリ使用量になる．したがって，そのメモリ使用量の
2倍以上のファイルを入力しないと，お題の条件「メモリ使用量はファイルサイズの
半分以下」を満たせない．
実際にそのメモリ量はというとなんと880MB！！である．なんじゃこりゃーっ！！
だとすると880 * 2 = 1.76 GB以上のファイルを扱えば，お題を満たすことにはなる．
でも，現実的な時間で処理が終了が終わるとは思えないなぁ．
実際どのくらいの計算時間になるか，小さいサイズの入力データを以下のコードで
生成して実験計測してみた．以下のコードで生成されるデータは1行60カラム幅に
n * 1000000 から 1 までの数字を右寄せ'0'詰めで出力しただけのものである．
このデータでは最悪のケース(重複がないケース)の計測となる．
すべてオンメモリで処理できる場合には，O(n log n)の計算だが，一定量の
Chunkに分解したので，O(n^2)の計算になっていると予想される．
-- テストデータ生成プログラム --
module Main where
import System.Environment
import Text.Printf
m :: Integer
m = 1000000
main :: IO ()
main = do { args <- getArgs
; case args of
[] -> loop m
a:_-> loop (read a * m)
}
loop :: Integer -> IO ()
loop 0 = return ()
loop n = printf "%060d\n" n >> loop (n-1)
----
とりあえず， 1 M 行からは 5 M 行までのケースで計測すると
行数 ファイルサイズ 処理時間
1,000,000 61 MB 242 s
2,000,000 122 MB 802 s
3,000,000 183 MB 1735 s
4,000,000 244 MB 2975 s
5,000,000 305 MB 4381 s
どの場合にも，メモリ使用量は最大 880 MB程度．
でたとえば，30 M 行にすればファイルサイズ 1.83 G で
メモリ使用量の 2倍を超えることになる．プログラムとしては動作できる．
処理時間は最悪の見積りで 170,000 s ≒ 47 時間くらいかなぁ．
丸二日ということになるなぁ．ううむ．ちょっとこのままじゃ
実用にならない．orz
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | module Main where
import qualified Data.Set as S
import System.IO
nl :: Int
nl = 200000
data N = N { pair :: (Int,String) }
instance Eq N where N (_,s) == N (_,t) = s == t
instance Ord N where N (_,s) `compare` N (_,t) = s `compare` t
main :: IO ()
main = do { n <- uniqSplit [] 0 nl
; differs n
; mapM_ cat [0..n]
}
cat :: Int -> IO ()
cat n = readFile (sf n) >>= putStr
uniqSplit :: [String] -> Int -> Int -> IO Int
uniqSplit ls n 0 = writeFile (sf n) (unlines (nset2ls . rls2nset $ ls)) >> uniqSplit [] (n+1) nl
uniqSplit ls n m
= do { eof <- isEOF
; if not eof then getLine >>= \ l -> uniqSplit (l:ls) n (m-1)
else if m == nl then return (n-1)
else writeFile (sf n) (unlines (nset2ls . rls2nset $ ls)) >> return n
}
sf :: Int -> FilePath
sf n = "test/"++show n
nset2ls :: S.Set N -> [String]
nset2ls = map snd . S.toAscList . S.map pair
rls2nset :: [String] -> S.Set N
rls2nset = foldr S.insert S.empty . zipWith ((N .) . (,)) [0,-1..]
uls2nset :: [String] -> S.Set N
uls2nset = S.fromList . zipWith ((N .) . (,)) [0..]
differs :: Int -> IO ()
differs 0 = return ()
differs m = nset m >>= diffs [0..m-1] >> differs (m-1)
nset :: Int -> IO (S.Set N)
nset n = return . uls2nset . lines =<< readFile (sf n)
nline :: Int -> IO [N]
nline n = return . zipWith ((N .) . (,)) [1..] . lines =<< readFile (sf n)
diffs [] _ = return ()
diffs (m:ms) nst
= do { mst <- nset m
; let diff = mst S.\\ nst
; seq (S.size diff) $ writeFile (sf m) (unlines $ nset2ls diff)
; diffs ms nst
}
diffs' [] _ = return ()
diffs' (m:ms) nst
= do { mst <- nset m
; let diff = foldr S.delete mst nst
; seq (S.size diff) $ writeFile (sf m) (unlines $ nset2ls diff)
; diffs' ms nst
}
|
にしお
#3424()
Rating1/1=1.00
「 ファイル内の重複行削除(後優先) 」の続編です。
1行あたり平均60文字のデータが書き込まれた、巨大なファイルがあるとします。どのくらい巨大かというと、積んでいるメモリの10倍程度の容量があります。このファイルから、同じ内容が書かれている行を取り除くプログラムを作ってください。ただし、同じ内容が書かれている行のうち、最後に出現したものを残すものとします。
このサイズのファイルを丸ごとメモリに読み込もうとしてしまうと、 スラッシング - Wikipedia が発生することが予想されます。そこで行単位で読み込もう、というのが前回のお題の趣旨でした。
しかし、与えられたファイルが運悪く「一致する部分のないファイル」である可能性を考えてみましょう。たとえ1行ずつ読んで処理をしたとしても、「重複するかどうかの判定」のために前の行をまるごとメモリに取っておいたのでは、最終的にファイルを丸ごとメモリに乗せることになってしまいます。
こういうデータが入力されうる状況の場合にどう書くか、というお題です。前回のお題の条件3「ファイル全体を一度にメモリに読み込んで処理しないこと」を「たとえすべての行が異なるようなデータであっても、メモリの消費量をファイルサイズのおよそ10%程度に抑えること」と読み替えてください。
追記：「メモリの10倍」はさすがに条件として厳しすぎました。「ファイルのサイズは4ギガバイト未満であり、メモリの消費量をファイルサイズの半分以下に抑えること」と読み替えてください。半分以下に抑えられているのならば題意は満たすものとします。もちろん、頑張ってもっと少ないメモリで動くようにするのもアリです。
[ reply ]