3

固定形式のデータを含む中程度の大きさのASCIIファイルが2つあります。最初のファイルの行の6つの指定されたフィールドが（指定された許容範囲内で）2番目のファイルの任意の行の6つのフィールドと一致するかどうかをテストし、共通の行を出力して処理を続行する必要があります。

私は現在、Fortranスタイルのラインリーダーを使用してファイル内の各行を分割し、各リストの各要素に対して正しいタイプのリストのリストを生成しています。両方のファイルのリストのリストを、それらを操作しながらメモリに保存しています。

比較する必要のあるフィールドはすべてフロートであり、現在、次のタイプのフローを使用しています。

tol = 0.01
for entry1 in file1List:
    for entry2 in file2List:
        if (abs(entry1[1] - entry2[1]) < tol and abs(entry1[2] - entry2[2]) < tol 
            and abs(entry1[3] - entry2[3]) < tol and abs(entry1[4] - entry2[4]) < tol
            and abs(entry1[5] - entry2[5]) < tol and abs(entry1[6] - entry2[6]) < tol):
            print entry1,entry2

これの実行は、行数が少ないファイルでは問題ありませんが、30000行を超えると、この部分だけの実行は1分以上になります。

はるかに高速な比較方法があるはずだと私はかなり確信していますが、それを見つけるのに苦労しています。助けていただければ幸いです。

4

4 に答える 4

2

要素をnumpy配列として格納できる場合file1list、file2list比較は少し簡単になります（おそらく、より高速になります）。

for entry1 in file1list:
    for entry2 in file2list:
        if(np.all(np.abs(entry1[1:7] - entry2[1:7]) > tol)):
            print entry1,entry2

numpy配列への変換は簡単です。

file1list = [ np.array(entry) for entry in file1list ]

これは、ソートされた場合に少しでも良くなりますfile2list

file2list=sorted(file2list,key=operator.itemgetter(1,2,3,4,5,6))
for entry1 in file1list:
    for entry2 in file2list:
        d=np.abs(entry1[1:7]-entry2[1:7])
        if(np.all(d < tol)):
            print entry1,entry2
        elif(d[0] > tol):
            break
于 2012-07-23T18:16:57.370 に答える
1

現在の処理はですO(n m)。ここnで、はファイル1の行m数とファイル2の行数です。の場合n ~ m ~ 30,000、900,000,000の比較を実行します。当然、1分かかります。

これは、許容範囲によって外れることが許可されているという事実によって少し複雑になります。完全に一致している場合は、ファイルの1つから値の辞書O(m)を作成してから、辞書を作成する時間があります。ハッシュベースの辞書にO(n)は定数時間のルックアップがあるため、ルックアップを実行する時間。

多少似ている可能性の1つは、丸められた値のディクショナリを作成して、内部のものtolが同じ値でキーイングされるようにし、tol一致する可能性のあるものが見つかったときにすべてが内部にあることを確認することです。これを行うには、各エントリを：より少し大きい値に丸めますtol。つまり、の場合tolは1e-3、に丸められたエントリに基づいてキーを入力します1e-2。これがどれほど効果的かは、値との分布によって異なりますtolが、かなり良いはずです。

つまり、次のようなことを行います（テストされていませんが、おそらく機能するはずです）。

 import math
 import operator

 cmp_fields = operator.itemgetter(1, 2, 3, 4, 5, 6)

 # higher-order function to get a key-getting function for a given tolerance
 def key_getter(tol):
     prec = -math.log10(tol) - 1
     def inner(entry):
         return tuple(math.round(x, prec) for x in cmp_fields(entry))
     return inner

 # make the key function we want here
 key_fn = key_getter(tol)

 # build the dictionary of entries from file2: key maps to a list of entries
 file_2_entries = collections.defaultdict(list)
 for entry in file2List:
     file_2_entries[key_fn(entry)].append(entry)

 for entry1 in file1List: # for each entry from file1...
     # check only the potential matches based on rounding from 2
     for entry2 in file_2_entries[key_fn(entry2)]:
         if all(abs(x1 - x2) < tol for x1, x2
                in zip(map(cmp_fields, (entry1, entry2)))):
             print entry1, entry2
于 2012-07-23T18:03:29.507 に答える
1

現在の方法の問題は、最初のファイルのすべての行を2番目のファイルのすべての行と比較していることです。for実行時間を短縮するには、「この反復が何らかの条件に一致する場合、後続のエントリのいずれかができることは不可能であるため、このループから抜け出すことができる」などのロジックを使用して、2番目のループを短絡するメソッドが必要です。マッチ"。

このロジックをサポートするには、最初に両方のリストを並べ替える必要があります。次に例を示します。

from operator import itemgetter
comp_fields = itemgetter(1, 2, 3, 4, 5, 6)
file1List.sort(key=comp_fields)
file2List.sort(key=comp_fields)
for entry1 in file1List:
    for entry2 in file2List:
        if (abs(entry1[1] - entry2[1]) < tol and abs(entry1[2] - entry2[2]) < tol 
            and abs(entry1[3] - entry2[3]) < tol and abs(entry1[4] - entry2[4]) < tol
            and abs(entry1[5] - entry2[5]) < tol and abs(entry1[6] - entry2[6]) < tol):
            print entry1,entry2
        elif entry2[1] - entry1[1] >= tol:
            # we know subsequent lines in file2List can't match due to ordering
            break

これはかなり単純な解決策です。たとえば、1つの可能な改善は、開始点を追跡することです。たとえば、前の反復で一致を見つける前file1Listに2000行を入力した場合、次の反復で次の反復を開始できます。また、最初の列での短絡のみを実行し、後続の列でも短絡させるためのロジックを追加できる場合があります（これは、完全一致を要求する代わりに許容範囲）。file2Listfile1Listfile2List

于 2012-07-23T18:09:29.027 に答える
0

次の値に従って、file1Listとfile2Listの両方を並べ替えることができます。

entry1[1]^2 + entry1[2]^2 + ... + entry1[6]^2

これらは、6空間のベクトルメトリックの2つのリストです。file1List内のベクトルを指定すると、ニュートンラプソン法（または二分法：Python[すでにサポート][1] this）を使用して、同じ長さのベクトルの位置を見つけることができます。

file1Listの次の値と一致するfile2Listの次の値をスキャンする場合は、前方にスキャンするだけで済みます。file2Listの最初の値がtolを超えると、file1Listの特定の値の検索が終了します。

元のJOINユーティリティのアルゴリズムは多かれ少なかれ似ていたと思います。

于 2012-07-23T18:37:01.547 に答える