fuzzywuzzy文字列マッチングロジックを実行している2m行のPythonでマルチプロセッシングを行う方法は？現在のコードは極端に遅いです

Question

私はPythonを初めて使い、fuzzywuzzyの文字列と一致するのリストに2百万のレコードがあります。 のコードはで動作しており、同様に出力しています。問題は、が極端に遅いです。 3時間で80行しか処理しません。私はそれをに一度に複数の行を処理することによって、速くしたいです。

私は16Gb RAMと1.9GHzデュアルコアCPUを搭載したマシンで実行しています。

以下は実行しているコードです。

d = [] 
n = len(Africa_Company) #original list with 2m string records 
for i in range(1,n): 
    choices = Africa_Company[i+1:n] 
    word = Africa_Company[i] 
    try: 
     output= process.extractOne(str(word), str(choices), score_cutoff=85) 
    except Exception: 
     print (word) #to identify which string is throwing an exception 
    print (i) #to know how many rows are processed, can do without this also 
    if output: 
     d.append({'Company':Africa_Company[i], 
        'NewCompany':output[0], 
        'Score':output[1], 
        'Region':'Africa'}) 
    else: 
     d.append({'Company':Africa_Company[i], 
        'NewCompany':None, 
        'Score':None, 
        'Region':'Africa'}) 


Africa_Corrected = pd.DataFrame(d) #output data in a pandas dataframe 

ありがとうございます！

Answer 1

これはCPUに関連する問題です。並列化することで、2つのコアがあるため、最大で2倍の速度にすることができます。本当にすべきことは、シングルスレッドのパフォーマンスを向上させることです。 Levenshteinの距離はかなり遅いので、速度を上げる機会がたくさんあります。

1. プルーニングを使用します。良い結果をもたらす方法がない場合は、2つの文字列の間で完全なファジー・マッチを実行しようとしないでください。あいまいなマッチの前に、無関係の選択肢をフィルタリングする単純な線形アルゴリズムを見つけようとする。
2. インデックス作成を検討してください。あなたのリストをインデックスに登録する方法はありますか？たとえば、マッチングが単語全体に基づいている場合は、単語を文字列にマップするハッシュマップを作成します。現在の文字列と共通の単語が少なくとも1つある選択肢に対してのみ試行してください。
3. 前処理。あなたが前処理することができるすべての試合の弦で何らかの作業が行われていますか？たとえば、Levenshteinの実装が文字列からセットを作成することから始まる場合は、最初にすべてのセットを作成して、各マッチで何度も同じ作業を繰り返す必要はありません。
4. 使用するアルゴリズムがいくつかありますか？たぶんLevenshteinの距離は、最善のアルゴリズムではありません。
5. 使用しているLevenshtein距離の実装は最適ですか？これはステップ3（前処理）に戻ります。ランタイムをスピードアップするためにできることは他にありますか？

マルチプロセッシングは、（コア数に応じて）一定の係数で高速化されます。インデックスを作成することで、より複雑なクラスに移行することができます。したがって、最初に枝刈りと索引作成に焦点を当て、次に手順3〜5を実行します。これらの手順のうち十分に絞った場合にのみ、マルチプロセッシングを考慮する必要があります。