python 処理速度を上げるためにこのコードのどこを改善すれば良いでしょうか？

Question

17GBの分かち書き済txtファイルを読み込み、n_gram処理をしているファイルです。処理が非常に遅く心配です。以下のコードを処理速度を上げるために改善できる箇所はあるでしょうか？
教えていただけるととても嬉しいです。

import pandas as pd
import sys
import csv
from collections import Counter

cmd, infile = sys.argv
termFreq = {}

n = 0
for wordArray in open(infile, errors='ignore'):
    wordArray = wordArray.split()
    if wordArray == []:
        continue

    ngram_list = ([(wordArray[i], wordArray[i+1], wordArray[i+2]) for i in range(len(wordArray)-2)])
    

    for n_word in ngram_list:
      if n_word in termFreq:
        termFreq[n_word] += 1
      else:
        termFreq[n_word] = 1
    print(n)
    n += 1





term_list = []
count_list = []
for term, count in termFreq.items():
    term_list.append(term)
    count_list.append(count)

s = pd.DataFrame({
 'Count':count_list,
 'List':term_list
 })

s = s.sort_values('Count', ascending=False)


print(s.shape)

s.to_csv('./effect_3.csv', index=False)

Comments

[meg_]

実行環境を質問に追記してください。（OSとかPCのスペックとか）

[meg_]

to_csv()はデータが大きいと時間がかかります。その前までの処理は遅いですか？具体的に今何分かかっていますか？

[tanukichipon]

コメントしていただきありがとうございます
プロセッサ：2.7 GHz Intel Core i5
メモリ：8 GB 1867 MHz DDR3
OS: MacOS Mojava
4700万行のうち1時間で600万行です。
to_csvより前の処理 for wordArrayの箇所が遅いです。

[meg_]

・皆さんの目に触れるように、回答は「質問に追記」してください。
・メモリに対してファイルサイズが大きいため時間がかかっているかと思われます。（マルチプロセス処理が可能であれば早くなる可能性はあります。メモリ不足なので効果があるかは分かりませんが。）

Answer 1

私の知っている範囲で最速のn-gramの関数と、それを使った処理を挙げておきます。

def ngram(seq, n):
    return zip(*map(islice, tee(seq, n), count(0), repeat(None)))

termFreq =  Counter(chain.from_iterable(ngram(line.rstrip().split(), 3) for line in open(infile, errors='ignore')))

---

100Mぐらいのファイルを作って計測してるソースと結果です。

1. 質問のコード
2. 質問のコードから冗長なループを解消したコード
3. 上のコード

を比べてみました。

import random
from collections import Counter
from datetime import datetime
from itertools import chain, count, islice, repeat, tee

infile = 'a.csv'


def question_code():
    termFreq = {}

    for wordArray in open(infile, errors='ignore'):
        wordArray = wordArray.split()
        if wordArray == []:
            continue

        ngram_list = [(wordArray[i], wordArray[i + 1], wordArray[i + 2]) for i in range(len(wordArray) - 2)]

        for n_word in ngram_list:
            if n_word in termFreq:
                termFreq[n_word] += 1
            else:
                termFreq[n_word] = 1
    return termFreq


def remove_redundant_loop():
    termFreq = {}

    for line in open(infile, errors='ignore'):
        wordArray = line.rstrip().split()
        if wordArray == []:
            continue

        for i in range(len(wordArray) - 2):
            n_word = wordArray[i], wordArray[i + 1], wordArray[i + 2]
            if n_word in termFreq:
                termFreq[n_word] += 1
            else:
                termFreq[n_word] = 1
    return termFreq


def ngram(seq, n):
    return zip(*map(islice, tee(seq, n), count(0), repeat(None)))


def use_itertools():
    return Counter(chain.from_iterable(ngram(line.rstrip().split(), 3) for line in open(infile, errors='ignore')))


if __name__ == '__main__':
    with open(infile, 'w') as w:
        for i in range(100000):
            print(' '.join(map(str, [random.randint(0, 10) for j in range(0, 500)])), file=w)

    start = datetime.now()
    print(question_code()[('0', '0', '0')])
    print(datetime.now() - start)

    start = datetime.now()
    print(remove_redundant_loop()[('0', '0', '0')])
    print(datetime.now() - start)

    start = datetime.now()
    print(use_itertools()[('0', '0', '0')])
    print(datetime.now() - start)

37156
0:00:19.557652
37156
0:00:19.402147
37156
0:00:09.168290

冗長なループが実行速度上は問題にならないことが分かります。

---

実はコードなんかよりもずっとずっと大事なことがあります。
作成している辞書が実メモリを超えないかどうかです。
辞書が実メモリを超えるようならコードをどんなに工夫しても速くなりません。低頻度語を捨てるなどの割り切りや、分割統治が必要になる問題です。

Comments

[tanukichipon]

本当に勉強になります。すごく助かりました。ありがとうざいます。

Answer 2

速度改善には、ループを並列処理させるのが手っ取り早いですが、環境によってできたりできなかったりしますので、アルゴリズム的に冗長な箇所をご指摘します。

ngram_list = ([(wordArray[i], wordArray[i+1], wordArray[i+2]) for i in range(len(wordArray)-2)])


    for n_word in ngram_list:
      if n_word in termFreq:
        termFreq[n_word] += 1
      else:
        termFreq[n_word] = 1

こちらですが、ngram_listを定義している内包表記のループと、そのあとのifでカウントしているループ、同時に処理できるはずです。
ngram_listをそもそも定義する必要がなく、直接
termFreqをカウントアップしていけると思います。

ただし、どの箇所が処理に時間が掛かっているのか、実際にtime関数やtqdmなどを使って計測してみて、その箇所について詰めていくのがよいとおもいます。

---

追記

for i in range(len(wordArray)-2)):
    n_word = wordArray[i], wordArray[i+1], wordArray[i+2]
    if n_word in termFreq:
        termFreq[n_word] += 1
    else:
        termFreq[n_word] = 1

Comments

[tanukichipon]

回答していただきありがとうございます。自分で調べてみたのですが内包リストがうまく記述できませんでした。厚かましいお願いなのですか後学のためにも上記の内包リストの記述仕方を教えていただけないでしょうか。どうかよろしくお願いいたします。

[qax]

内包する必要はありません。
追記のように、ngram_listの定義をやめ、下のループと統合することで、
冗長に2回同じループをしていたのを、1つのループに統合します。

[quickquip]

冗長と言っているのがどういう意味なのか、

>ngram_listをそもそも定義する必要がなく、直接termFreqをカウントアップしていけると思います。
というのがどういう意味でそれでどう速くなるのか、

私にはわかりませんでした。

[qax]

冗長というのは、同じような処理を何回も繰り返しているということです。
ご提示のコードでは、
(1) wordArrayからn_gramを生成(ngram_listの行)
(2) ngram_listを参照してtermFreqをカウントアップ
していますね。
これは、ngram_listを生成する部分をカットして、
(1) wordArrayを参照してtermFreqをカウントアップ
とすれば、同様の処理が実現でき、ngram_listを生成する分の処理がカットされるため、
速度が向上するという考えです。

[tanukichipon]

教えていただきありがとうございます。やはり扱っているファイル自体が大きいためか、そこまで大きく速度改善はしませんでした。しかしながらコードの書き方等大変参考になりました。ありがとうございました。