如何加快與字符串列表的字符串匹配？

我有一個字符串列表。我正在嘗試查找列表中是否有任何這些字符串出現在存儲爲另一個列表的英語字典中。如何加快與字符串列表的字符串匹配？

我觀察它需要找到一個匹配線性增長的時間。然而，當原始列表有幾千個字符串時，它變得太長了。

在我發展的EC2實例，它需要約2秒100串，〜15秒700串，〜100秒5000串，並〜800秒40000串！

有沒有辦法加快速度？提前致謝。

matching_word = "" 
    for w in all_strings: 
      if w in english_dict: 
        if matching_word: # More than one possible word 
          matching_word = matching_word + ", " + w 
        else: 
          matching_word = w

來源

2017-05-24 RebornCodeLover

而不是創建一個字符串，並擴展它，你可以使用列表理解爲是的：

matching_words = [x for x in all_strings if x in english_dict]

現在，您可以使用", ".join(matching_sords)該列表中的字符串。

另一種選擇 - 使用兩套可以使用&操作：

set(all_strings) & set(english_dict)

結果，這裏將是一組與您在兩份名單有項目。

來源

2017-05-24 23:12:03 Dekel

剛上最後一個音符 - 交集會破壞找到的單詞的順序，因此，如果順序很重要，應該使用的第一個例子（列表理解） - 打開字典爲一組，當然後。 – zwer

謝謝Dekel的解決方案。不幸的是，列表理解需要花費相同的時間。但猜猜看，你提供的解決方案超快。 – RebornCodeLover

只要不發生問題的內存，把你的english_dict到set（如果你確實有內存問題，加載你的字典作爲set開始與）：english_dict = set(english_dict)（之前的循環，當然）

這應該顯著加快查找。如果這還不夠，你將不得不求助於創建搜索樹和類似的搜索優化。

來源

2017-05-24 23:12:05 zwer

Zwer。謝謝你的幫助。我可以通過解決方案解決性能問題。現在它是邪惡的快！其實，我的英文字典非常小（僅約15K條目），而最大（全字母）爲3628800。現在，它只需要不到一秒的時間。 – RebornCodeLover

如果'all_strings'是大的，你不需要保存的順序，那麼一定把所有的'all_strings'和'english_dict'成組（甚至更好 - 加載它們作爲一組），並使用'all_strings.intersection（而不是。 – zwer

是的，那就是我最終做的。對於集合（all_strings）＆set（english_dict）中的w是非常快的。 – RebornCodeLover

如何加快與字符串列表的字符串匹配？

回答

相關問題