e**t
发帖数: 39 | 1 Any ideas?
It was asked so many times by almost every company |
u*****o
发帖数: 1224 | |
c******n
发帖数: 16666 | |
e**t
发帖数: 39 | 4 No. it's asking on the server side, how to answer this questions any time.
【在 c******n 的大作中提到】
: 网页里插段js？
|
g*****g
发帖数: 34805 | 5 put the url and the counter in memcache or Cassandra, done.
Those 2 did the hashing and linear scaling for you. this is called real
world solution.
【在 e**t 的大作中提到】
: Any ideas?
: It was asked so many times by almost every company
|
z****e
发帖数: 54598 | 6 aop上一个interceptor生成log
把log放到cassandra里面去
最后用mapreduce找结果
这是大的具体到实现的想法
如果是纯粹内存中的结果的话
先实现拦截器
然后找个结构存放
随便你用什么，比如最简单的，用arraylist吧
然后启动一个额外的线程
对list里面的超时的予以删除
这里有并发冲突的问题，那么老样子，上java.util.concurrent包
解法很多，看对方期望的是什么 |
r****s
发帖数: 1025 | 7 这个是经典的stream processing问题。
Server把url扔到后端，后端有数个server或者process,最简单的方法就是hash url然
后决定按hashcode把url扔到那个server或者process （modulo就可以了）,这个
process就把url累计count一下，然后把url:count这个pair 扔到后一级的process或者
server，后一级的server把url:count存到一个concurrent hashmap里。一个thread 大
概每10秒钟把这个map扫一遍，给出前10名。
这是很粗略的方法，讲究一些的可以加各种花里胡哨的东西上去。
知道twitter storm吗？就是干这个的。http://storm-project.net/ 阿里巴巴和淘宝都在用，估计那个主要开发者Xu Mingming也是淘宝的。 竞争对手是Apache S4,但是S4明显不是对手。 |
A*H
发帖数: 127 | 8 你这些counter都是ignore time的
如果查询是dynamic time range的呢(top K urls in recent N mins)
storm也不是完美的，它本身design是允许有误差的，twiiter要发布的hummingbird就
是结合online (storm) &offline (hadoop)，for accuracy
【在 r****s 的大作中提到】
: 这个是经典的stream processing问题。
: Server把url扔到后端，后端有数个server或者process,最简单的方法就是hash url然
: 后决定按hashcode把url扔到那个server或者process （modulo就可以了）,这个
: process就把url累计count一下，然后把url:count这个pair 扔到后一级的process或者
: server，后一级的server把url:count存到一个concurrent hashmap里。一个thread 大
: 概每10秒钟把这个map扫一遍，给出前10名。
: 这是很粗略的方法，讲究一些的可以加各种花里胡哨的东西上去。
: 知道twitter storm吗？就是干这个的。http://storm-project.net/ 阿里巴巴和淘宝都在用，估计那个主要开发者Xu Mingming也是淘宝的。 竞争对手是Apache S4,但是S4明显不是对手。
|
z****e
发帖数: 54598 | 9 上次看swjtuer的回答
还有一个可能可以用的数据结构：priorityqueue
如果多线程，priorityblockingqueue |
A*H
发帖数: 127 | 10 一般top k都会想到priority queue,要回答好这个问题，还是有很多细节要考虑
比如queue size维护多大，expired的node要remove掉，怎么remove又要保证
concurrency performance
【在 z****e 的大作中提到】
: 上次看swjtuer的回答
: 还有一个可能可以用的数据结构：priorityqueue
: 如果多线程，priorityblockingqueue
|
|
|
e**t
发帖数: 39 | 11 how to deal with time thing?
last 1 hr means it changes the time range whenver you query
【在 g*****g 的大作中提到】
: put the url and the counter in memcache or Cassandra, done.
: Those 2 did the hashing and linear scaling for you. this is called real
: world solution.
|
e**t
发帖数: 39 | 12 Assume the memory solution, do you keep all the items in memory?
For 24 hrs, that might be quite large
【在 z****e 的大作中提到】
: aop上一个interceptor生成log
: 把log放到cassandra里面去
: 最后用mapreduce找结果
: 这是大的具体到实现的想法
: 如果是纯粹内存中的结果的话
: 先实现拦截器
: 然后找个结构存放
: 随便你用什么，比如最简单的，用arraylist吧
: 然后启动一个额外的线程
: 对list里面的超时的予以删除
|
e**t
发帖数: 39 | 13 yeah. how to use it?
【在 A*H 的大作中提到】
: 一般top k都会想到priority queue,要回答好这个问题，还是有很多细节要考虑
: 比如queue size维护多大，expired的node要remove掉，怎么remove又要保证
: concurrency performance
|
r****s
发帖数: 1025 | 14 omfg, 少侠，你就不能想想办法？
比如那个每10秒钟的thread,读完数据之后你就不能扔到Kafka里面按时间查询？或者随
便一个数据库Mongo之类的都可以。对不对？
sorting on-the-fly是一个very bad idea,注意为什么那个10秒的thread要把数据结构
抄一遍下来，就是因为如果你有几千个url，每秒有几千个点击进来（比如Amazon),你
不可以做logN的insertion，只能做constant time的hash.
【在 A*H 的大作中提到】
: 一般top k都会想到priority queue,要回答好这个问题，还是有很多细节要考虑
: 比如queue size维护多大，expired的node要remove掉，怎么remove又要保证
: concurrency performance
|
z****e
发帖数: 54598 | 15 那就persist掉吧
太大的话，log留在内存里没有太多意义
【在 e**t 的大作中提到】
: Assume the memory solution, do you keep all the items in memory?
: For 24 hrs, that might be quite large
|
l*******0
发帖数: 63 | 16 基本思路应该就是use hash to count and min heap with size k to get top k? 如
果想要考虑时间区间的话的话，可否使得value复杂一些（key 还是url本身），比如说
是一个结构，结构内有多个单元，例如可以每小时一个单元，一天24个单元，记录整点
时候的点击数。 感觉实际中，这种东西不可能做到很精确吧？不大可能说你任意选一
个时间，然后往前数1个小时，就能得到一个点击数。。。那样的话，需要log的东西太
多了。。。还有什么更好的办法？ |
j*t
发帖数: 184 | |
f*******b
发帖数: 520 | |
t*********h
发帖数: 941 | 19 这个体有没有比较偏算法的一些idea？ 回帖都太偏SYStem了
【在 e**t 的大作中提到】
: Any ideas?
: It was asked so many times by almost every company
|
r****s
发帖数: 1025 | 20 这道题你要整出个单机版的解法，我包你进不了下一轮。
给个链接，你们学习一下。
http://www.michael-noll.com/blog/2013/01/18/implementing-real-t
【在 t*********h 的大作中提到】
: 这个体有没有比较偏算法的一些idea？ 回帖都太偏SYStem了
|
t*********h
发帖数: 941 | 21 太长了呀 大牛能不能给总结一下
【在 r****s 的大作中提到】
: 这道题你要整出个单机版的解法，我包你进不了下一轮。
: 给个链接，你们学习一下。
: http://www.michael-noll.com/blog/2013/01/18/implementing-real-t
|
