找出交易量最高的前10家公司

Question

如果你有所有交易的公司，并且有关于哪个公司正在交易以及交易量是多少的实时输入，你如何维护这些数据，以便你可以最有效地执行按股票交易量计算的前10个交易最多的公司的操作

我想到了同样的解决办法。虽然我不确定这是否是一个有效的一个或不：你如何维护一个二分搜索树。每插入一次，您都要插入公司名称和该公司的股票交易量。

我的树的基本节点是：

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

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

你对这个解决方案有什么看法？

Answer 1

这个问题和另一个问题很相似，但没有什么变化。首先，如果有人问我这个问题，我会问很多问题。我是否事先知道公司名称？公司数目是多少？他们的数量有上限吗？你指的是时间效率还是内存消耗效率，或者两者兼而有之？行业和顶级公司的要求比例是多少？它没有指定，但我会假设高交易量，并显示前10名的需求或在一些时间间隔。如果在每个交易到达后请求top10，堆将是无用的，即使n大于10，整个算法将会更简单。我也假设时间效率。内存效率会受到CPU缓存行为的限制，所以我们无论如何都不应该浪费它。

因此，我们将topn存储在一些结构中，这样可以快速地给我最少的成员。这是针对较大的n堆。我可以使用任何堆实现，即使是那些有错误的inckey和merge操作或根本没有这些操作的堆实现。我只需要insert、peek和remove操作。第10个是相当小的一个，我甚至不需要堆，特别是在编译好的编译器的编译语言中。我可以使用有序的数组或列表，甚至无序的。所以在我提到heap bellow的每个地方，都可以使用有序或无序的数组或列表。只有在顶部n中较大的n才需要堆。

所以就是这样，我们将存储顶部N公司名称和插入堆时的volume。

因此，我们将存储公司name作为密钥，并交易volume到目前为止，以及flag指示在HashMap中的堆中存储。

所以这里有算法。我们将有包含堆的状态，堆中的公司数量和HashMap。对于每个到达的公司mane和volume，我们将在HashMap中增加volume。然后，如果堆中的公司小于n(10)，我们将从hashmap中添加该公司name和volume，如果还没有的话（根据flag，并在hashmap中设置此标志）。否则，如果堆已满，当前公司不在堆中，我们将查看堆，如果当前公司到目前为止（在hashmap中）交易的卷少于堆中的公司，我们可以完成此交易并进入下一个。否则，我们必须首先更新堆中的公司。虽然位于堆顶部的公司（意味着卷)在堆中的卷小于当前堆中的卷并且与hashmap中的卷不同，但我们将更新该卷。可以通过从堆中删除并插入右值来完成。然后再次检查堆的顶部等等。注意，我们不需要更新堆中的所有公司，甚至不需要更新所有不是最新的顶级堆公司。挺懒的。如果当前公司的卷仍然大于堆顶部的卷，我们将从堆中删除公司，并在HashMap中插入当前公司和更新标志。仅此而已。

简要概述：

堆中的卷可能过期

以公司名称作为键，以最新的卷和指示堆成员的标志作为值的hashmap

首先在hashmap中更新当前公司卷并记住

新交易时间复杂性的处理很好O(1)。O(1)是hashmap查找，O(1)是堆中的peek。堆中的insert和delete被摊销为O(1)或O(logN)，其中n是常量，因此O(1)仍然是常量。堆中的更新数为O(N)，所以O(1)。当公司数量有上限时，您还可以计算处理时间的上限（开头提到的hashmap大小问题），因此通过良好的实现，您可以将其视为实时的。请记住，更简单的解决方案（如有序列表或无序列表、更新所有顶级成员等等）可以为nas 10带来更好的编译代码性能，尤其是在现代HW上。

该算法即使用函数语言也能很好地实现，只是不存在纯函数哈希表，但trie必须具有O(1)行为，否则会有不纯的模块。例如，Erlang实现使用有序列表作为hashMap的堆和字典。（我最喜欢的函数堆是配对堆，但对于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.

它每秒执行600k次交易。我希望在C实现中每秒几百万，这取决于公司的数量。更多的公司意味着更慢的K/V查找和更新。