c++ - 顶部命中对象的结构

Question

我想要一个接收到hit的 s 参数object，显示它的频率。并且能够拥有最频繁的 top hits object。 Unordered_map适合第一部分，object作为键和hit值。

unordered_map<object,int> 

它可以快速搜索object并增加其hit. 但是排序呢？priority_queue启用顶部命中对象。但是如何增加对象的命中？

Answer 1

I managed to solved it by keeping track of sorted list of objects by their hit number as I insert the objects. So there is always the list of the most N top hits. There are 3,000,000 objects and I want to have the top 20.

Here are the structures I used: key_hit to keep track of hits (by key, a string, I mean the object):

unordered_map<string, int> key_hit;

two arrays : hits[N], keys[N] which contains the top hits and their corresponding key (object).

idx,    hits,   keys
 0,     212,    x
 1,     200,    y
 ...
 N,     12,     z

and another map key_idx to keep the key and its corresponding index:

unordered_map<string,int> key_idx;

Algorithm (without details):

• key is input.
• search the key in key_hit, find its hit and increment (this is fast enough).
• if hit<hits[N], ignore it.
• else, idx=key_idx[key], (if not found, add it to structures and delete the existing one. it too long to write all details)
• H=h[idx]++
• check whether it is greater than the above entry, h[idx-1]<H. if yes, swap idx and idx-1 in key_idx,hits,keys.

I tried to make it fast. but I don't know how far it's fast.

Answer 2

我建议你看一下splay 树，它以最近和最常访问的对象更接近顶部的方式保存对象。这依赖于几个 euristicts，因此会给你一个完美解决方案的近似值。

对于一个精确的解决方案，最好实现自己的二进制堆并实现操作icrement优先级。理论上同样用于backing for priority_queue，但没有cahnge优先级操作，但可以在不影响数据结构操作复杂度的情况下完成。