続・ファイル内の重複行削除
Posted feedbacks - C++
ハッシュテーブルを作成して。 60MB 100万行で メモリ30MB、40秒くらいでした。
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 68 69 70 71 72 73 74 75 76 | #include <string>
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <numeric>
#include <algorithm>
#include <functional>
using namespace std;
template <int SIZE>
struct StringHashFunc : public binary_function<int, unsigned char, int> {
int operator()(int h, unsigned char c) const {
return (h * 137 + c) % SIZE;
}
};
template <class T, int SIZE>
class StringHashTable {
vector<list<T> > table;
public:
StringHashTable<T, SIZE>() : table(SIZE) {}
list<T> &operator[](const string &s) {
return table[accumulate(s.begin(), s.end(), 0, StringHashFunc<SIZE>())];
}
};
void uniq(const char *fname_in, const char *fname_out) {
StringHashTable<ifstream::off_type, 399989> table;
ifstream fin(fname_in); if (!fin) return;
ofstream fout(fname_out); if (!fout) return;
string s0, s1;
ifstream::pos_type p0, p1;
p0 = 0;
while (getline(fin, s0)) {
list<ifstream::off_type> &q = table[s0];
p1 = fin.tellg();
if (q.empty()) {
q.push_back(p0);
} else {
if (fin.eof()) fin.clear();
list<ifstream::off_type>::iterator ite;
for (ite = q.begin(); ite != q.end(); ++ite) {
fin.seekg(*ite, ios::beg);
getline(fin, s1);
if (s0 == s1) break;
}
if (ite == q.end()) q.push_back(p0);
else *ite = p0;
fin.seekg(p1, ios::beg);
}
p0 = p1;
}
fin.clear();
fin.seekg(0, ios::beg);
p0 = 0;
while (getline(fin, s0)) {
if (fin.eof()) {
fout << s0 << flush;
} else {
list<ifstream::off_type> &q = table[s0];
if (find(q.begin(), q.end(), p0) != q.end()) {
fout << s0 << '\n';
}
}
p0 = fin.tellg();
}
}
int main(void) {
uniq("dup.txt", "uniq.txt");
return 0;
}
|
にしお
#3424()
Rating1/1=1.00
「 ファイル内の重複行削除(後優先) 」の続編です。
1行あたり平均60文字のデータが書き込まれた、巨大なファイルがあるとします。どのくらい巨大かというと、積んでいるメモリの10倍程度の容量があります。このファイルから、同じ内容が書かれている行を取り除くプログラムを作ってください。ただし、同じ内容が書かれている行のうち、最後に出現したものを残すものとします。
このサイズのファイルを丸ごとメモリに読み込もうとしてしまうと、 スラッシング - Wikipedia が発生することが予想されます。そこで行単位で読み込もう、というのが前回のお題の趣旨でした。
しかし、与えられたファイルが運悪く「一致する部分のないファイル」である可能性を考えてみましょう。たとえ1行ずつ読んで処理をしたとしても、「重複するかどうかの判定」のために前の行をまるごとメモリに取っておいたのでは、最終的にファイルを丸ごとメモリに乗せることになってしまいます。
こういうデータが入力されうる状況の場合にどう書くか、というお題です。前回のお題の条件3「ファイル全体を一度にメモリに読み込んで処理しないこと」を「たとえすべての行が異なるようなデータであっても、メモリの消費量をファイルサイズのおよそ10%程度に抑えること」と読み替えてください。
追記：「メモリの10倍」はさすがに条件として厳しすぎました。「ファイルのサイズは4ギガバイト未満であり、メモリの消費量をファイルサイズの半分以下に抑えること」と読み替えてください。半分以下に抑えられているのならば題意は満たすものとします。もちろん、頑張ってもっと少ないメモリで動くようにするのもアリです。
[ reply ]