假设我们有这样的结构：
// 16 bins
let BIN_OF_BINS = [
[], // 128 bits each chunk
[], // 256
[], // 512
[], // 1024
[], // 2048
[], // 4096
[], // 8192
[], // 16384
[], // 32768
[], // 65536
[], // 131072
[], // 262144
[], // 524288
[], // 1048576
[], // 2097152
[{ start: 0, count: 100 }], // 4194304
]
中的每个垃圾箱BIN_OF_BINS保存一组代表内存中插槽的节点。 n+1 bin 包含的节点大小是 n bin 大小的两倍。因此，第一个 bin 保存 128 位值，下一个保存 256 位值，接下来的 512 位值，等等。 bin 中包含的值可以是连续的，因此我们可能在“256 位值 bin”中拥有 1024 位的连续块，因此可以表示为：
bin2 = [{ count: 4, addressStartsAt: 0 }]
如果它有两个不连续的 1024 块，它将是：
bin2 = [
{ count: 4, addressStartsAt: 0 },
{ count: 4, addressStartsAt: 4096 /* let's say */ }
]
原则上，您可以在使用和释放内存时添加和删除这些垃圾箱。但对于这个问题，我们只关心使用已释放的内存（即我们不关心这个问题的释放内存）。
所以当BIN_OF_BINS开始时，只有最上面的 bin 有 100 个值。所以我们从这个开始：
// 16 bins
let BIN_OF_BINS = [
[], // 128 bits each chunk
[], // 256
[], // 512
[], // 1024
[], // 2048
[], // 4096
[], // 8192
[], // 16384
[], // 32768
[], // 65536
[], // 131072
[], // 262144
[], // 524288
[], // 1048576
[], // 2097152
[{ start: 0, count: 100 }], // 4194304
]
现在，当我们去获取 256 位值时，我们发现没有，因此它会遍历列表到更大的 bin，并将其分成两半（或者执行其他操作，我将对此进行介绍）。因此，如果我们要求全新的 1 256 值BIN_OF_BINS，我们向上、向上、向上，直到到达顶峰才发现任何东西。然后我们迭代划分。从 4194304 开始，它是这样的（在我们已经迭代了空白到达顶部之后）：
// step 0
[{ start: 0, count: 100 }], // 4194304, bin 16
// step 1
[{ start: 4194304, count: 99 }], // 4194304, bin 16
[{ start: 0, count: 2 }], // 2097152, bin 15
// step 2
[{ start: 4194304, count: 99 }], // 4194304, bin 16
[{ start: 2097152, count: 1 }], // 2097152, bin 15
[{ start: 0, count: 2 }], // 1048576, bin 14
// step 3
[{ start: 4194304, count: 99 }], // 4194304, bin 16
[{ start: 2097152, count: 1 }], // 2097152, bin 15
[{ start: 1048576, count: 1 }], // 1048576, bin 14
[{ start: 0, count: 2 }] // 524288, bin 13
// etc.
我们继续这样划分，直到最终得到：
[{ start: 0, count: 2 }] // 256, bin 2
现在我们可以通过简单地执行以下操作从“bin 2”获取“256 位内存插槽”：
node.start += 256
node.count--
我们最终得到：
[{ start: 256, count: 1 }] // 256, bin 2
问题是，如何才能有效实施呢？这让我感到非常困惑和难以理解。
- 当获取某个大小（仅是前 4 个 bin 之一）时，如果不存在，请尝试从父级获取并分成两半。
- 如果父级没有，则细分其父级。
- etc.
基本上就是这样。这是我到目前为止所拥有的。我想在没有递归的情况下执行此操作（仅使用带有循环的迭代方法），因为它将在没有递归的地方使用。
// 16 bins
let BINS = [
[], // 4 32-bit values, so 128 bits each chunk
[], // 8 32-bit values, so 256
[], // 16 32-bit values, so 512
[], // 32 32-bit values, so 1024
[], // 2048
[], // 4096
[], // 8192
[], // 16384
[], // 32768
[], // 65536
[], // 131072
[], // 262144
[], // 524288
[], // 1048576
[], // 2097152
[{ start: 0, count: 100 }], // 4194304
]
function fetchBlockWithAllocation(i) {
let block = fetchBlock(i)
if (!block) prepareBlocks(i)
return fetchBlock(i)
}
function fetchBlock(i) {
if (!BINS[i].length) {
return -1
}
let bin = BINS[i]
let node = bin[0]
let address = node.start
node.count--
node.start += i * 32
if (!node.count) {
bin.shift()
}
return address
}
function prepareBlocks(index, howMany = 1024) {
let startBinIndex = index + 1
let scaleFactor = 1
while (startBinIndex < 16) {
let bin = BINS[startBinIndex++]
if (bin.length) {
for (let k = 0, n = bin.length; k < n; k++) {
let node = bin[k]
while (node.count) {
howMany -= scaleFactor
node.count--
}
}
// starting to get lost
} else {
}
}
}
堆栈/迭代方面让我陷入困境。似乎有一些简单的东西我缺少创建一个优雅的解决方案，而且我正在偏离轨道。我有prepareBlocks to 预分配一堆块，所以当它找不到任何块时，它就会批量执行，作为一种优化。理想情况下，它无需创建任何其他临时数组即可完成此操作。
我不断地想：
- 降低下一个级别。
- 我们还剩多少人？
- 降低下一个级别。
- 我们还剩多少人？
以更递归的方式尝试，我仍然陷入同一点：
let BINS = [
{ count: 0, array: [] }, // 4 32-bit values, so 128 bits each chunk
{ count: 0, array: [] }, // 8 32-bit values, so 256
{ count: 0, array: [] }, // 16 32-bit values, so 512
{ count: 0, array: [] }, // 32 32-bit values, so 1024
{ count: 0, array: [] }, // 2048
{ count: 0, array: [] }, // 4096
{ count: 0, array: [] }, // 8192
{ count: 0, array: [] }, // 16384
{ count: 0, array: [] }, // 32768
{ count: 0, array: [] }, // 65536
{ count: 0, array: [] }, // 131072
{ count: 0, array: [] }, // 262144
{ count: 0, array: [] }, // 524288
{ count: 0, array: [] }, // 1048576
{ count: 0, array: [] }, // 2097152
{ count: 0, array: [ { start: 0, count: 100 }] }, // 4194304
]
function prepareBlocks(index, minHowMany = 1024) {
let bin = BINS[index]
if (bin.count === 0) {
return prepareBlocks(index + 1, Math.ceil(minHowMany / 2))
} else {
let diff = Math.max(0, bin.count - minHowMany)
if (diff <= 0) {
return prepareBlocks(index + 1, Math.ceil(minHowMany / 2))
} else {
for (let k = 0, n = bin.length; k < n; k++) {
let node = bin[k]
if (node.count >= minHowMany) {
node.count -= minHowMany
} else {
// getting lost at same point
}
}
}
}
}
几乎就好像它必须曲折地遍历每个列表中的第一个项目，然后是第二个项目，依此类推，因此它只划分它需要的内容。
最新的伪代码是：
function allocateBunch(base, size, count) {
let desiredBits = size * count
let totalBits = 0
for bin, i in bins
let blockBits = 128 << i
while (bin.length)
block = bin[0]
let k = 0
let totalNewBits = block.count * blockBits
let totalWithNewBits = totalBits + totalNewBits
let diff = Math.floor(totalNewBits - desiredBits / blockBits)
block.count -= diff
let newChildBlock = { count: diff * (2 ** i) }
base.push(newChildBlock)
totalWithNewBits >= desiredBits
return
bin.shift()
}
注意：在寻找时预分配多少并不重要，我会说最大 4096 或其他东西，只是因为看起来足够合理。因此，在尝试获取块时，只需从最近的位置开始一直向下划分，这样您就可以获得所需大小的更多块。如果还不够，那么只需重复该过程即可。只是还不知道该怎么做。
另请注意，如果您考虑如何在该系统中“释放内存”，则可以在与奇数配对时合并每个节点，并将它们合并起来，这样您就会得到越来越大的块。也许这会影响你如何实现这一点，只是想指出。
还要寻求最大效率，我的意思是如果可能的话使用缓存或非幼稚的解决方案（例如重复进行计算或做不必要的工作）。
赏金将进入最优化的版本（在执行步骤、无递归等方面），这也很简单。
