高效的数据结构用于数据匹配

Question

什么是最有效的数据结构来匹配数据？例如，假设我面临以下情况：

<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)时间更长。处理该问题及类似问题的最有效数据结构是什么？

- Bob John

---

你能更具体地说明你想要做什么吗？也就是说，你能明确地列出你想要支持的操作以及它们发生的频率吗？ - templatetypedef

如果你反转你的初始想法，比如说你保持一个有序的销售价格列表，那么你的插入将增加到O(log n)，但你将能够在O(1)时间内“匹配”。 - Alexander

Answer 1

尝试使用从公司名称到按价格排序的销售订单堆的哈希映射。插入销售订单现在是O(log n)，如果购买订单不使用销售订单，则变为常数，或者如果使用，则为O(log n)（您的问题陈述没有指定）。

- jacobm

---

我唯一想引入的调整是在每个符号上对堆的一对哈希映射：一个买堆和一个卖堆。根据问题，他可能希望保留买入挂单，直到有足够的匹配卖出。 - phs

@phs，你介意详细说明一下吗？如果可以的话，也许你能构建一个答案，如果不是太麻烦的话。 - Bob John

请考虑澄清您的问题。 - phs

Answer 2

由于买卖将涉及相同的机构，最好将所有购买（或）销售记录保存在一个映射中，例如所有雅虎记录都保存在一个列表中，该列表被散列到以“雅虎”为键的映射中，这将最小化您的搜索空间。按时间戳、价格、数量排序，然后您可以使用此结构实现所需的函数，并具有最佳成本，在插入时。然后对于任何查询，由于搜索空间最小，所以应该需要更少的时间。

- MissingNumber