超高速比較検索アルゴリズムについて

以下のようなデータがテキストファイルで2つ、1つが4MB程度あります。

216.221.5.0/24
210.51.225.0/24
210.34.240.0/24
・・・・
・・・・

このデータファイルdat1とdat2を比較してdat1からdat2で増えたものとdat1からdat2で無くなったものをそれぞれ、plus.dat、minus.datへと出力したいです。

  dat1          dat2
216.221.5.0/24 216.221.5.0/24
210.51.225.0/24 1.1.1.1/10
ならば
plus.dat minus.dat
1.1.1.1/10 210.51.225.0/24
のようにです。
今はperlでdat1とdat2を比較してandのデータをファイルに出力して、andデータとdat1,dat2と比較して差分を出すというアルゴリズムです。andを取るアルゴリズムです。頭を使ってないので非常に遅いです。これを劇的に早くする方法を教えてください。
while($var1=<READ1>)
{
open(READ2,$re2)||die "can't open file #2";
while($var2=<READ2>)
{
if($var1 eq $var2)
{
print WRITE1 $var1;
close(READ2);
}
}

}

回答の条件
  • 1人2回まで
  • 登録:2008/10/29 11:23:59
  • 終了:2008/10/31 09:00:19

ベストアンサー

id:zzz_1980 No.2

zzz_1980回答回数492ベストアンサー獲得回数642008/10/29 13:16:36

ポイント50pt
#!/bin/sh
sort <dat1.log >_zz_tmp$$
sort <dat2.log >__zz_tmp$$
diff -u _zz_tmp$$ __zz_tmp$$|grep "^[+-][0-9]"|sed -e 's/^./& /'|awk '$1=="+"{print $2 >"plus.dat";}$1=="-"{print $2 >"minus.dat";}'
rm _zz_tmp$$
rm __zz_tmp$$
# for debug
echo "==plus.dat=="
cat plus.dat
echo "==minus.dat=="
cat minus.dat

その他の回答(1件)

id:i_kumagoro No.1

i_kumagoro回答回数170ベストアンサー獲得回数582008/10/29 12:34:38

ポイント20pt

提示された部分のみの代替としては

my %temp;
open(READ2,$re2)||die "can't open file #2";
while($var2=<READ2>)
{
  $temp{$var2} = 1;
}
close(READ2);

while($var1=<READ1>)
{
  if(defined($temp{$var1}))
  {
    print WRITE1 $var1;
  }
}

のようなコードでどうでしょうか。

メモリが許すのであればアルゴリズムを変更し、両方のファイルをハッシュに読み込んで比較したほうが速いと思います。

また、perlで完結する事にこだわるのでなければ、それぞれのファイルをsortしてからdiffをとった結果を加工するのが楽だと思います。

id:zzz_1980 No.2

zzz_1980回答回数492ベストアンサー獲得回数642008/10/29 13:16:36ここでベストアンサー

ポイント50pt
#!/bin/sh
sort <dat1.log >_zz_tmp$$
sort <dat2.log >__zz_tmp$$
diff -u _zz_tmp$$ __zz_tmp$$|grep "^[+-][0-9]"|sed -e 's/^./& /'|awk '$1=="+"{print $2 >"plus.dat";}$1=="-"{print $2 >"minus.dat";}'
rm _zz_tmp$$
rm __zz_tmp$$
# for debug
echo "==plus.dat=="
cat plus.dat
echo "==minus.dat=="
cat minus.dat
  • id:labtest
    追記です。今のアルゴリズムではファイルアクセスがボトルネックになっていると思うのでperlから単純にc言語にしても劇的に早くなるとは思ってません。ただ計算はただ単に比較してるだけなので。
  • id:Mook
    あら、最近コメントしたと思うと消えることがある気がするのですが、
    システムバグでしょうか。

    それはさておき先ほどのコメントの再掲です。

    アルゴリズムのみのコメントですが、
    一行単位の比較でよいのであれば、データをソートして先頭から比較していけば、
    ワンパスの処理で結果を出せると思います。
  • id:zzz_1980
    例の如く「perlを使わずに」書きましたので、最後に見てください。
    一応手元の環境では、数秒のオーダーで走ります。ロジックはソートして比較そのまま。
    algorithm-diff http://search.cpan.org/~tyemq/Algorithm-Diff-1.1902/lib/Algorithm/Diff.pm
    使うといいんでしょうね。
  • id:labtest
    皆さまご回答ありがとうございます。

    sortしてというのは考えにあったのですが「/」が気になってました。
    ただ全てに「/」がついてるから気にする必要はないのですかね。
    あとsortする時間も気になってました。とにかく試してみます。

    >i_kumagoroさん
    ハッシュのアイディアはありませんでした。ありがとうございます。

    >Mookさん
    はい。1行単位の比較です。

    >zzz_1980さん
    いつもお世話になっております。shellつかえるとかなり便利ですね。勉強したくなりました。
  • id:zzz_1980
    私がunixをさわりはじめたときはまだ perl はありませんでしたので(苦笑)
    192.168.0.1/24 と 192.168.0.1/25 では「ネットワーク」が異なりますので違うアドレスとしていいんじゃないのでしょうか。
    CIDR(+ルーター経路テーブル肥大対策) でルーターの中は/25、外にアナウンスするのは /24といった感じで異なったネットマスクを使っている(ように見える)のが普通になりました。
  • id:labtest
    >zzz_1980さん
    dat1.log 、dat2.logと上記のシェルを同じディレクトリに入れてシェルを実行したのですが、

    :No such file or directorytmp5080
    :No such file or directorytmp5080
    diff:__ZZ_tmp5080:No such file or directory
    diff:__ZZ_tmp5080:No such file or directory
    以下rm、catも同様のエラー

    になってしまうのですが。

    >192.168.0.1/24 と 192.168.0.1/25 では「ネットワーク」が異なりますので違うアドレスと
    >していいんじゃないのでしょうか。

    はい。そう考えております。「/」が気になったというのはsortした時に数字ではない文字列である「/」をどう扱うのかよく分からないなぁと思ったのです。
  • id:zzz_1980
    sort の出力ファイル名指定に使っている _zz_tmp$$ と __zz_tmp$$ あたりを確認してみてください。
    最初のは先行する _ がひとつ、次のは _ が二つになっています。
    sh script においては、$$ は実行プロセスのpidになるので、nandakanda >tmp$$ としておくと、
    実行毎に異なった名前のテンポラリファイルを生成することが出来ます。
    今回書いたスクリプトは、テンポラリファイルが二つ必要でしたので、_ と __ で使い分けています。
    これはあまりいいテクニックではないのですが、cygwin 上で使う分には問題ないでしょう。
  • id:labtest
    >zzz_1980さん

    色々調べた結果、改行文字がcygwinとwinで違っていたせいで動かなかったことが分かりました。
    perlでは数時間かかっていたものが数秒で終わりました。まさに劇的に早くなりました。
    本当にいつもありがとうございます。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません