w********g
发帖数: 106 | 1 指出了一个design的题目。
class Msg
{
long key; // unique
long val;
};
class Window
{
Window(int nMicrosecs);
addMsg(Msg m);
Msg getMsg(long key);
Double getAvg();
};
有一个stream of messgages，把最近的一些message存到Window里面，就像个sliding
window一样。要求design这个Window class。
比如，Window里面存最近5分钟的message。
addMsg（）就要添加一个mesage。
getMsg（）就return一个message。
getAvg（）计算window里所有message的val的平均值。
要求要efficient。
我不明白他说的5分钟什么意思，因为msg数据结构里没有时间，他说我可以自己添加。
我又问：如果过去5分钟没有任何message进来，那么window就空了。他马上说：明白你
的意思，不用考虑window的这种随时间的变化。我就问：那时间就无意义了，还不如就
用一个serial number，window的size就是serial number的差值。这里他反复变化，浪
费了很久。
讨论了半天才明白他说的efficient只是指用lock锁住window而已。addMsg时读写锁，
其他操作只加上写锁。那问题又来了，如果window锁住了，新来的message怎么办？是
不是临时存起来？
我回答的非常不好，他的很多考点我没有理解。感觉最难的是题目里有太多unclear的
东西，仔细design一下就遇到很多东西要和他讨论，他自己也说讨论三天都讨论不完。
估计就是考我找design weakness的能力和communication吧。 |
s********r
发帖数: 403 | 2 basic circular buffer, parallel access efficiency |
w********g
发帖数: 106 | 3 我用了circular buffer了，也提了用list。
parallel access efficiency怎么实现呢？
【在 s********r 的大作中提到】
: basic circular buffer, parallel access efficiency
|
u*****o
发帖数: 1224 | |
r*******e
发帖数: 7583 | 5 我觉得要考虑锁的粒度，不要直接锁住整个circular buffer
每个buffer entry单独一个锁应该能提高效率
sliding
【在 w********g 的大作中提到】
: 指出了一个design的题目。
: class Msg
: {
: long key; // unique
: long val;
: };
: class Window
: {
: Window(int nMicrosecs);
: addMsg(Msg m);
|
c********p
发帖数: 1969 | |
s*******n
发帖数: 305 | |
s********r
发帖数: 403 | 8 提高 circular buffer 的并发是个 open question,
我所了解并实现、测试过的是利用原子级操纵符代替 lock,实现了fine grain，从
interface 上完成类似 transaction memory 的操作。
circular buffer 因为简单高效，一般相关公司都有自己的独门秘籍针对具体应用在并
发行上进行专门优化，还有些是专利的技术
【在 w********g 的大作中提到】
: 我用了circular buffer了，也提了用list。
: parallel access efficiency怎么实现呢？
|
c*********m
发帖数: 43 | 9 都有依据key查找了，Msg getMsg(long key);肯定得用hash table啊，只是最好每个
bucket给个锁，而不是锁整个表
还有一个trick应该就是根据原有的n条消息的averge value,当加入一条消息时，更新
averge.
average = (n * average + new value) / (n + 1)
最近5分钟的message这个实现，可以当每次访问一个bucket的item时，把这个bucket的
大于5分钟的东西去掉，memcached应该有处理这个的策略，我有些忘了。。 |
z****e
发帖数: 54598 | 10 这只是一个很简单的考多线程基础的题
所以对方后面会说用lock，线性实现就足够了
Window类添加一个hashmap
记录每一个message进来的时间
然后实现put方法，需要找一个类来记录msg
还是hashmap吧，既然已经用了hashmap
然后实现get方法
get方法里面，先找
找到后做一个判断，是否当前时间超过5分钟
超过，则返回空，否则返回找到的值
然后关键是remove超过5分钟的msg
简单啊，启动一个scheduler线程，sleep(1000*60)
然后醒来后，扫一遍记录时间的hashmap
找到超时的msg，去记录msg的hashmap删除就好了
这里会有并发的问题，hashmap不是线程安全的
上java.util.concurrent
这就是所谓的efficiency的意思 |
|
|
c*********m
发帖数: 43 | 11 remove超过5分钟的msg这块应该有更好的策略啦。你这样的话删除性能不太好。
【在 z****e 的大作中提到】
: 这只是一个很简单的考多线程基础的题
: 所以对方后面会说用lock，线性实现就足够了
: Window类添加一个hashmap
: 记录每一个message进来的时间
: 然后实现put方法，需要找一个类来记录msg
: 还是hashmap吧，既然已经用了hashmap
: 然后实现get方法
: get方法里面，先找
: 找到后做一个判断，是否当前时间超过5分钟
: 超过，则返回空，否则返回找到的值
|
z****e
发帖数: 54598 | 12 谁说的，要不要试试？
我测试过，可以做到比你用的hashtable快十倍
【在 c*********m 的大作中提到】
: remove超过5分钟的msg这块应该有更好的策略啦。你这样的话删除性能不太好。
|
c*********m
发帖数: 43 | 13 我是说应该有比你那个更好的策略啦，你那个策略只是很一般的删除方法。我都没说我
的删除方法，你怎么知道快10倍的。。
【在 z****e 的大作中提到】
: 谁说的，要不要试试？
: 我测试过，可以做到比你用的hashtable快十倍
|
c*********m
发帖数: 43 | 14 拿Double getAvg()来说，还是hash table 的每个bucket 都有一个average 和mesage
count会好些。 |
z****e
发帖数: 54598 | 15 因为你已经说了你用什么类了
这题考察的是多线程大并发的策略
看你用什么类就知道效率了
【在 c*********m 的大作中提到】
: 我是说应该有比你那个更好的策略啦，你那个策略只是很一般的删除方法。我都没说我
: 的删除方法，你怎么知道快10倍的。。
|
z****e
发帖数: 54598 | 16 瓶颈不在这里
写的时候你的整个对象会被锁
而写操作是频率最高的操作
对于这题来说
mesage
【在 c*********m 的大作中提到】
: 拿Double getAvg()来说，还是hash table 的每个bucket 都有一个average 和mesage
: count会好些。
|
c*********m
发帖数: 43 | 17 写时你是锁整个hashtable还是一个bucket啊？ 肯定应该锁一个bucket吧。取平均数的
时候你也不应该锁住整个表来遍历所有msg吧？
这题要讨论的东西多了， 根据不同情况应该有不同的策略，我觉得啊。
【在 z****e 的大作中提到】
: 瓶颈不在这里
: 写的时候你的整个对象会被锁
: 而写操作是频率最高的操作
: 对于这题来说
:
: mesage
|
z****e
发帖数: 54598 | 18 用现成的类就行了
自己去写估计你来不及写完
【在 c*********m 的大作中提到】
: 写时你是锁整个hashtable还是一个bucket啊？ 肯定应该锁一个bucket吧。取平均数的
: 时候你也不应该锁住整个表来遍历所有msg吧？
: 这题要讨论的东西多了， 根据不同情况应该有不同的策略，我觉得啊。
|
s********u
发帖数: 1109 | 19 弱弱的问一下，这一块的基础知识（多线程，circular buffer），应该怎么去补（不
可能去看大部头的书了，也消化不了）。非CS专业小白，只看过Careercup书和
leetcode |
u*****o
发帖数: 1224 | 20 你说的这个我觉得很好耶,每个BUCKET记录上到目前为止的average,而不是遍历全部
buffer, 但remove的时候，这个average也得跟着更新吧，去掉过时的msg.
【在 c*********m 的大作中提到】
: 都有依据key查找了，Msg getMsg(long key);肯定得用hash table啊，只是最好每个
: bucket给个锁，而不是锁整个表
: 还有一个trick应该就是根据原有的n条消息的averge value,当加入一条消息时，更新
: averge.
: average = (n * average + new value) / (n + 1)
: 最近5分钟的message这个实现，可以当每次访问一个bucket的item时，把这个bucket的
: 大于5分钟的东西去掉，memcached应该有处理这个的策略，我有些忘了。。
|
c*********m
发帖数: 43 | 21 对，remove的时候也要更新啦。
【在 u*****o 的大作中提到】
: 你说的这个我觉得很好耶,每个BUCKET记录上到目前为止的average,而不是遍历全部
: buffer, 但remove的时候，这个average也得跟着更新吧，去掉过时的msg.
|
