続・ファイル内の重複行削除
Posted feedbacks - Java
ファイルを2回読み込み、1回目でハッシュを使って重複している行を洗い出して、2回目で出力をします。 45万行76M byteのファイルについて、最大ヒープサイズ20Mbyte（-Xmx20m）でOutOfMemory発生しませんでした。全体の使用メモリは30Mちょっと。 実行後のファイルは8万行19Mbyteでした。 使用するメモリ量は2回以上出現する文字列の種類に依存します。
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 | import java.io.*;
import java.util.*;
public class Uniq {
public static void main(String[] args) throws FileNotFoundException, IOException {
File file = new File(args[0]);
printUniq(file, findDuplications(file));
}
private static Map<String, Integer> findDuplications(File file)
throws FileNotFoundException, IOException {
BufferedReader br = new BufferedReader(new FileReader(file));
try {
Set<Integer> hash = new HashSet<Integer>();
Map<String, Integer> dupStrings = new HashMap<String, Integer>();
String line;
int lineCount = 0;
while ((line = br.readLine()) != null) {
if (!hash.add(line.hashCode())) {
dupStrings.put(line, lineCount);
}
lineCount++;
}
return dupStrings;
} finally {
br.close();
}
}
private static void printUniq(File file, Map<String, Integer> map)
throws FileNotFoundException, IOException {
BufferedReader br = new BufferedReader(new FileReader(file));
try {
String line;
int lineCount = 0;
while ((line = br.readLine()) != null) {
final Integer last = map.get(line);
if (last == null || last.intValue() == lineCount) {
System.out.println(line);
}
lineCount++;
}
} finally {
br.close();
}
}
}
|
にしお
#3424()
Rating1/1=1.00
「 ファイル内の重複行削除(後優先) 」の続編です。
1行あたり平均60文字のデータが書き込まれた、巨大なファイルがあるとします。どのくらい巨大かというと、積んでいるメモリの10倍程度の容量があります。このファイルから、同じ内容が書かれている行を取り除くプログラムを作ってください。ただし、同じ内容が書かれている行のうち、最後に出現したものを残すものとします。
このサイズのファイルを丸ごとメモリに読み込もうとしてしまうと、 スラッシング - Wikipedia が発生することが予想されます。そこで行単位で読み込もう、というのが前回のお題の趣旨でした。
しかし、与えられたファイルが運悪く「一致する部分のないファイル」である可能性を考えてみましょう。たとえ1行ずつ読んで処理をしたとしても、「重複するかどうかの判定」のために前の行をまるごとメモリに取っておいたのでは、最終的にファイルを丸ごとメモリに乗せることになってしまいます。
こういうデータが入力されうる状況の場合にどう書くか、というお題です。前回のお題の条件3「ファイル全体を一度にメモリに読み込んで処理しないこと」を「たとえすべての行が異なるようなデータであっても、メモリの消費量をファイルサイズのおよそ10%程度に抑えること」と読み替えてください。
追記：「メモリの10倍」はさすがに条件として厳しすぎました。「ファイルのサイズは4ギガバイト未満であり、メモリの消費量をファイルサイズの半分以下に抑えること」と読み替えてください。半分以下に抑えられているのならば題意は満たすものとします。もちろん、頑張ってもっと少ないメモリで動くようにするのもアリです。
[ reply ]