続・ファイル内の重複行削除
Posted feedbacks - SQL
使い方：sh uniq.sh input.txt http://unicode.org/にあるUnihan.txtを37個連結した、 約4000万行（約1GB）のファイルの処理に、 Core2 6700, メモリ2GB、MySQL 5.0.45（設定ファイルはmy-huge.cnf）で、 約23分かかりました（消費メモリは約400MB） uniq.shは下に
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | mysql -uroot -N -r test << EOF
DROP TABLE IF EXISTS tmp;
CREATE TABLE tmp (
id INT PRIMARY KEY AUTO_INCREMENT,
line LONGTEXT NOT NULL,
INDEX (line(10))
) CHARACTER SET UTF8;
LOAD DATA LOCAL INFILE "$1" INTO TABLE tmp FIELDS TERMINATED BY '\n' (line);
SELECT line FROM tmp GROUP BY line ORDER BY max(id);
EOF
|
にしお
#3424()
Rating1/1=1.00
「 ファイル内の重複行削除(後優先) 」の続編です。
1行あたり平均60文字のデータが書き込まれた、巨大なファイルがあるとします。どのくらい巨大かというと、積んでいるメモリの10倍程度の容量があります。このファイルから、同じ内容が書かれている行を取り除くプログラムを作ってください。ただし、同じ内容が書かれている行のうち、最後に出現したものを残すものとします。
このサイズのファイルを丸ごとメモリに読み込もうとしてしまうと、 スラッシング - Wikipedia が発生することが予想されます。そこで行単位で読み込もう、というのが前回のお題の趣旨でした。
しかし、与えられたファイルが運悪く「一致する部分のないファイル」である可能性を考えてみましょう。たとえ1行ずつ読んで処理をしたとしても、「重複するかどうかの判定」のために前の行をまるごとメモリに取っておいたのでは、最終的にファイルを丸ごとメモリに乗せることになってしまいます。
こういうデータが入力されうる状況の場合にどう書くか、というお題です。前回のお題の条件3「ファイル全体を一度にメモリに読み込んで処理しないこと」を「たとえすべての行が異なるようなデータであっても、メモリの消費量をファイルサイズのおよそ10%程度に抑えること」と読み替えてください。
追記：「メモリの10倍」はさすがに条件として厳しすぎました。「ファイルのサイズは4ギガバイト未満であり、メモリの消費量をファイルサイズの半分以下に抑えること」と読み替えてください。半分以下に抑えられているのならば題意は満たすものとします。もちろん、頑張ってもっと少ないメモリで動くようにするのもアリです。
[ reply ]