什麼是最有效的方法來保持（或排序）前10名暢銷產品？

如果您想保留十大暢銷產品並在產品銷售時不斷調整，那麼使用什麼算法是一個好方法？在面試時我很好奇。什麼是最有效的方法來保持（或排序）前10名暢銷產品？

一個很好的例子是亞馬遜如何保持最暢銷的產品排名。

我以爲他們可能會使用排序算法，但考慮到有大量的產品，每次產品銷售的次數發生變化時，排序可能會太慢，因爲排序需要平均O （N log N）。或者他們可能使用鏈表來保持訂單？如果一個產品超過了以前的暢銷產品，就把它放在鏈表的前面。

來源

2017-01-08 mkwon7

這通常是用heap實施的priority queue完成的。

來源

2017-01-08 20:24:11 pscuderi

哦，完全忘了優先級隊列..謝謝！ – mkwon7

二進制堆並不是一個特別好用的數據結構，因爲在堆中找到一個項目以便更新它是很昂貴的。更新（重新調整堆）爲O（log n），但找到該項目爲O（n）。您可以使用單獨的數據結構來跟蹤項目在堆中的位置，但這樣做需要額外的插入和刪除工作。如果您需要經常更改優先級的功能，則最好使用基於指針的堆，例如[配對堆]（https://en.wikipedia.org/wiki/Pairing_heap），或者使用平衡搜索樹某種。 –

您可以將最好的產品保留在平衡的二元搜索樹中（如std::set或std::map）。無論何時銷售產品，您都可以增加銷售數量（產品映射到銷售數量的方式取決於訪問模式，但在大多數情況下，散列表格可以很好地工作），如果它不在樹插入中它（如果它已經存在，可以將它移除並重新插入樹中）。插入後，如果存在多於k（這種情況下爲10），則需要刪除該產品。這種方法的優點是，我們在樹中只保留k最佳項目，因此時間複雜度爲O(log k)，而不是每個更新的O(log n)。

但是，包含最佳k項目的簡單數據結構（如排序向量或排序列表）對於小型k也可以很好地工作。

來源

2017-01-08 20:28:38 kraskevich

什麼是最有效的方法來保持（或排序）前10名暢銷產品？

回答

相關問題