解決高效插入和查找的更優化的方式

下面有一個片段，我有。我要實現addTrade 和printTop解決高效插入和查找的更優化的方式

public static void main(String args[]) throws Exception { 
     MostTraded mt = new MostTraded(); 
     mt.addTrade("IBM", 1000); 
     mt.addTrade("AAPL", 500); 
     mt.addTrade("NFLX", 600); 
     mt.addTrade("AAPL", 900); 

     mt.printTop(2); // AAPL 1400, IBM 1000 
    }

簽名的兩種方法如下：

public void addTrade(String instrument, int volume) 
public void printTop(int count)

參數來printTop意味着打印的許多重交易的股票。例如printTop(2)將意味着前兩名交易股票。增加必須是有效的，這也意味着股票可以被多次交易，在這種情況下需要更新volume。

我有以下想法來解決它，但不知道是否有更好的方法。

要實現高效除用於查找值並添加股票，我可以用一個簡單的HashMap與<stockname, volume> 要做到printTop，我可以用TreeMap，其關鍵是volume和價值是Set<String>跟蹤。很明顯，當我這樣做，並且addTrade，我將不得不修改TreeMap中的條目。

有沒有更好的方法來解決同樣的問題？

來源

2017-10-04 curiousengineer

最佳答案可能取決於預期如何使用解決方案。我認爲如果adds通常在printTops之間發生數千次，那麼最好的解決方案將與printTops之間只有少數幾個Adds不同。 – hatchet

@hatchet，你的假設是正確的，添加的方式比printTop更頻繁。而且這種緩慢是可以接受的。保持你的假設是頭腦，什麼會是更理想的解決方案？ – curiousengineer

特別是如果不同代碼的數量小於PrintTop調用之間預期發生的Add數量，或者通常所需的頂級項目數量很少，那麼我猜測根據需求進行部分排序會更便宜（當調用PrintTop時）如DodgyCodeException所暗示的那樣，而不是維護有序集合。你只會維護HashMap。如果您只是希望PrintTop儘可能最優，並且不關心通過添加分配的維護成本，那就表明不同的答案。 – hatchet

這取決於您要尋找多少優化。如果你正在編寫一個實時交易應用程序，你會希望它儘可能快。維護一組字符串的TreeMap不會很有效。你只想找到N個項目中的top K。因此您需要一個partial sort algorithm。 C++已經有一個標準的部分排序方法;不幸的是，Java沒有。但是您可以在網上找到第三方網站或自己寫一個第三方網站。

來源

2017-10-04 17:38:38 DodgyCodeException

解決高效插入和查找的更優化的方式

回答

相關問題