如何減少縮短Python編程中運行時間的for-loops數量？

-1

我正在從事Python編程。問題是我的代碼太慢，無法在幾天內獲取數據。如何減少縮短Python編程中運行時間的for-loops數量？

我的代碼如下。而詞典的數據就是這樣的; dic [0] = ['happy'，100，[1234，1245，1515，1785，... up to 100]]也就是說，dic [0] [1]表示dic [0] [2 ]。我想要做的是計算DICE係數（詞相似度）（dic [i] [0]代表一個詞（在上面的例子中，'happy'），dic [i] [1]代表dic [i ] [2]（只是len（dic [i] [2]）），dic [i] [2]表示該單詞（dic [i] [0]）出現的行號列表。在語料庫行號）

DICE係數的計算方法以這種方式：兩個單詞（WORD1，單詞2）一起在一個句子/（數字1 + WORD2的總外觀）的數量的總外觀的外觀的數目。

總數據是（很）很大。我的程序已經工作了2天..但沒有結果..我必須儘快使用結果，因爲這項工作的最後期限是下週..

是否有任何替代（好得多）的算法，我可以馬上執行？謝謝。

for j in range(len(dic)): 
      for k in range(len(dic)): 

       score_temp = 0 

       for r in range(len(dic[j][2])): 
        if(dic[j][2][r] in dic[k][2]): 
         score_temp += 1 
       score_final = float(score_temp)/(dic[j][1] + dic[k][1]) 
       dice_cursor.execute('insert into dices values(?,?,?)', (dic[j][0], dic[k][0], score_final))

來源

2014-01-14 GoodGJ

請，至少說明真正的問題。你想在這裏做什麼？ –

@Ashwini Chaudhary我改變了我的帖子。對不起，簡單的解釋。 – GoodGJ

「dic」實際上是一個'dict'，其鍵是從0到'len（dic）'的順序自然數？如果是這樣，爲什麼你不使用'list'？ – abarnert

問題不在於你的算法;這是你的數據結構。

如果我明白你的問題，你必須遍歷所有j, k組合;那根本就沒有辦法。所以最好的算法可能是在dic長度上的二次方。

但是，對於每一對，您都重複地執行一堆線性搜索，對於dic[j][2][r] in dic[k][2]。而那部分是不必要的。如果您只是將這些dic[*][2]列表中的每一個都更改爲集合，則相同的查找會變爲即時。

所以，與其O(N^2 * M^2)，其中N是dic和M長度（平均？）的dic[*][2]長度，它會O(N^2 * M)。仍然緩慢，但更快。

，你建立這個巨大的清單你還沒有告訴我們，所以我不能告訴你如何以不同的方式構建它... ...但通常它只是一個帶有set()開始，並呼籲.add，而不是與[]啓動和呼叫的事.append。

或者，如果你不能改變它的內置的方式，你可以隨時在事後更改：

dic = [[a, b, set(c)] for a, b, c in dic]

我假設在這裏你還不算重複兩次。如果你應該這樣做，我認爲你做錯了 - 你計算j中的重複項，但不包括k中的重複項。但無論如何，你可以通過使用「multiset」類型來解決這個問題。通常是collections.Counter是最簡單的方法。

通過使用集合交集而不是遍歷一個集合來檢查另一集合，也可以使其更簡單（儘管速度稍快）。取而代之的是：

for r in range(len(dic[j][2])): 
    if(dic[j][2][r] in dic[k][2]): 
     temp_score += 1

...這樣做：

temp_score += len(dic[j][2] & dic[k][2])

雖然我們在這，而不是做for j in range(len(dic))，然後使用dic[j]所有的地方，你可以只使用for x in dic並使用x。就像這樣：

for x in dic: 
    for y in dic: 
     score_temp = len(x[2] & y[2]) 
     score_final = float(score_temp)/(x[1] + y[1]) 
     dice_cursor.execute('insert into dices values(?,?,?)', 
          (x[0], y[0], score_final))

或者，更簡潔：

for x, y in itertools.product(dic, dic):

來源

2014-01-14 07:32:28 abarnert

感謝您的回答。我認爲你的解釋會很有幫助。現在，我將停止正在運行的程序，並執行您所解釋的內容。再次感謝。：） – GoodGJ

啊..我能再問一個問題嗎？ len（dic）只有770左右，但dic [i] [2]的平均值大約在10萬以上。那麼，你的方式會更有幫助嗎？ – GoodGJ

@ GoodGJ：絕對！這意味着你從770 * 770 * 100000 * 100000步驟變爲770 * 770 * 100000，這快了10萬倍。 – abarnert

有這麼多的問題與您的代碼：

由於您使用range()遍歷你的字典的鍵，從0開始，看起來，最好使用一個列表，實質上，它只是一個從整數到值的映射，整數是連續的，從0開始。另外，鍵似乎不播放在你的代碼中的其他角色，但要解決您的字典中的條目。這意味着，你不必重複range()。相反，你應該遍歷像這樣（假設你使用一個列表，而不是一個字典）：

for a in the_list: 
    for b in the_list: 
     ... 
     for value in a[2]: 
      if value in b[2]: 
       ...

不過，這僅僅是稍微好一點。如果你可以使用集合而不是列表作爲數據的第三項，那將會好得多。列表上的in運算符的時間複雜度爲O（n）。在集合上它平均只有O（1）。另外，您可以使用標準庫中的正確功能。然後你到達這樣的東西：

from itertools import combinations 

the_list = [ 
    ['happy', 100, set([<100 elements>)]], 
    ['unhappy', 90, set([<90 elements>)]], 
    ['green', 120, set([<120 elements>)]], 
    ['red', 50, set([<50 elements>)]], 
    ... 
] 

for a, b in combinations(the_list, 2): 

    score = len(a[2] & b[2]) 
    dice_cursor.execute('insert into dices values(?,?,?)', (a[0], b[0], score)) 
    dice_cursor.execute('insert into dices values(?,?,?)', (b[0], a[0], score)) 

# now the pairings we didn't generate so far: 
for a in the_list: 
    dice_cursor.execute('insert into dices values(?,?,?)', (a[0], a[0], len(a[2])))

來源

2014-01-14 07:56:07 pillmuncher

如何減少縮短Python編程中運行時間的for-loops數量？

回答

相關問題