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。

No comments:

Post a Comment