s*******m
发帖数: 228 | 1 message{msgId,byte[]}。
大量message持续的input，要支持Message[] getAll(
msgId)，问怎么存储message。
多个消息会具有同样的msgId， getAll(MessageId)是返回相同msgId的所有
消息。
输入是一个持续输入的流，内存大小固定，放不下淘汰旧的。
方案
然后他说就用数组存message,最后给了个hashmap做索引，类似数组实现的循环队列存
message，freelist管理内存的方案
freelist管理内存是什么意思？
hashmap的key = msgID, value是数组的index list。
更新数组的时候，更新index list。
是这样吗？ |
|
w*********g
发帖数: 30882 | 2 猴王：国内国际局势分析20111203
1、美国：
本周美国针对中国主要是和缅甸的交流来堵住中国在印度洋的一个出海口，同时关
于周三这一仗的分析下面有详细的内在逻辑分析。针对美国的这些措施，我国在朝鲜、
巴基斯坦和伊朗等地进行了外源性策应。
相关大宗的走势昨天已经写了专门的一篇文章。
对于欧元区，因为本周是欧元区发债比较集中的时期，美国的量化宽松起到了很好
的缓解作用，看看德国的短期国债收益率都是负了（收益率越低证明发行情况越好）。
同时也造就了欧美股市和非美货币的一波短期上涨。但是预计下周开始又会对于欧元区
开始一波攻击，不过欧元区已经是缴枪不杀了，所以美国不会用杀猪的手段的，只会用
剪羊毛的手段，让欧元形成波段性梯次的下降，德国的投降和这个很有关系，因为欧元
有序的下跌对于德国是大利好，有利于德国的出口，但是对于法国来说损失比收益大，
因此法国最近不太爽。
有个网友给了我一张美国航母的位置图（http://web.stratfor.com/images/northamerica/map/Naval_Update_11-30-11_800.jpg?utm_so... 阅读全帖 |
|
H****r
发帖数: 2801 | 3 哎怎么没人回。 用linked list + freeList做了下，果然只能处理到8个80byte的
queue...
第一个post出正确思路的有包子...
additional
queues
have |
|
H*M
发帖数: 1268 | 4 1. given a binary tree ,find the largest sub-tree which is a BST...(largest
mea
ns subtree having largest no of nodes in it)
我的理解是subtree就是说是一个子树,比如要到原来树的leaf,而不能把原来树的inter
nal nodes做leaf.也就是不能中间截一块,是这样的吗?
有什么好方法.我写的特别繁琐.if else 很多,用recursion.
2. 第二题说,design n stacks in an array of N. 这个我想愿意肯定不是让一个
stack分派固定的.感觉是要综合调配的,比如,如果array还有空,就不能说某个stack不
能加入了.我
想法是keep一个free list,,每个stack元素都要有个Next的指针,指向下个元素,stack
push的时候,就从freelist里面取.这样stack的元素就不连续了.
有什么其它的好办法么? |
|
|
S********t
发帖数: 3431 | 6 就是freelist first fit best fit那些，话说这个是我当年onsite第一个面试的第一
道题目，做的还有些紧张。没想到这好几年后，这个题还没有被ban |
|
M**u
发帖数: 10158 | 7 最简单的话，用freelist就可以了
其实linux里面也是用brk/sbrk实现的 |
|
y*******x
发帖数: 40 | 8 第二题我回答的不好。
开始给了个类LSM-Tree的方案，把message存硬盘，索引丢内存。面试官说只考虑全内
存方案。
又给了个类似memeche内存管理的block/slab+LRU方案，面试官说太复杂，哭了。。。
然后他说就用数组存message,最后给了个hashmap做索引，类似数组实现的循环队列存
message，freelist管理内存的方案，可能我水平有限，但我觉得这方案不如用block/
slab来的效率高。特别是做getAll和remove的时候。 |
|
y*******x
发帖数: 40 | 9 第二题我回答的不好。
开始给了个类LSM-Tree的方案，把message存硬盘，索引丢内存。面试官说只考虑全内
存方案。
又给了个类似memeche内存管理的block/slab+LRU方案，面试官说太复杂，哭了。。。
然后他说就用数组存message,最后给了个hashmap做索引，类似数组实现的循环队列存
message，freelist管理内存的方案，可能我水平有限，但我觉得这方案不如用block/
slab来的效率高。特别是做getAll和remove的时候。 |
|
|
U********d
发帖数: 577 | 11 Delete一般是操作系统实现的，通常情况下你delete掉一个对象，操作系统只是将这个
对象所在的内存块标记为空闲，比如windows2000通常情况是把这个堆链回到freelist
或者其他几个堆管理的队列里面去。
把这块内存清0的工作是很费时间的，操作系统一般不主动作这件事情，所以删除掉后
无论内容还是对象的指针都没有任何变化。至于栈上的数值，除非你显示地指定Cptr=
null，否则在它整个生命周期里面也没有任何人会管他，这两个条件导致你短时间内无
论取成员变量还是调用成员函数都没有任何区别。
有可能变化的情况是你再次new了一个，操作系统有可能把同一块地址再分配给你然后
你又做了其他的事情。还有一种可能就是等足够长的时间System Idle Process把这块
地址清0了。
把操作系统看作政府的话，可以简单的认为delete只是贴了一个拆迁的标签，表示这栋
房子以后可以随便拆了。贴标签后你再去访问里面的人，可能钉子户还在，因为没有人
赶他走，但是你不能保证每次去都能看到，因为指不定哪天操作系统就给你拆迁了。 |
|
N***m
发帖数: 4460 | 12 if you set cptr=null, you may still use it in some cases.
freelist |
|
t****t
发帖数: 6806 | 13 delete is usually not implemented by OS. it's usually implemented by libc++.
freelist |
|
U********d
发帖数: 577 | 14 其实就是在说堆内存管理的问题 :)
不过讨论到后面我们纠缠于“内存管理到底是不是操作系统的一部分”，钻牛角尖的。
不涉及到新分配内存，堆回收和融合，freelist、lookaside或者heap cookie什么的。
没有什么营养，就俩小孩在斗气呢，呵呵~ |
|
h******u
发帖数: 155 | 15 "大部分JAVA的对象分配通常都是几条机器指令"有點誇張，呵呵。目前最efficient也
就是thread-local bump-the-pointer allocation, 就算是fast path也需要平均 12
instructions。C/C++的memory allocation也不是一定需要freelist-based，很多
customized的allocator就用bump-the-pointer。並且allocation的efficiency不光光
是通過allocation幾條指令來衡量的，還有好多好多的因素，比如説cache locality,
同一個processor的不同threads會不會經常access同一個cache line，還有
fragmentation等等。各種原因在一起非常複雜。
另外performance-wise“可以肆无忌惮地创建对象，把一切对象化”不是一個good
idea :) 現在看到很多server applications的scalability已經被excessive object
creation所限制。我們study過... 阅读全帖 |
|
