数据匹配的高效数据结构

匹配数据的最高效数据结构是什么？例如，假设我提出与后续的情景：数据匹配的高效数据结构

<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

数据匹配的高效数据结构

回答

相关问题