數據匹配的高效數據結構

匹配數據的最高效數據結構是什麼？例如，假設我提出與後續的情景：數據匹配的高效數據結構

<time available> <buy or sell> <company name> <buy or sell price> <amount to buy or sell>

所以，一個文件可能包含：

0 sell yahoo $100 #1 
2 sell yahoo $14 #1 
2 sell yahoo $28 #1 
.. 95 other yahoo sells <$125 and amount #1 
3 sell yahoo $17 #1 
5 sell yahoo $33 #1 
9 buy yahoo $125 #100

是否有可能這最後買與前100搭配銷售的爲O（n ）時間，其中n = 100，如果購買與其想要購買的公司相對應的最低銷售價格相匹配（或者配對時排在第一位）。

我知道一個天真的解決方案將排序列表，並按順序，但這需要比O（n）時間更長。處理這個問題和類似的問題最有效的數據結構是什麼？

來源

2013-03-24 Bob John

你能對你想要做的更具體嗎？也就是說，你能否明確說明你希望能夠支持哪些操作以及（相對而言）他們發生的頻率？ – templatetypedef 2013-03-24 20:15:47

如果您反轉您的初始想法，假設您保留一個有序的銷售價格清單，您的插入將增加到O（log n），但您可以在O（1） – Alexander 2013-03-24 21:53:14

嘗試使用從公司名稱到銷售訂單堆的哈希映射，按價格排序。現在插入賣出訂單O(log n)，如果買入沒有用完賣出訂單，則買入訂單將變爲常量，如果存在，則輸入O(log n)（您的問題陳述未指定）

來源

2013-03-24 22:17:07 jacobm

處「匹配」。我會介紹的唯一調整是在堆對上的哈希映射：每個符號的購買堆和銷售堆。取決於問題，他可能希望持有待買直到有足夠的匹配銷售出現。 – phs 2013-03-24 22:19:07

@phs，你介意闡述嗎？也許你可以構建一個答案，如果問題不是太多的話。 – 2013-03-24 23:44:52

考慮澄清你的問題。 – phs 2013-03-24 23:53:59

由於買入和賣出將交易與同一組織，最好將所有購買（或）銷售記錄保存在地圖中，就像所有雅虎記錄都保存在以「yahoo」作爲關鍵字的地圖中一樣，這會最大限度地減少搜索空間。在尊重時間戳，價格和數量的情況下進行排序，然後在插入時實施此結構，並以最佳的成本實現您所需的功能。那麼在這之後的任何查詢應該花費更少的時間，因爲搜索空間很小。

來源

2013-03-25 12:49:07 MissingNumber

數據匹配的高效數據結構

回答

相關問題