算法骨料點

我有一個表評分算法骨料點

ROW1 =（V1，K1，5）;
row2 =（V2，K2,7）;
row2 =（V1，K1,3）;

我需要聚合的點在AggregateRating表這樣，該表包含

ROW1 =（V1，K1，8）;
row2 =（V2，K2,7）;

我循環，一旦通過評分表創建一個映射[鍵=（Col1中，col2的），值=點] 如果密鑰存在我添加其他的點創建一個新的映射條目。評分表可以包含近100 +條目，所以我想避免多次通過。

這是最有效的方法嗎？

來源

2012-04-07 Oliver

除非'100+'中的'+'不代表數十億，否則你應該堅持一個乾淨而高效的實現，正如你所建議的那樣。 **最**有效的解決方案很少需要。 – Howard 2012-04-07 07:56:45

@你的意思是什麼樣的更有效的解決方案？順便說一句，如果查詢是十億次，它可能是減少其複雜性100倍的重要。 – 2012-04-07 08:00:07

@Boris正是我的意思。「最高效」和「現實世界中的高效」之間存在差異。所有類型的「骯髒」事物，如預取，緩存行的大小......都會起作用。如果你的數據在數十億的範圍內，但不是'100 +'，那很重要。在這個地區，您應該保持解決方案的簡單易懂 - 即對於編碼人員和所有其他人閱讀您的代碼（當然，不會不必要地損害系統性能）有效。 – Howard 2012-04-07 08:05:32

這取決於你用什麼數據結構來存儲地圖。如果使用哈希映射而不是存儲並從中讀取，其複雜度將保持不變（O(1)）。然後，您使用一個查詢進行單個傳遞，並且對於數組中的每個條目至多進行一次插入。這意味着您的算法的整個複雜性將是O(n)。

但是，輸入單獨是O(n)，這意味着你不能做得更好。

請記住，如果您選擇不同的地圖實現方式，例如樹圖，複雜性將會改變，你不會得到最有效的解決方案。

來源

2012-04-07 07:59:10

謝謝你，我正在使用一個HashMap – Oliver 2012-04-10 16:05:32

回答

相關問題