続・ファイル内の重複行削除 DouKaku?

「ファイル内の重複行削除(後優先) 」の続編です。

1行あたり平均60文字のデータが書き込まれた、巨大なファイルがあるとします。どのくらい巨大かというと、積んでいるメモリの10倍程度の容量があります。このファイルから、同じ内容が書かれている行を取り除くプログラムを作ってください。ただし、同じ内容が書かれている行のうち、最後に出現したものを残すものとします。

このサイズのファイルを丸ごとメモリに読み込もうとしてしまうと、スラッシング - Wikipedia が発生することが予想されます。そこで行単位で読み込もう、というのが前回のお題の趣旨でした。

しかし、与えられたファイルが運悪く「一致する部分のないファイル」である可能性を考えてみましょう。たとえ1行ずつ読んで処理をしたとしても、「重複するかどうかの判定」のために前の行をまるごとメモリに取っておいたのでは、最終的にファイルを丸ごとメモリに乗せることになってしまいます。

こういうデータが入力されうる状況の場合にどう書くか、というお題です。前回のお題の条件3「ファイル全体を一度にメモリに読み込んで処理しないこと」を「たとえすべての行が異なるようなデータであっても、メモリの消費量をファイルサイズのおよそ10%程度に抑えること」と読み替えてください。

追記：「メモリの10倍」はさすがに条件として厳しすぎました。「ファイルのサイズは4ギガバイト未満であり、メモリの消費量をファイルサイズの半分以下に抑えること」と読み替えてください。半分以下に抑えられているのならば題意は満たすものとします。もちろん、頑張ってもっと少ないメモリで動くようにするのもアリです。

python付属ののDBパッケージを使っています。
実際にどれだけのサイズが扱えるのか未確認なので
本当にこれでうまく行くかどうかは分かりません。

import os, sys, dumbdbm, md5

db = dumbdbm.open('tmp')
fp = file(sys.argv[1], 'r')
i = 0
for s in fp:
  k = md5.md5(s).digest()
  if db.has_key(k):
    db[db[k]] = '0'
  db[k] = str(i)
  db[str(i)] = '1'
  i += 1

fp.seek(0)
i = 0
for s in fp:
  if db[str(i)] == '1':
    sys.stdout.write(s)
  i += 1
fp.close()
db.close()

os.remove('tmp.dat')
os.remove('tmp.dir')
os.remove('tmp.bak')

よかった、ちゃんと投稿できたんだ

さすがに「メモリの10倍の量」は
条件として厳しすぎたかなと後悔しています。
まず4ギガを超えるファイルを扱えるのかとか…

というわけで、少し条件をゆるめたいと思います。

題意から離れてしまう突っ込みですが…
大きいファイルを扱うのも大変ですが小さいファイルを扱うのも大変そうです
おそらく数バイトのファイルで追加条件をクリアするのは不可能でしょう

なるほど。ファイルサイズが小さい場合には処理系が食うメモリだけで制限を超えてしまう場合があるわけですね…。題意は1行あたり何バイトあれば重複行の削除ができるかという点なのでそういう定数オーダーの項は無視してもいいことにしましょうか。

これ、ファイルを何回でもスキャンしていいとすれば、だいぶ楽になると思うんですがどうでしょう？
ファイルを何回もスキャンするのはスラッシングとは違う気がするんだけど、どうなんだろうなぁ。

この問題では、「動くはず」と「動いた」は全然違う危険があります。
具体的な検証用のファイル（あるいはその作り方）を示して、
「実際に動作したものを投稿する」というルールが必要なのではないでしょうか。

もちろんそれは禁止されていません。
というより、「ファイルを読むのは1回だけ」とか
「別のファイルに書き出したりしてはいけない」とか
条件をつけてしまうと解けなくなるのではないかと…

「動くつもりで投稿したけど動かない」という事態は今までにも何度も起きましたが、「動かないコードを投稿してそれが発覚するとマイナス評価を受ける」「動かないことを指摘した人はプラス評価を受ける」という形でうまく回っているように思えます。

ルールを増やして縛るよりも、行動の結果に対する評価でフィードバックする方がいいのではないかと思っています。

バッファは1行です。
頭から1行ずつ取り出して、
それ以降の行と比べ、同じ行が無ければ出力します。
注目する行の移動には、seekを使ってます。
計算量の事は聞かないで下さい。
; #3437の事は無かったことにして下さい。

(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)))))))

> 題意は1行あたり何バイトあれば重複行の削除ができるか
ということは、ハッシュに任意の行へのオフセット(ファイルサイズが4GB超なので仮に6バイト)
だけを置いて一行60バイトなので必要なサイズが行あたり6/60で
使用メモリがファイルサイズの10分の1になるというあたりが、想定していた回答なのかな。

全行一回なめて行頭n文字が同じだった行の位置を記録します。
んで巻き戻して読んでいって、さっき記録した疑わしい行がある場合、実際見に行って比較、表示か非表示を決めます。

60メガ100万行のファイルでメモリ30メガ、44秒くらいでした。

def fetch(fin, head)
  cur = fin.pos
  fin.pos = head
  s = fin.gets
  fin.pos = cur
  s
end

def line_with_headpos(fin)
  head = fin.pos
  while line = fin.gets
    yield(line, head)
    head = fin.pos
  end
end

def zoku(fn, n=5)
  open(fn){|fin|
    h = {}

    line_with_headpos(fin){|line, head|
      (h[line[0,n]] ||= []) << head
    }

    fin.rewind

    line_with_headpos(fin){|line, head|
      flag = h[line[0,n]].any?{|ps|
        head < ps && line == fetch(fin, ps)
      }
      print line unless flag
    }
  }
end

zoku(ARGV[0])

6メガ10万行のファイルで実行してみましたが
メモリ使用量が最大時25メガほど、
100メガほどのテンポラリファイルが作成され、
時間は24秒ほどでした。

そういうことは、動くコードで語ってくれと言うのがここの主旨なんじゃないですかね。

あとこのコードだとMD5が衝突したときのことが考慮されてないと思います。

まぁ、僕が出題時に考えていたのはまさにその通りの方法です。

自分のRubyのもそうですが一行のみファイルには負ける、
ということでバッファ一文字で。
がんがんseekします。

#include <stdio.h>
#include <fcntl.h>
#include <sys/types.h>
#include <unistd.h>

char same(int fin, off_t a, off_t b){
    char x[1],y[1];
    char ret;

    while (1){
        lseek(fin, a++, SEEK_SET);
        ret = read(fin, x, 1);

        lseek(fin, b++, SEEK_SET);
        ret += read(fin, y, 1);

        if (ret == 1 || x[0] != y[0]){
            return 0;
        }
        if (ret == 0 || x[0] == '\n'){
            return 1;
        }
    }
}

off_t next_line(int fin, off_t a){
    char x[1];
    char ret;

    lseek(fin, a, SEEK_SET);
    do{
        ret = read(fin, x, 1);
    }while(x[0] != '\n' && ret > 0);

    return ret == 0 ? 0 : lseek(fin, 0, SEEK_CUR);
}

void print(int fin, off_t a){
    char x[1];
    char ret;

    lseek(fin, a, SEEK_SET);
    do{
        ret = read(fin, x, 1);
        if (ret == 0)
            break;

        printf("%c", x[0]);
    }while(x[0] != '\n');
}

void zoku(int fin){
    off_t a=0,b=0;

    do{
        char flag = 1;

        lseek(fin, a, SEEK_SET);
        b = a;
        while ((b = next_line(fin, b))){
            if (same(fin, a, b)){
                flag = 0;
                break;
            }
        }
        if (flag)
            print(fin ,a);

    }while((a = next_line(fin, a)));
}

int main(int argc, char** argv){
    int fin;

    if (argc <= 1)
        return 1;

    fin = open(argv[1], O_RDONLY);

    if (fin < 0)
        return 1;

    zoku(fin);

    return 0;
}

使い方：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は下に

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

この問題は「ファイルの書き換え」ではなく、「標準出力に表示」でもOKですか？

構想は同じですが、なんかすっきりしてないなぁ。
line_with_headposを拝借させていただきました。

def line_with_headpos(fin)
  head = fin.pos
  while line = fin.gets
    yield(line, head)
    head = fin.pos
  end
end

def deldup(file)
  require 'digest/md5'
  
  buf = Hash.new
  open(file, 'r') {|io|
    
    line_with_headpos(io){|line, head|
      (buf[Digest::MD5.digest(line)] ||= []) << head
    }
    
    buf.each_value {|val|
      0.upto(val.size-2) {|i|
        io.pos = i
        idat = io.gets
        i.upto(val.size-1) {|j|
          io.pos = j
          if idat == io.gets
            val[i] = -1
            break
          end
        }
      }
    }
    
    buf.values.flatten.select {|i|
      i != -1
    }.sort.each {|i|
      io.pos = i
      print io.gets
    }
  }
end

deldup(ARGV[0])

一文字バッファに萌えました。

#3427を投稿したものです。

今や同じmd5値を持つデータが生成可能らしいですが
逆に言えば敢えてそういうデータを処理するのでもない限り
特に問題ない、というわけには行きませんか。

もともとこの手のダイジェスト関数は一意とみなせる
と言うところに価値があるわけですから。

md5には原理的な脆弱性が見つかっていますので、
実用的なプログラムでは使わない方がいいでしょう、
とだけは言い添えておきます。

外部コマンドsortを使ってます。
・対象ファイルの各行のハッシュ値をテンポラリファイルに出力
・テンポラリファイルを順ソート後、読み込んで重複行数をカウント
・対象ファイルを再読込、重複行に出会うたびに重複行数カウントをデクリメント
100万行、60MBの数字のみファイルで、実行時間は50秒、メモリ35MB使用です。
マシンはCelleon2.8Ghz、メモリ1GB、Ubuntu7.04。

require 'tempfile'

def make_big_seq_file(cntmax,lthmin,eps)
  cntmax.times {
    s = ""
    (lthmin+rand(eps)).times {
      s << rand(10).to_s
    }
    puts s
  }
end

#make_big_seq_file(10**6,50,20)

def double_line_reject(f)
  h = Hash.new(0)

  temp = Tempfile::new("foobar")
  open(f) {|fin|
    while line = fin.gets
      temp.puts(line.hash)
    end
    temp.close

    f = open("|sort #{temp.path}")
    iold = ""
    f.each {|i|
      i = i.chomp.to_i
      h[i] += 1 if iold == i
      iold = i
    }
    fin.rewind
    while line = fin.gets
      puts line if h[line.hash] < 1
      h[line.hash] -= 1
    end
  }
end

double_line_reject(ARGV[0])

ハッシュテーブルを作成して。
60MB 100万行で メモリ30MB、40秒くらいでした。

#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;
}

> 今や同じmd5値を持つデータが生成可能らしいですが
> 逆に言えば敢えてそういうデータを処理するのでもない限り
> 特に問題ない、というわけには行きませんか。
> もともとこの手のダイジェスト関数は一意とみなせる
> と言うところに価値があるわけですから。

目的によります。そして、今回のお題に対して衝突を無視するのはどっちかというとまずいと思います。
false positiveがごく少数生じても良い場合と、ごくわずかでもその可能性があったら
(それ単独では)使えない場合とがあるわけですよ。

(まあ、お題の元ネタがヒストリファイルの整理ってことで、
打ったはずのコマンドが出現しない確率がわずかにあっても
それほど困らないだろう、という議論は出来ると思いますが。
一般的に「一意とみなせるから良いはずだ」という議論は乱暴だと思います)

> md5には原理的な脆弱性が見つかっていますので、
> 実用的なプログラムでは使わない方がいいでしょう、
> とだけは言い添えておきます。

目的によります。そして、今回のお題のような問題にmd5を使うのは、
衝突へのフォローさえ入れれば、実用的なプログラムに使っても*全く*問題ありません。
(もっとも、今回の問題の場合もっとナイーブなハッシュ関数で良いと思いますが)

「脆弱性」とか「一意とみなせる」とかいう話は、それにくっついてる文脈があるんですよ。
文脈を無視して言葉だけ取り出して議論するのは無意味です。

参加者の総意で評価が形成されていく
というのはいいアイディアですね。

でも、今回は、4G程度が目標だったはずが、
参加者の総意で60M程度に落ち着きそうで、
ちょっと残念な気がします。

まあ、これからに期待ですね。

4Gでも問題なく動くコードを投稿いただければ
少なくとも僕はプラス評価をつけますよ。

ファイルを2回読み込み、1回目でハッシュを使って重複している行を洗い出して、2回目で出力をします。

45万行76M byteのファイルについて、最大ヒープサイズ20Mbyte（-Xmx20m）でOutOfMemory発生しませんでした。全体の使用メモリは30Mちょっと。
実行後のファイルは8万行19Mbyteでした。
使用するメモリ量は2回以上出現する文字列の種類に依存します。

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(); 
      }
   }
}

全部メモリ内で処理しているように見えるのはきのせいですか？お題の真意的に、重複行あるなしにかかわらず処理できないといけないと思うのでこの場合重複なしだったらまずい予感？

早とちりしました。
メモリ使用量についてちゃんと注意書きがありましたね^^;
失礼しました。

専門的な知識は持ち合わせていませんのこれ以上の議論はしませんが
私が知りたいのは、
「このコードにおいて既知の手法を使った人為的な衝突以外の衝突を考慮する必要があるのか」
ただそれだけです。

必要がないのなら、このコードにおいて自前のデータを処理する場合に限れば
衝突を考慮しなくて構わないはずだし、必要があるのならやっぱりmd5は捨てだな、と言うだけです。

他の人がコードを利用したいならその人がどうにかすればいいわけで私は関知しません。

これで何か問題ありますか？

個人的思うのは。
別に性能要件があるわけではないので、
結果を見て4G程度でも耐えられるという根拠になれば
十分ではないかなーなんて思います。

そういった点で言うとコメントで
どのくらいのペースで使用メモリが増えていくのとか
あると良かったのかもしれませんね。
# めんどくさいからきっと僕もしないのだろうけど(笑

Squeak Smalltalk で。

| in memo currPos line out |
in := FileStream oldFileNamed: 'in.txt'.
memo := Dictionary new.

[   currPos := in position.
    (line := in nextLine) notNil
] whileTrue: [memo at: line hash put: currPos].
in reset.

out := FileStream forceNewFileNamed: 'out.txt'.
memo values sort do: [:pos |
    out nextPutAll: (in position: pos; nextLine); cr].
in close. out edit

なぜか言語欄の選択が投稿に反映されなかったようです。お手数ですが、「Other」→「Smalltalk」への差し替えをお願いいたします。

「衝突する可能性がある」という問題はmd5に起因するものではなく
一般的にハッシュ関数すべてにあるものなので
md5で意図的に衝突を起こさせる方法が見つかっているかどうかとは
まったく無関係じゃないですか？

今回の件に関してmd5に非はないですよね？

アルゴリズムがmd5であれSHA-1であれ、
今回のような使い方をすれば
「きわめて低い確率で期待と違う挙動をする」
とうバグを作り込むことになってしまいます。
「これはとても危険なコーディングスタイルだ」
というのがあなたにマイナス評価をつけている人たちの言いたいことなのでは。

にしおさんがフォローしてるけど。

>「このコードにおいて既知の手法を使った人為的な衝突以外の衝突を考慮する必要があるのか」

だから目的によります。ちなみに、セキュリティ用途(一方向関数としてハッシュを使っている場合)でなければ、人為的な衝突か偶然な衝突かは関係ないことの方が多いと思います。今回の問題は情報圧縮のためにハッシュを使ってるので、原因が何であれ衝突は衝突ですね。

今回のようなお題の場合、大抵のプログラマは経験的に衝突しちゃまずいと考えると思うんですが、その判断が間違ってる可能性もあります。ほんとうに衝突を考慮する必要があるのかどうか知りたければ、「今回の問題の要件において、衝突が生じる可能性はxx%であり、コマンドのヒストリファイルという前提で一日yy個のコマンドを叩いているとすれば、衝突が起きるのはzz年に一度の確率である。そんなことを気にするよりもディスクのクラッシュを心配した方がよい。よって今回のお題で衝突を考慮する必要はない。」というような定量的な議論をしてみると良いでしょう。みんなそれが面倒だから安全側に倒れてるだけで、実は意外な結論になるかもしれません。私も見てみたいです。そういう議論。

> これで何か問題ありますか？

これも目的によります:-) あなたが趣味で自分で使うコードを書いているだけで、プログラミングの面白さについてもこれ以上踏み込むつもりがないのなら、何も問題ないと思います。

そうでないなら、一度「ハッシュ」というものについて調べてみるといいですよ。深追いするとすごく面白いです。

DouKaku?

続・ファイル内の重複行削除

Posted feedbacks - Flatten