Python：通過避免重複相同的比較來加速我的循環

我正在研究檢查英語單詞之間相似性的算法。Python：通過避免重複相同的比較來加速我的循環

已經定義了一個名爲'相似性'的函數，我檢查整個單詞列表以檢查相似單詞，如果兩個單詞之間的相似性非常高（= 1），算法會將兩個單詞中的一個更改爲另一個。

這裏是邏輯：

list_of_word = [word1, word2, word3, word4]

假設有WORD1和word4之間非常高的相似性。

結果：

list_of_word = [word1, word2, word3, word1]

通常情況下，我只需要循環播放，所採取的措施將是這樣的：

取字1時，比較字詞1，word2和WORD3，word4
取word2，比較word1，word2，word3，word4
取word3，比較word1，word2，word3，word4
把word4，比較word1，word2，word3，word4

但是，有一些無用和重複的操作。例如，我不必一次比較字1和字2。

問題是我必須經過100萬字，它可能需要很多天才能運行。

有什麼建議嗎？

這裏是我使用的那一刻代碼：

from nltk.corpus import wordnet as wn 
from itertools import product 

def similarity(wordx,wordy): 
    sem1, sem2= wn.synsets(wordx), wn.synsets(wordy) 
    maxscore = 0 
    for i,j in list(product(*[sem1,sem2])): 
     score = i.path_similarity(j) # Wu-Palmer Similarity 
     maxscore = score if maxscore < score else maxscore 
    return maxscore 

def group_high_similarity(target_list,tc): 
    result = target_list[:] 
    num_word = len(result) 
    for word in result: 
     wordx = word 
     i = 0 
     while i<len(result): 
      wordy = result[i] 
      value = similarity(wordx,wordy) 
      if value >= tc: 
       result[i] = wordx 
       if wordy != wordx :print wordy+"---> "+ wordx 
      i += 1 
    return result

來源

2016-11-02 David Chan Chi Fung

你可以使用['itertools.combinations（即，2）']（https://docs.python.org/3/library/itertools.html#itertools.combinations）避免比較相同的話多個時間，但還有很多比較...... – Delgan

假設你所有的單詞列表是不重複的（意味着你已經把它們放到集）

恕我直言，你可以在相似應用集合理論數學。

如果A類似B，而X也類似於B，這意味着A也類似於X.

所以，你有一組單詞 [ 「汽車」，「公交車」，「貓」的，「狗」，「鋼筆」，「鴨」，「摩托車」]

在「機動車輛，如果」汽車「類似於」公共汽車「，和」汽車「類似於」摩托車「的相似屬性。「公交車」也類似於「摩托車」，所以你可以看到，你不需要比較所有類似的詞，已被發現，所以之後的「車」相似性比較完成後，它已經帶走 [」汽車「，」公共汽車「，」摩托車「]，」公共汽車「，」摩托車「不需要再次用於比較。

你只剩下[「貓」，「狗」，「鋼筆」，「鴨子」等）。

接下來你需要做的是在這個類似的位置保留一個索引。也許第二次檢查距離得分。

（更新）重要提示：在自然語言，同樣動詞和名詞可以具有多個含義，例如雞可能意味着懦夫。例如。你可能會錯過複合詞，諺語等。例如。 雞出門與出門雞無關; 體外是一個動詞，你不能分裂它們。以上方法非常積極。但是，你需要從某個地方開始，然後逐步添加更多的功能來完善它們。

來源

2016-11-02 10:37:53 mootmoot

只需使用一個嵌套的循環，其中第二指數第一的價值開始：

for i in xrange(len(results)): 
    for j in xrange(i+1, len(results)): 
     # compare element i and j

當然，這優化（將計算除以2）僅適用於您的相似性度量是對稱的（類似於b == b類似於a）。此外，這並不會改變計算複雜度，它仍然是O（n^2）（更準確地說：O（n（n-1）/ 2））。

另一種更復雜的計算計算效率更高的相似性度量的方法是使用二項式展開式（後面我會加入更多）。

你也應該避免while循環，通常它們可以被for循環替換。這是更可靠的（沒有無限循環）可以被解釋者更好地優化。

來源

2016-11-02 09:55:51 gaborous

當前，您會檢查列表中的每個單詞與列表中的每個單詞。這正是。

您可以通過檢查每個單詞後面的每個單詞來減少這一點。它是1 + 2 + ... +（n-1）+ n = n（n-1）/ 2。這將重複您的支票。雖然你的支票需要是對稱的。

from nltk.corpus import wordnet as wn 
from itertools import product 

def similarity(wordx,wordy): 
    sem1, sem2= wn.synsets(wordx), wn.synsets(wordy) 
    maxscore = 0 
    for i,j in list(product(*[sem1,sem2])): 
     score = i.path_similarity(j) # Wu-Palmer Similarity 
     maxscore = score if maxscore < score else maxscore 
    return maxscore 

def group_high_similarity(target_list,tc): 
    result = target_list[:] 
    for x in xrange(0, len(target_ist)): 
     for y in xrange(x + 1, len(target_list)): 
      wordx, wordy = target_list[x], target_list[y] 
      value = similarity(wordx,wordy) 
      if value >= tc: 
       result[x] = wordx 
       if wordy != wordx :print wordy+"---> "+ wordx 
    return result

它可能仍然需要很長時間才能運行，因爲它現在只有大約一半的尺寸。

來源

2016-11-02 10:01:49

Python：通過避免重複相同的比較來加速我的循環

回答

相關問題