请教大神们一道算法题关于实时输出Top K最频繁变动的股价 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教大神们一道算法题关于实时输出Top K最频繁变动的股价

请教大神们一道算法题关于实时输出Top K最频繁变动的股价# JobHunting - 待字闺中

d*62017-04-25 07:04

1 楼

不知道是不是可以在这个版问
看面经的时候看到一个题，就是说不断有股票价格进来，要实时按顺序show出变动最频
繁的Top K只股票代码。原题在这，第一轮里面的问题 http://www.1point3acres.com/bbs/thread-113733-1-1.html
楼主说用heap来做，我没想明白用heap可以做到最优化么？
请教各位大神们

s*32017-04-25 07:04

2 楼

关注一下也想知道...

h*c2017-04-25 07:04

3 楼

rb trea

n*x2017-04-25 07:04

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*62017-04-25 07:04

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*s2017-04-25 07:04

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 的大作中提到】