獲得最大頂部k值

現在我有一個表達式y=0.5*a+0.7*b+0.4*c，其中0<a,b,c<1。假設有一個名單表的a,b,c的值，例如：獲得最大頂部k值

(a, b, c) 
--------------- 
(0.9, 0.4, 0.6) 
(0.5, 0.8, 0.4) 
(0.7, 0.4, 0.8) 
(0.9, 0.2, 0.1) 
...

是否有y發現頂部k=3值的一些快捷方式？

我知道蠻力的方法是枚舉(a,b,c)的每個元組來計算y，然後找到y的k個最大值，但是當元組個數很大時，看起來這個方法並不是很多高效。所以歡迎任何其他方式！

來源

2013-03-26 John Smith

是否有任何關於元組的知識？否則，你需要看看元組，所以我們不能比「蠻力」更好。 – Knoothe 2013-03-26 03:39:48

在你的控制下表中元組的順序是？ – Knoothe 2013-03-26 03:55:02

不需要訂購。 – 2013-03-26 04:24:52

遍歷每個元組。當你閱讀它時，評估它上面的表達式，並隨着時間維護一組前三個值。

試圖比這更聰明的問題是，如果你的元組列表是巨大的，你的程序花費的時間將完全由閱讀它支配，沒有聰明可以讓你擺脫這一點。評估表達式並保持數組與最前三個值保持最新的開銷將是微不足道的，只是讀取部分頂部的幾條指令。（至於爲什麼我建議把你的最高值保存在一個數組中，而不是像堆這樣的東西：當k = 3時，任何使用非平凡數量的指令執行或者需要足夠的內存你並不總是會得到緩存命中，這將超過數據結構提供的任何漸進式收益。）

來源

2013-03-26 03:34:59 jacobm

+1，但堆也可以作爲一個數組來實現，這是通常在知道k時選擇的實現（並且k稍大）。 – Knoothe 2013-03-26 03:39:05

無論你做什麼，你仍然需要遍歷表中的每個元組，所以這將至少是一個O(n)操作。對於只有前3個值，您可以硬編碼大小爲3的數組，並需要if檢查。

因此，考慮到您必須至少遍歷整個表格一次，在這種情況下，您不會比O(n)做得更好。

來源

2013-03-26 03:37:26 Yuushi

使用QuickSelect會給你上平均爲O（n）的複雜性：

假設有N個元件和Y = F（A，B，C），計算長度爲N的一個陣列Y代表每個（a，b，c）（將（a，b，c）的索引添加到Y以及稍後需要的後向引用）。
在Y上使用QuickSelect來獲得第（N-k）階統計量，並獲得結果Y.元素Y [N-k-1]到Y [N-1]將是您的k個最大元素。
將Y [N-k-1]排序爲Y [N-1]以獲得您的結果。

來源

2013-03-26 03:38:20 SidR

對於k = 3這是矯枉過正。當我們可以在O（1）中做的時候，空間的使用是Omega（n）。當然對於更大的k，這可能是適用的。 – Knoothe 2013-03-26 03:41:43

@Knoothe是的，我在推廣k。我同意，對於較小的k值，雅可比解決方案在空間需求較小的情況下可以很好地工作。 – SidR 2013-03-26 03:46:44

獲得最大頂部k值

回答

相關問題