3

約 700,000 行からなる 2 つのテキスト ファイルがあります。

2 番目のファイルは、対応する行の最初のファイルのステートメントに対する応答で構成されます。

一致する行に表示される単語のペアごとに、Fisher's Exact Score を計算する必要があります。

たとえば、ファイルの n 行目が

how are you

と

fine thanx

次に、(how,fine)、(how,thanx)、(are,fine)、(are,thanx)、(you,fine)、(you,thanx) のフィッシャーのスコアを計算する必要があります。

フィッシャーの正確なスコアを計算するために、次のように、コレクション モジュールのカウンターを使用して、各単語の出現回数と、2 つのファイル全体でのそれらの同時出現回数をカウントしました。

with open("finalsrc.txt") as f1, open("finaltgt.txt") as f2:
    for line1, line2 in itertools.izip(f1, f2):
        words1 = list(set(list(find_words(line1))))
        words2 = list(set(list(find_words(line2))))
        counts1.update(words1)
        counts2.update(words2)
        counts_pair.update(list(set(list(itertools.product(words1, words2)))))

次に、scipy モジュールを使用して、各ペアのフィッシャーの正確なスコアを計算します。

from scipy import stats
def calculateFisher(s, t):
    sa = counts1[s]
    ta = counts2[t]
    st = counts_pair[s, t]
    snt = sa - st
    nst = ta - st
    nsnt = n - sa - ta + st
    oddsratio, pvalue = stats.fisher_exact([[st, snt], [nst, nsnt]])
    return pvalue

これは小さなテキスト ファイルでは高速で問題なく動作しますが、私のファイルにはそれぞれ 700,000 行が含まれているため、値をすばやく取得するにはカウンターが大きくなりすぎて、非常に遅くなると思います。

(各センテンスが 10 語であると仮定すると、counts_pair には (10^2)*700,000=70,000,000 エントリが含まれます。)

ファイル内のすべての単語ペアの計算を完了するには、数十日かかります。

これに対する賢明な回避策は何でしょうか?

ご協力をお願いいたします。

4

3 に答える 3

3

クロス積を遅延して生成する必要があるように思えます.7000Counter万の要素があると、多くのRAMが必要になり、事実上すべてのアクセスでキャッシュミスが発生します.

代わりに、「ファイル 1」の単語を対応する「ファイル 2」の単語のセットのリストにマッピングする dict を保存するのはどうでしょうか。

イニシャル：

word_to_sets = collections.defaultdict(list)

交換：

   counts_pair.update(list(set(list(itertools.product(words1, words2)))))

と：

   for w1 in words1:
       word_to_sets[w1].append(words2)

次に、Fisher 関数で、これを置き換えます。

st = counts_pair[s, t]

と：

    st = sum(t in w2set for w2set in word_to_sets.get(s, []))

それは私が得ることができるほど怠惰です-クロス積はまったく計算されません;-)

編集または「リスト1」の単語をそれ自体にマップしますCounter：

イニシャル：

word_to_counter = collections.defaultdict(collections.Counter)

交換：

   counts_pair.update(list(set(list(itertools.product(words1, words2)))))

と：

   for w1 in words1:
       word_to_counter[w1].update(words2)

フィッシャー関数では:

    st = word_to_counter[s][t]
于 2013-10-23T21:34:13.427 に答える
3

ボトルネックは、カウンター以外のデータ構造をどのように操作するかにあると思います。

words1 = list(set(list(find_words(line1))))の結果から、リストからセットからリストを作成しますfind_words。これらの各操作では、すべてのオブジェクトを保持するためにメモリを割り当て、コピーする必要があります。さらに悪いことに、によって返される型にメソッドfind_wordsが含まれていない場合__len__、結果のリストは、反復するにつれて大きくなり、再コピーする必要があります。

カウンターを更新するために必要なのは、反復可能な一意の単語だけであると想定しています。これsetで完全に十分です。

for line1, line2 in itertools.izip(f1, f2):
    words1 = set(find_words(line1)) # words1 now has list of unique words from line1
    words2 = set(find_words(line2)) # words2 now has list of unique words from line2
    counts1.update(words1)          # counts1 increments words from line1 (once per word)
    counts2.update(words2)          # counts2 increments words from line2 (once per word)
    counts_pair.update(itertools.product(words1, words2)

orには繰り返し要素がないため、 にitertools.product渡される の出力を変更する必要がないことに注意してください。そのため、デカルト積には繰り返し要素がありません。counts_pairwords1words2

于 2013-10-23T21:09:04.217 に答える