algorithm - 找出交易量最高的十大公司

Question

我一直在处理玻璃门的问题，这是我应该去的公司在一次公司采访中提出的问题。问题是：


如果您拥有所有要交易的公司，并且实时输入正在交易的公司，以及交易量是多少，那么如何维护数据，以便您可以进行以下操作：最有效的股票交易量


我想到了相同的以下解决方案。尽管我不确定这是否有效：您如何维护二叉搜索树。在每次插入时，都插入公司名称和交易量。

我的树的基本节点将是：

class Node
{
String key; // company name
int volume; // volume
Node leftNode;
Node rightNode;
}

因此，在每次新插入时，我都会继续插入树中。在最终检索时，我可以运行以下代码，直到全局计数的计数达到10。

traversal(Node a)
{
 if(a!=null)
  {
   traverse(a.getRightNode());
   System.out.println(a.getKey()+a.getValue());
   traverse(a.getLeftNode());
  }
}

您对此解决方案有何看法？

Answer 1

这个问题与另一个question非常相似，但几乎没有任何转折。首先，如果有人问我这个问题，我会问很多问题。我事先知道公司名称吗？公司数目是多少？他们的人数上限吗？您是指时间效率或内存消耗效率，还是两者兼而有之？交易与顶级公司要求的比率是多少？它没有指定，但我将承担大量交易并按需或在一定时间间隔内显示前10名。如果在每次交易到达堆之后请求前10名，即使N大于10，也将毫无用处，整个算法可能会更简单。我还假设时间效率。然后，内存效率受到CPU缓存行为的限制，因此我们无论如何都不要浪费它。

因此，我们将top N存储在某种结构中，这将使我的成员人数最少。这显然是用于大N堆。我可以使用任何堆实现，即使那些IncKey和Merge操作不正确或根本不执行的操作也是如此。我只需要Insert，Peek和Remove操作。数字10很小，我什至不需要堆，特别是在具有良好编译器的编译语言中。我可以使用有序数组或列表，甚至可以使用无序数组。因此，在我将提到堆波纹管的每个地方，都可以使用有序或无序数组或列表。只有顶部N中的较大N才需要堆。

就是这样，我们将存储排名前列的N公司name，并且将其放入堆中时为volume。

然后，我们需要在一些K / V存储中跟踪公司贸易volume。密钥是name。为此，K / V存储可以是hashmap，trie或Judy。如果我们提前知道公司名称，那将会很好。这将使我们能够为hashmap计算完美的哈希或构造最优的trie。否则，如果我们知道公司的上限，那就太好了；否则，请选择合适的哈希长度和存储桶数。否则，我们将不得不进行可调整大小的哈希或使用Judy。没有什么比散列图或Judy更好的动态K / V实现了。所有这些K / V存储都具有O(k)访问复杂性，其中k是密钥的长度，在这种情况下为name。在每个我将在下面提到哈希图的地方，都可以使用Judy或trie。只有在事先知道所有公司名称的情况下，才能使用trie，并且可以定制超快速优化的代码。

因此，我们将存储公司name作为键，并交易volume到目前为止，而flag指示存储在哈希图中的堆中。

所以这里有算法。我们将具有包含堆，堆中的公司数和哈希图的状态。对于每个到达的公司mane和volume，我们将在哈希图中增加volume。然后，如果堆中的公司少于N（10），我们将从哈希表中将此公司name和volume添加到堆中（如果尚不存在）（根据在哈希图中的标记和设置此标志）。否则，如果堆满了并且当前公司不在堆中，我们将窥视堆，并且如果当前公司（在哈希图中）交易的volume少于堆中公司，则我们可以完成此交易并继续下一步。否则，我们必须先更新堆中的公司。虽然位于堆顶部的公司（这意味着volume最少）的堆中的volume小于当前堆中的volume，并且与哈希映射中的值也不同，但我们将更新此volume。可以通过从堆中删除并插入正确的值来完成。然后再次检查堆的顶部，依此类推。注意，我们不需要更新堆中的所有公司，甚至不需要更新所有不是最新的顶级堆公司。很懒。如果当前公司的N仍大于堆顶部，则我们将从堆中删除公司，并插入当前公司并更新哈希映射中的标志。仅此而已。

简要概述：


最小堆存储由volume排序并包含公司name的前volume个公司，或直接索引到哈希图中
堆中的name可能已过期
以公司volume为键和最新的volume以及代表堆成员为值的标志的哈希图
首先在哈希图中更新当前公司volume并记住
如果少于当前交易的公司，则反复更新堆顶
如果仍然少于当前公司，则删除堆顶部，并在堆中添加当前堆顶部


该算法的优势在于，交易volume只能为正数，因此堆中的IncKey只能小于正确的值，并且如果堆的顶部具有所有堆中的最小值，并且仍然小于正确的值并且仍然大于任何正值hasmap中的公司一切都很完美。否则，我们将必须将所有公司存储在堆中，使用最大堆而不是最小堆，实现O(1)并针对所有交易执行此操作，并在哈希图中保留对堆的反向引用，这将使事情变得更加复杂。

O(1)处理新的交易时间复杂度很好。 O(1)是哈希映射查找，Peek是堆中的Insert。堆中的Delete和O(logN)被摊销为O（1）或N，其中O(1)是常量，因此仍然O(N)。堆中的更新数为O(1)，因此为N。当公司数目有上限（开头提到的哈希图大小问题）时，您还可以计算处理时间的上限，因此，如果实施良好，则可以实时考虑。请记住，更简单的解决方案（按有序列表或无序列表，更新所有Top成员等）可以在较小的为10的编译代码中带来更好的性能，尤其是在现代硬件上。

即使没有函数式哈希表，该算法也可以很好地实现，除非没有纯函数哈希表，但是trie应该具有O（1）行为，或者为此存在一些不纯净的模块。例如，使用排序列表作为堆和哈希表字典的Erlang实现。 （我最喜欢的功能堆是配对堆，但对于10个而言，这是过大了。）

-module(top10trade).

-record(top10, {
    n = 0,
    heap = [],
    map = dict:new()
    }).

-define(N, 10).

-export([new/0, trade/2, top/1, apply_list/2]).

new() ->
  #top10{}.

trade({Name, Volume}, #top10{n = N, map = Map} = State)
    % heap is not full
    when N < ?N ->
  case dict:find(Name, Map) of
    % it's already in heap so update hashmap only
    {ok, {V, true}} ->
      State#top10{map = dict:store(Name, {V+Volume, true}, Map)};
    % otherwise insert to heap
    error ->
      State#top10{
        n = N+1,
        heap = insert({Volume, Name}, State#top10.heap),
        map = dict:store(Name, {Volume, true}, Map)
        }
  end;

% heap is full
trade({Name, Volume}, #top10{n = ?N, map = Map} = State) ->
  % look-up in hashmap
  {NewVolume, InHeap} = NewVal = case dict:find(Name, Map) of
    {ok, {V, In}} -> {V+Volume, In};
    error -> {Volume, false}
  end,
  if InHeap ->
      State#top10{map = dict:store(Name, NewVal, Map)};
    true ->  % current company is not in heap so peek in heap and try update
      update(NewVolume, Name, peek(State#top10.heap), State)
  end.

update(Volume, Name, {TopVal, _}, #top10{map = Map} = State)
    % Current Volume is smaller than heap Top so store only in hashmap
    when Volume < TopVal ->
  State#top10{map = dict:store(Name, {Volume, flase}, Map)};
update(Volume, Name, {TopVal, TopName}, #top10{heap = Heap, map = Map} = State) ->
  case dict:fetch(TopName, Map) of
    % heap top is up-to-date and still less than current
    {TopVal, true} ->
      State#top10{
        % store current to heap
        heap = insert({Volume, Name}, delete(Heap)),
        map = dict:store( % update current and former heap top records in hashmap
          Name, {Volume, true},
          dict:store(TopName, {TopVal, false}, Map)
          )
        };
    % heap needs update
    {NewVal, true} ->
      NewHeap = insert({NewVal, TopName}, delete(Heap)),
      update(Volume, Name, peek(NewHeap), State#top10{heap = NewHeap})
  end.

top(#top10{heap = Heap, map = Map}) ->
  % fetch up-to-date volumes from hashmap
  % (in impure language updating heap would be nice)
  [ {Name, element(1, dict:fetch(Name, Map))}
   || {_, Name} <- lists:reverse(to_list(Heap)) ].

apply_list(L, State) ->
  lists:foldl(fun apply/2, State, L).

apply(top, State) ->
  io:format("Top 10: ~p~n", [top(State)]),
  State;
apply({_, _} = T, State) ->
  trade(T, State).

%%%% Heap as ordered list

insert(X, []) -> [X];
insert(X, [H|_] = L) when X < H -> [X|L];
insert(X, [H|T]) -> [H|insert(X, T)].

-compile({inline, [delete/1, peek/1, to_list/1]}).

delete(L) -> tl(L).

peek(L) -> hd(L).

to_list(L) -> L.

每秒执行60万笔交易。我期望每秒C实施数百万，具体取决于公司的数量。更多的公司意味着K / V查找和更新速度变慢。