pythonでfor文の中でfor文を回すときの最適な方法について

Question

pythonについてです

以下のようなコードがあります

collection = nltk.TextCollection(word) 
uniqterms = list(set(collection)) 
for do in word:
    wo=[]
    for term in uniqterms:
        if(collection.tf_idf(term, do) > 0):
           wo.append([term,collection.tf_idf(term, do)])

このときfor文の中でfor文が回っているので
O(n^2)になるはずです

自分が実行したいデータでは、wordとuniqtermsが非常に大きいので
処理時間が膨大になってしまいます

どうにかこの処理を軽くできませんか？
コードの書き方とか、ライブラリとかがあれば教えていただきたいです

Comments

[mattn]

collection.tf_idf が 1 以上を返す条件次第なのでループは変えられないと思います。先に絶対にありえないペアを取り除いておくとループが回る回数を減らす事は出来ます。

[kohekoh]

なるほど、ありがとうございます

Answer 1

from itertools import product
from functools import lru_cache

collection = nltk.TextCollection(word)
uniqterms = list(set(collection))

@lru_cache(maxsize=len(uniqterms))
def costy_eval(term, do):
    return term, collection.tf_idf(term, do)

wo = [*filter(
    lambda *args: args[1] > 0,
    map(costy_eval, *zip(*product(uniqterms, word)))
)]

'''
- 2重ループの代わりにproductとmap、ifの代わりにlambdaとfilterを使用
- collection.tf_idfの呼び出し回数が減らせるかもしれないのでlru_cacheをかます
- listへのappend呼び出し回数を減らすためにイテレータから直接listを生成
- woの順序を問わないのであればconcurrent.futuresで並列化する手もあり
- 追記:costy_evalの引数が2個なのでproductにzipを追加。mapの使い方を間違えてました。
- 追記2:アスタリスクを二つ足したのでもう速くなさそうなコードになりました。
'''

Comments

[kohekoh]

これを入力すると
wo= …　のところで
unhashable type :'list'
のエラーがでてしまいます
なぜでしょうか

[YouheiSakurai]

uniqtermsとwordはどんなデータですか？

[YouheiSakurai]

多分termかdoがlistだからlru_cacheでキャッシュできないんだと思いました。lru_cacheを外してみてください。

[kohekoh]

外しました
そのあと、実行すると
また同じやつがでてきてしまいました
ちなみに、map(costy_eval, product(uniqterms, word)
の部分のcosty_evalは引数を入力して実行でいいんですよね

そのまま実行したら、引数ないですよっていわれたので

[kohekoh]

なるほど…ありがとうございます

Answer 2

遅いなら並列化すればいいじゃん。

雨の中、Cを書かずにPythonで並列計算をする人間がいてもいい。自由とはそういうものだ。

今時のCPUマルチコアだけど、普通に書くと、一つのCPUしか使わないから、全力じゃないですよ。

Comments

[kohekoh]

ありがとうございます
参考にさせていただきます

Answer 3

TF= 文書(doc)における単語の出現頻度なので、０以外を抽出したいだけなら文書(doc)に存在する単語のみ計算すればよいです。（TF-IDF = TF * IDFにて文書に存在しない単語のTFは０になる）
２重ループはそのまま残りますが、計算量は減ります。

import nltk

docs = [
    ['明日','の','天気','は','晴れ'],
    ['今日','の','天気','は','曇'],
    ['昨日','の','天気','は','晴れ']]

collection = nltk.TextCollection(docs) # 文書群に存在する全単語が含まれる
print(set(collection))

print( '全探索')
uniqTerms = list(set(collection))
for doc in docs:
    print( "====================")
    for term in uniqTerms:
        print( "%s : %f" % (term, collection.tf_idf(term, doc)))

print( '文書に存在する単語のみ探索')
for doc in docs:
    print( "====================")
    # １文書に存在する単語のみ計算。存在しない場合は常に０なので。
    for term in set(doc):
        print( "%s : %f" % (term, collection.tf_idf(term, doc)))

さらに、全文書に必ず存在する単語、すなわち、IDFが０になる単語、上記例での「の」「天気」「は」を２番目のtermループから外しておくと、上記の例よりもさらに計算量を減らすことができます。

参考：nltk.TextCollection.tf_idf の使い方

Comments

[kohekoh]

参考にさせていただきます　
ありがとうございます