平坦化嵌套循環/減少複雜性 - 互補對計數算法

Question

我最近試圖解決一些Python中的任務，並且我發現似乎具有複雜度爲O（n log n）的解決方案，但我相信它對於一些輸入是非常低效的（例如第一個參數是0和pairs是非常長的零列表）。

它也有三個級別for循環。我相信它可以優化，但在現階段，我不能更優化它，我可能只是缺少明顯的東西;）

所以，基本上，問題如下：

考慮的整數列表（values），功能需要返回索引對滿足以下條件的數：

• 讓我們假設單個索引對像(index1, index2)一個元組，
• 然後values[index1] == complementary_diff - values[index2]我真的，

例：如果給定的像作爲[1, 3, -4, 0, -3, 5]和values作爲1complementary_diff列表 ，函數應該返回4（這是索引對以下列表的長度：[(0, 3), (2, 5), (3, 0), (5, 2)]）。

這是我迄今爲止，它應該很好地工作的大部分時間，但 - 正如我所說的 - 在某些情況下，它可能運行非常緩慢，儘管其複雜性的近似爲O（n日誌N ）（看起來像悲觀的複雜性是O（n^2））。

def complementary_pairs_number (complementary_diff, values): 
    value_key = {} # dictionary storing indexes indexed by values 
    for index, item in enumerate(values): 
     try: 
      value_key[item].append(index) 
     except (KeyError,): # the item has not been found in value_key's keys 
      value_key[item] = [index] 
    key_pairs = set() # key pairs are unique by nature 
    for pos_value in value_key: # iterate through keys of value_key dictionary 
     sym_value = complementary_diff - pos_value 
     if sym_value in value_key: # checks if the symmetric value has been found 
      for i1 in value_key[pos_value]: # iterate through pos_values' indexes 
       for i2 in value_key[sym_value]: # as above, through sym_values 
        # add indexes' pairs or ignore if already added to the set 
        key_pairs.add((i1, i2)) 
        key_pairs.add((i2, i1)) 
    return len(key_pairs) 

對於給定的例子，它的行爲像：

>>> complementary_pairs_number(1, [1, 3, -4, 0, -3, 5]) 
4 

如果你看怎麼樣的代碼可以「扁平化」或「簡化」，請讓我知道。

我不確定是否只是檢查complementary_diff == 0等是最好的方法 - 如果您認爲是這樣，請讓我知道。

編輯：我糾正了這個例子（謝謝，unutbu！）。

Answer 1

我認爲這會提高複雜O(n)：

• value_key.setdefault(item,[]).append(index)比使用 的try..except塊更快。它也比使用collections.defaultdict(list)快。 （我用ipython％timeit測試了這個）。
• 原始代碼訪問每個解決方案兩次。對於每個pos_value in value_key，存在與 pos_value相關聯的唯一sym_value。當sym_value也在 value_key中時有解決方案。但是，當我們遍歷value_key中的密鑰時， pos_value最終會被指定爲sym_value的值，其中 會使代碼重複執行它已經完成的計算。所以你可以把 的工作減半，如果你可以停止pos_value等於 舊的sym_value。我用seen = set()實現，保持 跟蹤看到sym_value s。

• 該代碼只關心len(key_pairs)，而不是key_pairs自己。因此，我們可以簡單地跟蹤計數（與num_pairs），而不是跟蹤對（與 set），我們可以簡單地跟蹤計數。因此，我們可以用

  num_pairs += 2*len(value_key[pos_value])*len(value_key[sym_value]) 
  

  或半更換兩個內部的for循環，在「獨特的對角線」的情況下，pos_value == sym_value。

---

def complementary_pairs_number(complementary_diff, values): 
    value_key = {} # dictionary storing indexes indexed by values 
    for index, item in enumerate(values): 
     value_key.setdefault(item,[]).append(index) 
    # print(value_key) 
    num_pairs = 0 
    seen = set() 
    for pos_value in value_key: 
     if pos_value in seen: continue 
     sym_value = complementary_diff - pos_value 
     seen.add(sym_value) 
     if sym_value in value_key: 
      # print(pos_value, sym_value, value_key[pos_value],value_key[sym_value]) 
      n = len(value_key[pos_value])*len(value_key[sym_value]) 
      if pos_value == sym_value: 
       num_pairs += n 
      else: 
       num_pairs += 2*n 
    return num_pairs 

Answer 2

你可能想看看功能編程成語，如降低等

很多時候，嵌套陣列邏輯可以通過使用功能，如降低，地圖簡化，拒絕等

例如（在javascript中）檢出下劃線js。我對Python並不是很聰明，所以我不知道他們有哪些庫可用。

Answer 3

我認爲（部分或全部）這些會有所幫助，但我不確定我會如何證明它。

1）取的值，並將其降低到一組不同的值，記錄每個元件的計數（O（N））

2）分類所得的數組。 3）如果你可以分配很多內存，我想你可能可以用值填充一個稀疏數組 - 如果值的範圍是-100：+100，則分配一個[201]的數組，並且縮減集合中存在的任何值在大型稀疏數組中的值索引處彈出一個值。

4）要檢查它是否符合條件的任何值現在都必須根據x-y關係查看稀疏數組中的索引，然後查看該值是否存在。 5）正如unutbu指出的那樣，它是平凡對稱的，所以如果{a，b}是一對，那麼{b，a}也是如此。

Answer 4

我認爲你可以通過將代數部分從搜索中分離出來並使用更智能的數據結構來改善這一點。

1. 檢查列表並從列表中的每個項目的互補比較中減去。

   resultlist[index] = complementary_diff - originallist[index] 
   

   您可以使用地圖或簡單循環。 - >採取O（n）時間。

2. 查看結果列表中的數字是否存在於原始列表中。

   • 這裏，一個天真的名單，你會真正得到爲O（n^2），因爲你可以結束了搜索在結果列表中每個項目的整個原始清單。

   • 但是，有比這更聰明的方式來組織您的數據。如果您有原始列表分類，你的搜索時間減少了O（nlogn + nlogn）= O（nlogn），nlogn的排序和nlogn每元素的二進制搜索。

   • 如果你想成爲更聰明，你可以讓你列表中的字典（或哈希表），然後這一步變成O（N + N）= O（N），ñ以建立字典並且搜索字典中的每個元素以及 * n。 （*編輯：*既然你不能假設在原始列表中的每個值的唯一性，您可能想保留的每個值多少次出現在原始列表計數）。

本

所以現在你得到O（n）總運行時間。使用

你的例子：

1, [1, 3, -4, 0, -3, 5], 

1. 生成結果列表：

   >>> resultlist 
   [0, -2, 5, 1, 4, -4]. 
   

2. 現在我們搜索：

   • 拉平原始列表轉換成字典。我選擇使用原始列表的指數值作爲這似乎是你感興趣的一個側面數據

     >>> original_table 
     {(1,0), (3,1), (-4,2), (0,3), (-3,4), (5,5)} 
     

   • 對於結果列表中的每個元素，哈希表搜索，使元組：

     (resultlist_index, original_table[resultlist[resultlist_index]]) 
     

     這應該看起來像你有例子的解決方案。

3. 現在您只需找到所得到的元組列表的長度。

現在，這裏的代碼：

example_diff = 1 
example_values = [1, 3, -4, 0, -3, 5] 
example2_diff = 1 
example2_values = [1, 0, 1] 

def complementary_pairs_number(complementary_diff, values): 
    """ 
     Given an integer complement and a list of values count how many pairs 
     of complementary pairs there are in the list. 
    """ 
    print "Input:", complementary_diff, values 
    # Step 1. Result list 
    resultlist = [complementary_diff - value for value in values] 
    print "Result List:", resultlist 

    # Step 2. Flatten into dictionary 
    original_table = {} 
    for original_index in xrange(len(values)): 
     if values[original_index] in original_table: 
      original_table[values[original_index]].append(original_index) 
     else: 
      original_table[values[original_index]] = [original_index] 
    print "Flattened dictionary:", original_table 

    # Step 2.5 Search through dictionary and count up the resulting pairs. 
    pair_count = 0 
    for resultlist_index in xrange(len(resultlist)): 
     if resultlist[resultlist_index] in original_table: 
      pair_count += len(original_table[resultlist[resultlist_index]]) 
    print "Complementary Pair Count:", pair_count 

    # (Optional) Step 2.5 Search through dictionary and create complementary pairs. Adds O(n^2) complexity. 
    pairs = [] 
    for resultlist_index in xrange(len(resultlist)): 
     if resultlist[resultlist_index] in original_table: 
      pairs += [(resultlist_index, original_index) for original_index in 
       original_table[resultlist[resultlist_index]]] 
    print "Complementary Pair Indices:", pairs 

    # Step 3 
    return pair_count 

if __name__ == "__main__": 
    complementary_pairs_number(example_diff, example_values) 
    complementary_pairs_number(example2_diff, example2_values) 

輸出：

$ python complementary.py 
Input: 1 [1, 3, -4, 0, -3, 5] 
Result List: [0, -2, 5, 1, 4, -4] 
Flattened dictionary: {0: 3, 1: 0, 3: 1, 5: 5, -4: 2, -3: 4} 
Complementary Pair Indices: [(0, 3), (2, 5), (3, 0), (5, 2)] 
Input: 1 [1, 0, 1] 
Result List: [0, 1, 0] 
Flattened dictionary: {0: [1], 1: [0, 2]} 
Complementary Pair Count: 4 
Complementary Pair Indices: [(0, 1), (1, 0), (1, 2), (2, 1)] 

謝謝！

Answer 5

改性由@unutbu提供的解決方案：

的問題可以減少到比較這些2點字典：

1. 值

2. 預先計算字典（complementary_diff - 值[ i]）

   def complementary_pairs_number(complementary_diff, values): 
       value_key = {} # dictionary storing indexes indexed by values 
       for index, item in enumerate(values): 
        value_key.setdefault(item,[]).append(index) 
   
       answer_key = {} # dictionary storing indexes indexed by (complementary_diff - values) 
       for index, item in enumerate(values): 
        answer_key.setdefault((complementary_diff-item),[]).append(index) 
   
       num_pairs = 0 
       print(value_key) 
       print(answer_key) 
       for pos_value in value_key: 
        if pos_value in answer_key: 
         num_pairs+=len(value_key[pos_value])*len(answer_key[pos_value]) 
       return num_pairs