d**6
发帖数: 106 | 1 不知道是不是可以在这个版问
看面经的时候看到一个题，就是说不断有股票价格进来，要实时按顺序show出变动最频
繁的Top K只股票代码。原题在这，第一轮里面的问题 http://www.1point3acres.com/bbs/thread-113733-1-1.html
楼主说用heap来做，我没想明白用heap可以做到最优化么？
请教各位大神们 |
s****3
发帖数: 270 | |
h**********c
发帖数: 4120 | |
n*****x
发帖数: 686 | 4 最简单的是用1个treemap记录k个高频，一个hash map记录每个股票的频率，每次更新
都看一眼treemap的min，大就查找lowerbound然后更新。update时间复杂度O(k)。
如果update时间要求O1,就再加一个linked list记录k个频率，treemap改成hashmap记
录iterator。
那个楼主说的heap大概不行，得用hash heap
【在 d**6 的大作中提到】
: 不知道是不是可以在这个版问
: 看面经的时候看到一个题，就是说不断有股票价格进来，要实时按顺序show出变动最频
: 繁的Top K只股票代码。原题在这，第一轮里面的问题 http://www.1point3acres.com/bbs/thread-113733-1-1.html
: 楼主说用heap来做，我没想明白用heap可以做到最优化么？
: 请教各位大神们
|
d**6
发帖数: 106 | 5 我觉得这个方法靠谱！
非常感谢大牛指点！
【在 n*****x 的大作中提到】
: 最简单的是用1个treemap记录k个高频，一个hash map记录每个股票的频率，每次更新
: 都看一眼treemap的min，大就查找lowerbound然后更新。update时间复杂度O(k)。
: 如果update时间要求O1,就再加一个linked list记录k个频率，treemap改成hashmap记
: 录iterator。
: 那个楼主说的heap大概不行，得用hash heap
|
L***s
发帖数: 1148 | 6 hash heap 思路算是 baseline 标准答案。就在原有的 min heap array
基础上内置一个 hash map 来标记 key 在 heap array 中的 index，
sift up/down, pop, push 每次触发 swap 的时候更新 index 即可。
如果 N >> K，为省空间一般用 min heap of size K，时间每次 O(log K)；
如果 N 和 K 差不多，用 max heap of size N，全装进去好了。
股票总数 N 其实不会太大，所以两者均可。
拓展开来，像这种求 top K frequent 的问题，在 N 非常大时，
hash heap 里面那个 hash map 容易爆（虽然可以取模分布在多机）。
如果不需要准确统计变动次数，允许计数误差(高估)，
其实可用一些基于概率的数据结构来替换该 hash map，
比如类似 bloom filter 的各种变种，比如下面链接提到的 CM Sketch：
http://soulmachine.gitbooks.io/system-design/content/cn/bigdata/heavy-hitters.html
【在 n*****x 的大作中提到】
: 最简单的是用1个treemap记录k个高频，一个hash map记录每个股票的频率，每次更新
: 都看一眼treemap的min，大就查找lowerbound然后更新。update时间复杂度O(k)。
: 如果update时间要求O1,就再加一个linked list记录k个频率，treemap改成hashmap记
: 录iterator。
: 那个楼主说的heap大概不行，得用hash heap
|
