大きな２つのファイルから共通するデータを抜き出す方法を教えてください。

質問

２つのテキストファイルから共通する行を高速に抜き出す方法に困っています。

fileA.txtには
139 36.1
139.01 36.1
139.02 36.1
という感じで１万行ぐらいあり、

fileB.txtには
138.8 36.3 0.01
138.81 36.3 NaN
138.82 36.3 0.01
という感じで100万行ぐらいあります。

fileAと１、２欄目が共通する行をfileBから抽出しようと思って以下のawkのスクリプトを書きましたが、処理に異様に時間がかかってしまいました(5時間かけてたった300行ぐらいしか処理できない！)。
もっと高速に処理するための方法をぜひ教えてください。

BEGIN{FS="\t"
while(getline <"fileA.txt" > 0)
form[++n]=$1":"$2
}
{for(i=1;i<=n;i++){
temp=form[i]
if($1":"$2 == temp){print $0}
}
}

回答No.1

spinach-chicken · ベストアンサー

awkは判りませんが、比較する対象を出来る限り減らせば速度はあがるのではないでしょうか？
今のプログラムだとfileAの行数×fileBの行数の比較をしているのでしょうか？

例えば、fileA、fileB共にソートして、

while(fileAの終端まで) {
　　fileAを１行読み込む
　　while(fileBの終端まで) {
　　　　fileBを１行読み込む
　　　　if (fileA = fileB) {出力し、whileを抜ける}
　　　　if (fileA < fileB) {無かったとみなし、whileを抜ける}
　　　　#fileA>fileB 次のfileBの行を読み込む為に戻る
　　}
}

こんなプログラムだと、比較回数はぐっと減ると思います。

お礼

回答ありがとうございます。

たしかに「fileAの行数×fileBの行数の比較」をしていました。
「if (fileA = fileB) {出力し、whileを抜ける}
if (fileA < fileB) {無かったとみなし、whileを抜ける}」
を基本方針にして頑張ってみます。

回答No.6

GuruGuru22

#3です。やってることを簡略化して説明。

たとえば、fileAが
aaa
bbb
ccc
だとして、BEGINの中でその値をkeyにした
連想配列をつくる。

以下の配列ができる↓
form["aaa"] = 1
form["bbb"] = 1
form["ccc"] = 1

続いて、2つめの{}の中で、
連想配列に値があるか確認する。
fileBが
ddd
aaa
aa
とすると、

1行目、
form["ddd"]の値があるか(0より大きいか)
if文でチェックする。
BEGINの処理でform["ddd"]はつくられていない。
form["ddd"] > 0 は成り立たない。

2行目
BEGINの処理でform["aaa"]には1が代入されている。
form["aaa"] > 0 は成り立ち、print文が実行される。

以下続く・・・って感じです。

あ、そういえば、form[$1$2] += 1
+= じゃなくて、= だけの方がよかったですね。

お礼

解説ありがとうございました。
質問のところにわたしが書いたスクリプトよりも早そうな感じですね。

回答No.5

imogasi

＃４です。
データが事務計算の場合と異なるようです。ですから＃４で言っている範疇のことと異なります。当てはまりません。
あとはパターンマッチングや文字列を高速に見つける
KMP法
Boyer-Moore法
などの系統のアルゴリズムや手法を勉強して見てください。

お礼

「KMP法」「Boyer-Moore法」ですね。
ちょっと調べた限りではなかなか難しそうなので、
そのうち挑戦してみます。

回答No.4

imogasi

＞共通する行、の意味が、下記のどちらを言うのか、またそう言うことが大切だと言う認識がないためか、記述がなく曖昧です。
（１）各レコードには、同一かどうかのキー部がある、か
（２）または両ファイルでで完全に一致のものを探す（探してアウトプットするとか）。
その場合は２つのファイルを、それぞれキー部かまたはレコード全体でソートします。大型やオフコンにはソートマージユティリティソフトが必ず有るが。
そして２つのファイルをマッチングのロジックで処理すれば、ソート後のファイルを各々１回読みで処理が終わる。
前段階のソートに時間はかかりますが、あのてこの手を使ってプロが優秀なプログラムを組むものだから、素人は敵わなくて、ソートだけやらす方が、相当速いわけです。
ただパソコンなど視野にもなかった昔のころは大型やオフコンにはソートマージユティリティソフトが必ず付いてきたが、パソコンではこのユティリティの大切さ重要さの
認識が不足していると（特にMS社、個人的に）思う。
ソートと言えばエクセルを使うような始末です。
アクセスのソートの力を借りればなんとかなるかな？
独立したソートの良いプログラムを探してください。

お礼

>記述がなく曖昧です
すみません、言葉足らずでしたね。

fileAは(X、Y)＝(x1,y1),(x2,y1)・・・,(x1,y2)・・・の組のファイルで、
fileBは(X、Y、Z)＝(x1,y1,z11),(x1,y2,z12)・・・の組のファイルです。
fileA,fileB共に、ソートされていません。
fileBの中から、「(xn,ym)の組がfileAの中で定義されているような(x,y,z)」を抜き出したいと思いました。
つまり、fileA=(1,1),(1,2)、fileB=(1,1,a),(2,1,b),(1,2,c),(2,2,d)だとすると、
(1,1,a),(1,2,c)を出力させたいという意味です。

日本の国旗の表面に数字を書いた小さな紙がぎっしり敷き詰めてあって、その中から、赤い丸の部分に載っている紙のみを取り出すというイメージです。fileBが国旗全体、fileAが赤い丸の部分に相当します。赤い丸の位置情報(x,y)は、fileAの中にランダムに並んでいます。

回答No.3

GuruGuru22

私もAWK、あんまり使わないんだけど
はじめに少ない方の値をkeyにして、連想配列つくって、
チェックするって手も。

BEGIN{
　FS = "\t"
　while(getline <"fileA.txt" > 0)form[$1$2] += 1
}

{
if(form[$1$2] > 0)
　　print $1$2
}

お礼

具体的に書いてくださってありがとうございます。

わたしの理解力が及ばず、後半の{　}の意味を捉えるのにもう少し時間がかかりそうです。
良かったら解説をいただけませんか？

回答No.2

ngsvx

レコード件数の多いデータのマッチングは、
事前にソートして、ソートされたデータを前提にしたマッチングをすれば劇的に速くなります。

お礼

アドバイスありがとうございます。

「ソートされたデータを前提にしたマッチング」
力技の前にちょっと細工をすべきなんですね。