最快獲得500 000收集的一些成員

Question

可能重複：
construct orderbook from orders example

我想改一下我剛纔的問題construct orderbook from orders example，因爲它非常糟糕的措辭請不要閱讀:)

我收到訂單更新，每個新訂單有+1 orderId：

new orderid = 1 price = 100 quantity = 10 
new orderid = 2 price = 101 quantity = 10 
modify orderid = 1 price = 100 quantity = 8 
new orderid = 3 price = 100 quantity = 7 
new orderid = 4 price = 101 quantity = 3 
delete orderid = 1 
and so on 

在每個順序更新我需要計算簿，delete orderid = 1後，這將是：

price = 100 totalQuantity = 7 
price = 101 totalQuantity = 13 

讓我們假設最初兩個orders和orderbook是空

我想我應該寫一些東西像這樣：

if (order.action = add) 
    orderBook[order.price] += order.quantity 
if (order.action = delete) 
    orderBook[order.price] -= getLastQuantity(order.id) 
if (order.action = modify) 
    orderBook[order.price] += order.quantity - getLastQuantity(order.id) 

大概你能提出不同的實現，但這個是最微不足道的，我認爲 的問題是：如何實現getLastQuantity(int orderId)

簡單的實現：

int[] lastQuantity = new int[100000000]; 

public int getLastQuantity(int orderId) { 
    return lastQuantity[orderId]; 
} 

佔用太多的內存，我甚至不知道有多快是

另一種簡單的實現是使用Dictionary，但我有去逐個我如何可以利用這一點來提高性能比較下令INT鍵？

請注意，一旦訂單被刪除，我不需要記住它的「lastQuantity」。我只需要活動訂單的「最後數量」。

• 訂單總數不超過100 000 000
• 活動訂單是少於500 000

Answer 1

你可以嘗試一個SortedDictionary。這裏是一個很好的文章，關於字典與散列vs散列列表與散列字典集合的性能：http://blog.bodurov.com/Performance-SortedList-SortedDictionary-Dictionary-Hashtable/

實質上，插入操作很昂貴，但檢索不是。

從MSDN：

的SortedDictionary通用類是二叉查找樹 用O（log n）的檢索，其中n是在 字典元件的數量。在這方面，它與SortedList泛型類相似。這兩個類有相似的對象模型，並且都有O（log n）檢索。這兩個類別不同的​​是 內存使用和插入和刪除的速度：

SortedList使用的內存少於SortedDictionary。

SortedDictionary有更快的插入和刪除操作 未排序數據：O（log n），而不是O（n），對於 SortedList。

如果列表從排序數據一次全部填充，則 SortedList比SortedDictionary快。

SortedDictionary通用類是一個二進制搜索 具有O（log n）檢索的樹，其中n是 字典中的元素數。在這方面，它與SortedList泛型類相似。這兩個類有相似的對象模型，並且都有O（log n）檢索。這兩個類別不同的​​是 內存使用和插入和刪除的速度：

SortedList使用的內存少於SortedDictionary。

SortedDictionary有更快的插入和刪除操作 未排序數據：O（log n），而不是O（n），對於 SortedList。

如果列表從排序數據一次全部填充，則 SortedList比SortedDictionary快。

Answer 2

由於沒有確定的大小，您可以使用List而不是數組。它會根據需要自行增長，而不會從一開始就過大或創建太多新陣列。

字典不會那麼糟糕。它可能會比List更浪費一點空間，並且由於碰撞而執行速度會稍微慢一點，但這不會是一個糟糕的解決方案。一個字典在'刪除'操作中也會表現得更好，所以如果你做了很多刪除操作，我會用字典去做。