続・ファイル内の重複行削除
Posted feedbacks - Scheme
バッファは1行です。 頭から1行ずつ取り出して、 それ以降の行と比べ、同じ行が無ければ出力します。 注目する行の移動には、seekを使ってます。 計算量の事は聞かないで下さい。 ; #3437の事は無かったことにして下さい。
1 2 3 4 5 6 7 8 9 10 11 12 13 | (define (main args)
(call-with-input-file (cadr args)
(lambda (port)
(let loop ((next 0))
(port-seek port next)
(let ((buf (read-line port))
(next (port-tell port)))
(unless (eof-object? buf)
(let loop1 ()
(let1 bufn (read-line port)
(cond ((eof-object? bufn) (print buf))
((not (string=? bufn buf)) (loop1)))))
(loop next)))))))
|
にしお
#3424()
Rating1/1=1.00
「 ファイル内の重複行削除(後優先) 」の続編です。
1行あたり平均60文字のデータが書き込まれた、巨大なファイルがあるとします。どのくらい巨大かというと、積んでいるメモリの10倍程度の容量があります。このファイルから、同じ内容が書かれている行を取り除くプログラムを作ってください。ただし、同じ内容が書かれている行のうち、最後に出現したものを残すものとします。
このサイズのファイルを丸ごとメモリに読み込もうとしてしまうと、 スラッシング - Wikipedia が発生することが予想されます。そこで行単位で読み込もう、というのが前回のお題の趣旨でした。
しかし、与えられたファイルが運悪く「一致する部分のないファイル」である可能性を考えてみましょう。たとえ1行ずつ読んで処理をしたとしても、「重複するかどうかの判定」のために前の行をまるごとメモリに取っておいたのでは、最終的にファイルを丸ごとメモリに乗せることになってしまいます。
こういうデータが入力されうる状況の場合にどう書くか、というお題です。前回のお題の条件3「ファイル全体を一度にメモリに読み込んで処理しないこと」を「たとえすべての行が異なるようなデータであっても、メモリの消費量をファイルサイズのおよそ10%程度に抑えること」と読み替えてください。
追記：「メモリの10倍」はさすがに条件として厳しすぎました。「ファイルのサイズは4ギガバイト未満であり、メモリの消費量をファイルサイズの半分以下に抑えること」と読み替えてください。半分以下に抑えられているのならば題意は満たすものとします。もちろん、頑張ってもっと少ないメモリで動くようにするのもアリです。
[ reply ]