a******d 发帖数: 82 | 1 Implement two functions that assign/release unique id's from a pool. Memory
usage should be minimized and the assign/release should be fast, even under
high contention.
目前想法就是两个HashSet 一个放用过的ID 一个放没用过的ID, 每次assign 和
release时修改这两个HashSet.
不过如果多线程情况下 容易成为瓶颈. |
a******d 发帖数: 82 | 2 或者可以把所有可用IDs 分成N 段, 然后这N段IDs 之间互相独立, 就可以并行访问修
改了.
目前只能想到这么多.
Memory
under
【在 a******d 的大作中提到】 : Implement two functions that assign/release unique id's from a pool. Memory : usage should be minimized and the assign/release should be fast, even under : high contention. : 目前想法就是两个HashSet 一个放用过的ID 一个放没用过的ID, 每次assign 和 : release时修改这两个HashSet. : 不过如果多线程情况下 容易成为瓶颈.
|
h**********c 发帖数: 4120 | 3 如你第二段说,如果把线性分段设置成树状结构呢?
锁树节点而不是锁,assign, release,可能好一些 |
w*******i 发帖数: 186 | 4 hashset虽然耗的内存是O(N),但是常数大。我onsite也面过这题,做出来后说把
hashset换掉。纯array做都不够,最后被逼着往bitmap上想。这个有点类似于实现一个
文件系统,metadata区域有个bitmap表示哪些block被分配。
个人觉得这题很坑爹,最后用居然时间换内存。bitmap上只能线性查找,只不过用多层
不同粒度去优化。 |
a******u 发帖数: 69 | 5 bitmap上线性查找是指做assign的时候要找没用过的id?
多层不同粒度优化是指,先用查大block里面有没有没有的id然后再逐步深入到更小的
block里?
【在 w*******i 的大作中提到】 : hashset虽然耗的内存是O(N),但是常数大。我onsite也面过这题,做出来后说把 : hashset换掉。纯array做都不够,最后被逼着往bitmap上想。这个有点类似于实现一个 : 文件系统,metadata区域有个bitmap表示哪些block被分配。 : 个人觉得这题很坑爹,最后用居然时间换内存。bitmap上只能线性查找,只不过用多层 : 不同粒度去优化。
|
w*******i 发帖数: 186 | 6 这题我当时做得不好,不知道最优解法是什么。根据那人的提示大概就是这样。我也觉
得线性查找很坑爹。
【在 a******u 的大作中提到】 : bitmap上线性查找是指做assign的时候要找没用过的id? : 多层不同粒度优化是指,先用查大block里面有没有没有的id然后再逐步深入到更小的 : block里?
|