Thursday, March 20, 2014
找出过去12小时内访问量最大的url
输入是一个stream,是实时的被点击的url
要随时输出过去12小时最频繁的那个URL
记录过程不要求,但是要随时立刻输出最频繁的那个URL
用滚动数组
可以用个带戳的链表 或者滚动数组
每次把最老的一段删掉
不过如在记录节点时候 要保留一个Counter
删掉最老节点的时候 更新对应的 Counter
这个Counter 应该会要用 heap 存……
其实 如果不在乎写的性能 其实找一遍也行
不过用 priority queue 或者 heap 显得屌一点
------------------------------- 是用个hashmap, key是URL,value是一个circular array吗
一个带时间戳的 链表或者 滚动数组 里面记录所有在这个时间段送来的URL 和 指向 对应 Value 的 指针
value 本身 存在一个 priority queue 里面
或者 只存 URL 然后用个 hash表存 URL value指针对
value 本身存在 一个 priority queue 里面 每次有节点更新 就更新这个 heap
还是调整下 让 heap 里面的值也要带 URL value 对…… 不然不好找对应的 URL
map<URL, 滚动数组>,要性能的话再加上每个URL的moving sum,有请求时修改其值。heap根据sum排列,moving sum变化时更新heap。
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment