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里？
|
