在python中搜索的速度比嵌套循環更快

我正在嘗試爲數組尋找最低預期成本的最佳順序。在python中搜索的速度比嵌套循環更快

的輸入是：

input = [[390, 185, 624], [686, 351, 947], [276, 1023, 1024], [199, 148, 250]]

這是四種選擇的陣列，第一個數字是一個成本和第二兩個是得到的結果的概率，所述第一（[i][1]），其中是分子和第二個（[i][2]）是分母。

目標是找到這些值/概率對的最優順序，以最小的總成本提供結果。

def answer(input): 

    from itertools import permutations 

    length = len(input) 
    best_total = 999 
    for combination in permutations(input): 
     # print combination 
     total = 0.0 
     for i in range(0, length): 
      current_value = 1.0 
      for j in range(0, i): 
       current_value = current_value * (1.0 - \ 
       (float(combination[j][1])/float(combination[j][2]))) 
      total = total + (float(combination[i][0]) * current_value) 
      if total > best_total: 
       i = length 
     # print total 
     if total <= best_total: 
      best_total = total 
      best_combination = combination 

    answer = map(input.index, best_combination) 

    return answer

運行：

print answer(input)

應給定的輸入返回

[2, 3, 0, 1]

。

這顯然是一個詳盡的搜索，它變得非常緩慢，超過四個選擇。我認爲二叉搜索樹是非常相似的輸入，但我無法弄清楚如何實現它。

我一直在爲此工作四天，似乎無法想出適用於任何輸入的快速版本（假設正向成本和概率）。

這不是作業或任何東西，只是我一直試圖找出一個難題。

來源

2015-05-03 Tim

'minions'從哪裏來？ –

你應該使用python2的xrange，你每次打電話時都會建立列表 –

只是一個簡單的參考：看看[分數]（https://docs.python.org/dev/library/fractions.html）模塊。 –

我會確定原始數組中每個案例的值，存儲這些值，然後對列表進行排序。這是在python 3中，所以我不知道這是否會影響到你。

確定每種情況下的值的原始陣列中，並將它們存儲：

inputA = [[390, 185, 624], [686, 351, 947], [276, 1023, 1024], [199, 148, 250]] 
results = [] 
for idx,val in enumerate(inputA): 
    results.append((val[0]*val[1]/val[2], idx))

排序列表中，提取的位置：

l = lambda t:t[1] 
print(list(map(l,sorted(results,reverse=True))))

遍歷該列表是O(n)，以及排序是O(nlogn)。地圖/列表/打印再次迭代O(n)，因此性能應爲O(nlogn)。

來源

2015-05-03 22:25:57 fdsa

在python中搜索的速度比嵌套循環更快

回答

相關問題