电子交易所前K股算法

Question

您在电子交易所工作。全天，您都会收到报价（交易数据），其中包括产品名称及其股票交易量。例如：{name: vodafone, volume: 20}

如果出现以下情况，您将维护什么数据结构：

• 您必须k在一天结束时按交易量告诉顶级产品。
• 您必须k按全天交易量来告诉热门产品。

您能想到的最有效的解决方案是什么？

我能想到的最有效的解决方案是针对这两种情况使用堆和映射

• 通过减少数量来存储库存的堆（更新 -O(logn)和 getTop k - O(k)）
• 跟踪库存量的地图（更新 - O(1)）

Answer 1

您正在寻找的是一种支持以下查询的地图或字典：

• Add(key, x)：将 x 添加到该键的总数中，如果尚不存在则创建一个新条目。
• GetKLargest(k)：返回 k 个最大条目的键/总计。

假设Q是查询数量，n是不同键的数量。我们应该假设Q远大于n；以纽约证券交易所为例，交易的股票有几千只，每天的交易量有几百万笔。

在第一个场景中，我们假设有大量Add查询后面跟着一个GetKLargest查询。由于查询的成本Add占主导地位，我们可以使用哈希表，这样Add需要 O(1) 时间，然后在一天结束时，我们可以使用大小为k的优先级队列GetKLargest在 O( n log k ) 时间内完成；请注意，我们不需要在 O( n log n ) 时间内对整个键集进行排序只是为了找到k 个最大元素。回答Q个查询的总成本为 O( Q + n log k )。

在第二种情况下，我们假设可能存在大量两种查询。任一查询的成本都可能占主导地位。一个好的选择是使用顺序统计树，它支持AddO(log n ) 时间和GetKLargestO( k log n ) 时间。要在树中按名称查找公司需要一个单独的索引，该索引可以作为哈希表进行维护。最坏情况下，总成本为 O( Qk log n )。

如果k是固定的或者有固定的限制，我们可以做得更好：将总数保存在哈希表中，同时还维护当前前k 个元素的优先级队列。由于维护优先级队列，查询的成本Add现在为 O(log k )；为了有效地做到这一点，我们需要映射还将每个公司的当前索引存储在优先级队列中（如果存在），否则在优先级队列中搜索正确的公司的时间复杂度为 O( k )。由于我们只是输出优先级队列的内容，因此成本GetKLargest为 O( k )。（问题并没有说我们需要按顺序输出它们。如果我们这样做，那么我们可以使用排序数组而不是堆作为优先级队列，并且Add需要 O( k ) 时间。）

在这种情况下，回答Q 个查询的总成本是 O( Qk )。请注意，只有当我们在查询到达之前预先知道可以查询的k的最大值时，这才有效；否则我们不知道优先级队列有多大。