如何有效地将大块细分为许多大小为 JavaScript 的 2 次幂的小块
How to efficiently subdivide large block into many small blocks sized power of 2 in JavaScript
建立 ：
function allocate(bits) {
if ((bits & (bits - 1)) != 0) {
throw "Parameter is not a power of 2";
}
if (bits < 128 || bits > 4194304) {
throw "Bits required out of range";
}
var startBinIndex = Math.log2(bits >> 7);
var lastBin = BIN_OF_BINS.length - 1;
for (var binIndex = startBinIndex; binIndex <= lastBin ; binIndex++) {
var bin = BIN_OF_BINS[binIndex];
//
// We have found a bin that is not empty...
//
if (bin.length != 0) {
//
// Calculate amount of memory this bin takes up
//
var thisBinMemorySize = (128 << binIndex);
var lastBinOfBinsIndex = bin.length - 1;
var binBlock = bin[lastBinOfBinsIndex];
var memoryAddress = binBlock.start;
//
// We are going to return this block
//
var allocatedMemoryBlock = {start : memoryAddress, count : 1};
//
// Before we return the above block, we need to remove the block if count is 1 otherwise decrease count and adjust memory start pointer by bin size
//
if (binBlock.count == 1) {
bin.pop();
}
else {
binBlock.count--;
binBlock.start += thisBinMemorySize;
}
//
// if we want 1024 bits and it takes it from bin 15, we simply subtract 1024 from 4194304 which gives us 4193280
// if we then populate bin 3 (1024 bits) onward, until bin 14, the exact number we end up populating those bins with is 4183280
//
var remainingUnsedMemory = thisBinMemorySize - bits;
var adjustmentSize = bits;
while (remainingUnsedMemory != 0) {
memoryAddress += adjustmentSize;
BIN_OF_BINS[startBinIndex].push({start : memoryAddress, count : 1});
startBinIndex++;
remainingUnsedMemory -= bits;
adjustmentSize = bits;
bits <<= 1;
}
return allocatedMemoryBlock;
}
}
return null; // out of memory...
}
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
]
console.log("Memory returned:", allocate((128 << 1)));
console.log("Memory returned:", allocate((128 << 1)));
console.log("Memory returned:", allocate((128 << 1)));
console.log("Memory returned:", allocate((128 << 2)));
console.log("Memory returned:", allocate((128 << 2)));
console.log("Memory returned:", allocate((128 << 2)));
console.log("Memory returned:", allocate((128 << 1)));
console.log(JSON.stringify(BIN_OF_BINS, null, 2));
你怎么能让它接受两个参数，allocate(bits, count)，而不是一个，其中 count 参数告诉要分配多少 bits 大小的内存插槽 提前?
我整晚都在尝试，但没有得到任何非常接近工作的结果，而且它开始失去原来答案的简单性。
// desired count is a power of two only
function allocateBunch(bins, base, size, desiredCount) {
let desiredFactor = (2 ** (size - 1))
let totalFound = 0
let i = 0
let n = bins.length
while (i < n) {
// 1024 4096
let factor = 1 << i
let bin = bins[i]
while (bin.length) {
block = bin[0]
let diff = desiredCount - totalFound
let diff1 = Math.ceil(diff / factor)
let min = Math.min(block.count, diff1)
block.count -= min
totalFound += (min * factor)
base.push({
start: block.start,
count: diff
})
block.start += ((min * factor) * (64 << size))
let done = totalFound >= desiredCount
if (done) return
if (done) {
var bits = (64 << size)
var remainingUnsedMemory = ((min * factor) - diff) * bits
var adjustmentSize = bits
var startBinIndex = i
var memoryAddress = block.start + (diff * bits)
while (remainingUnsedMemory != 0) {
// memoryAddress += adjustmentSize;
// bins[startBinIndex].push({
// start: memoryAddress,
// count: 1
// });
// startBinIndex--;
remainingUnsedMemory -= bits;
// adjustmentSize = bits;
// bits >>= 1;
}
} else {
bin.shift()
}
}
i++
}
}
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
]
let base = []
allocateBunch(BIN_OF_BINS, base, 1, 4096)
allocateBunch(BIN_OF_BINS, base, 1, 8192)
console.log(BIN_OF_BINS, base)
基本上我要做的就是这个。假设您想提前分配 100、1000 或 4096（选择一些数字）块（遵循上下文的链接问题，或上面的第一个算法）。你有 BIN_OF_BINS ，它以一个顶级值开始，表示一些可用内存。您可以根据需要对其进行细分以获得所需的块，但实际上不需要递归细分内容，您可以使用快捷方式。你可以做一些计算来判断跳多远。但是很难到达那里。
如果块（在许多 additions/removals 或 allocate/frees 之后）散落在各处，理想情况下算法仍然能够收集一定大小的一堆块，因此它们已准备好采摘。
例如：如果我要求 1 个大小为 512 的块，我应该得到：
[
[],
[],
[ { start: 0, count: 1 } ],
[ { start: 1024, count: 1 } ],
[ { start: 2048, count: 1 } ],
[ { start: 4096, count: 1 } ],
[ { start: 8192, count: 1 } ],
[ { start: 16384, count: 1 } ],
[ { start: 32768, count: 1 } ],
[ { start: 65536, count: 1 } ],
[ { start: 131072, count: 1 } ],
[ { start: 262144, count: 1 } ],
[ { start: 524288, count: 1 } ],
[ { start: 1048576, count: 1 } ],
[ { start: 2097152, count: 1 } ],
[ { start: 4194304, count: 99 } ]
]
如果我改为请求 8192 512 位值，我应该：
[
[],
[],
[ { start: 0, count: 8192 } ],
[],
[],
[],
[],
[],
[],
[],
[],
[],
[],
[],
[ { start: 2097664, count: 1 } ],
[ { start: 4194304, count: 99 } ]
]
更新版本，内存偏移计算现在是向后而不是向前。
let FRAGMENTED_BINS_OF_BIN = [
[], // 128 bits each chunk
[], // 256
[], // 512
[], // 1024
[], // 2048
[], // 4096
[], // 8192
[], // 16384
[], // 32768
[], // 65536
[], // 131072
[], // 262144
[], // 524288
[], // 1048576
[], // 2097152
[{ start: 0, count: 100 }], // 4194304
];
function allocate(binDataSource, bits, quantity) {
var requiredSize = bits * quantity
if (requiredSize < 128 || requiredSize > 4194304) {
throw "Bits required out of range";
}
var lastBin = binDataSource.length - 1;
for (var binIndex = 0; binIndex <= lastBin ; binIndex++) {
var bin = binDataSource[binIndex];
//
// We have found a bin that is not empty...
//
if (bin.length != 0) {
//
// Calculate amount of memory this bin takes up
//
var thisBinMemorySize = (128 << binIndex);
for (var b = bin.length - 1; b >= 0; b--) {
var blockOfInterest = bin[b];
var blockSize = blockOfInterest.count * thisBinMemorySize;
//
// We've found a continous block this bin that fits the amount we want
//
if (blockSize >= requiredSize) {
//
// We are going to return this block
//
var allocatedMemoryBlock = {start : blockOfInterest.start, count : quantity, bits : bits};
//
// Figure out how many blocks were consumed...
//
var blockConsumed = Math.ceil(requiredSize / thisBinMemorySize);
var totalMemoryConsumed = thisBinMemorySize * blockConsumed;
//
// Perfect amount, so delete whole block from bin
//
if (blockConsumed == blockOfInterest.count) {
bin.splice(b);
}
else {
//
// Otherwise count reduced by consumed block amount and the start address is adjusted to account for consumed block
//
blockOfInterest.count -= blockConsumed;
blockOfInterest.start += thisBinMemorySize * blockConsumed;
}
//
// We may have acquired more memory than we need so we need to put the excess back into their respective bins...
//
var leftOverMemory = totalMemoryConsumed - requiredSize;
if (leftOverMemory > 0) {
//
// adjust the left over memory start address by the amount we have actually used
//
var leftOverMemoryAddressStartsAt = allocatedMemoryBlock.start + requiredSize;
var endOfMemory = allocatedMemoryBlock.start + totalMemoryConsumed;
while (leftOverMemory != 0) {
//
// Previous bin... size and index
//
thisBinMemorySize >>= 1;
binIndex--;
//
// This unused block fits in this bin...
//
if (leftOverMemory - thisBinMemorySize >= 0) {
//
// Register it...
//
endOfMemory -= thisBinMemorySize;
binDataSource[binIndex].push({start : endOfMemory, count : 1});
//
// Reduce the amount of left over memory...
//
leftOverMemory -= thisBinMemorySize;
leftOverMemoryAddressStartsAt += thisBinMemorySize;
}
}
}
return allocatedMemoryBlock;
}
}
}
}
return false; // failed to find any sizable blocks
}
function freeMemoryBlock(memoryBlock) {
var bits = memoryBlock.bits;
delete memoryBlock.bits;
var belongsToBin = Math.log2(bits >> 7);
FRAGMENTED_BINS_OF_BIN[belongsToBin].push(memoryBlock);
}
建立
function allocate(bits) {
if ((bits & (bits - 1)) != 0) {
throw "Parameter is not a power of 2";
}
if (bits < 128 || bits > 4194304) {
throw "Bits required out of range";
}
var startBinIndex = Math.log2(bits >> 7);
var lastBin = BIN_OF_BINS.length - 1;
for (var binIndex = startBinIndex; binIndex <= lastBin ; binIndex++) {
var bin = BIN_OF_BINS[binIndex];
//
// We have found a bin that is not empty...
//
if (bin.length != 0) {
//
// Calculate amount of memory this bin takes up
//
var thisBinMemorySize = (128 << binIndex);
var lastBinOfBinsIndex = bin.length - 1;
var binBlock = bin[lastBinOfBinsIndex];
var memoryAddress = binBlock.start;
//
// We are going to return this block
//
var allocatedMemoryBlock = {start : memoryAddress, count : 1};
//
// Before we return the above block, we need to remove the block if count is 1 otherwise decrease count and adjust memory start pointer by bin size
//
if (binBlock.count == 1) {
bin.pop();
}
else {
binBlock.count--;
binBlock.start += thisBinMemorySize;
}
//
// if we want 1024 bits and it takes it from bin 15, we simply subtract 1024 from 4194304 which gives us 4193280
// if we then populate bin 3 (1024 bits) onward, until bin 14, the exact number we end up populating those bins with is 4183280
//
var remainingUnsedMemory = thisBinMemorySize - bits;
var adjustmentSize = bits;
while (remainingUnsedMemory != 0) {
memoryAddress += adjustmentSize;
BIN_OF_BINS[startBinIndex].push({start : memoryAddress, count : 1});
startBinIndex++;
remainingUnsedMemory -= bits;
adjustmentSize = bits;
bits <<= 1;
}
return allocatedMemoryBlock;
}
}
return null; // out of memory...
}
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
]
console.log("Memory returned:", allocate((128 << 1)));
console.log("Memory returned:", allocate((128 << 1)));
console.log("Memory returned:", allocate((128 << 1)));
console.log("Memory returned:", allocate((128 << 2)));
console.log("Memory returned:", allocate((128 << 2)));
console.log("Memory returned:", allocate((128 << 2)));
console.log("Memory returned:", allocate((128 << 1)));
console.log(JSON.stringify(BIN_OF_BINS, null, 2));
你怎么能让它接受两个参数，allocate(bits, count)，而不是一个，其中 count 参数告诉要分配多少 bits 大小的内存插槽 提前?
我整晚都在尝试，但没有得到任何非常接近工作的结果，而且它开始失去原来答案的简单性。
// desired count is a power of two only
function allocateBunch(bins, base, size, desiredCount) {
let desiredFactor = (2 ** (size - 1))
let totalFound = 0
let i = 0
let n = bins.length
while (i < n) {
// 1024 4096
let factor = 1 << i
let bin = bins[i]
while (bin.length) {
block = bin[0]
let diff = desiredCount - totalFound
let diff1 = Math.ceil(diff / factor)
let min = Math.min(block.count, diff1)
block.count -= min
totalFound += (min * factor)
base.push({
start: block.start,
count: diff
})
block.start += ((min * factor) * (64 << size))
let done = totalFound >= desiredCount
if (done) return
if (done) {
var bits = (64 << size)
var remainingUnsedMemory = ((min * factor) - diff) * bits
var adjustmentSize = bits
var startBinIndex = i
var memoryAddress = block.start + (diff * bits)
while (remainingUnsedMemory != 0) {
// memoryAddress += adjustmentSize;
// bins[startBinIndex].push({
// start: memoryAddress,
// count: 1
// });
// startBinIndex--;
remainingUnsedMemory -= bits;
// adjustmentSize = bits;
// bits >>= 1;
}
} else {
bin.shift()
}
}
i++
}
}
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
]
let base = []
allocateBunch(BIN_OF_BINS, base, 1, 4096)
allocateBunch(BIN_OF_BINS, base, 1, 8192)
console.log(BIN_OF_BINS, base)
基本上我要做的就是这个。假设您想提前分配 100、1000 或 4096（选择一些数字）块（遵循上下文的链接问题，或上面的第一个算法）。你有 BIN_OF_BINS ，它以一个顶级值开始，表示一些可用内存。您可以根据需要对其进行细分以获得所需的块，但实际上不需要递归细分内容，您可以使用快捷方式。你可以做一些计算来判断跳多远。但是很难到达那里。
如果块（在许多 additions/removals 或 allocate/frees 之后）散落在各处，理想情况下算法仍然能够收集一定大小的一堆块，因此它们已准备好采摘。
例如：如果我要求 1 个大小为 512 的块，我应该得到：
[
[],
[],
[ { start: 0, count: 1 } ],
[ { start: 1024, count: 1 } ],
[ { start: 2048, count: 1 } ],
[ { start: 4096, count: 1 } ],
[ { start: 8192, count: 1 } ],
[ { start: 16384, count: 1 } ],
[ { start: 32768, count: 1 } ],
[ { start: 65536, count: 1 } ],
[ { start: 131072, count: 1 } ],
[ { start: 262144, count: 1 } ],
[ { start: 524288, count: 1 } ],
[ { start: 1048576, count: 1 } ],
[ { start: 2097152, count: 1 } ],
[ { start: 4194304, count: 99 } ]
]
如果我改为请求 8192 512 位值，我应该：
[
[],
[],
[ { start: 0, count: 8192 } ],
[],
[],
[],
[],
[],
[],
[],
[],
[],
[],
[],
[ { start: 2097664, count: 1 } ],
[ { start: 4194304, count: 99 } ]
]
更新版本，内存偏移计算现在是向后而不是向前。
let FRAGMENTED_BINS_OF_BIN = [
[], // 128 bits each chunk
[], // 256
[], // 512
[], // 1024
[], // 2048
[], // 4096
[], // 8192
[], // 16384
[], // 32768
[], // 65536
[], // 131072
[], // 262144
[], // 524288
[], // 1048576
[], // 2097152
[{ start: 0, count: 100 }], // 4194304
];
function allocate(binDataSource, bits, quantity) {
var requiredSize = bits * quantity
if (requiredSize < 128 || requiredSize > 4194304) {
throw "Bits required out of range";
}
var lastBin = binDataSource.length - 1;
for (var binIndex = 0; binIndex <= lastBin ; binIndex++) {
var bin = binDataSource[binIndex];
//
// We have found a bin that is not empty...
//
if (bin.length != 0) {
//
// Calculate amount of memory this bin takes up
//
var thisBinMemorySize = (128 << binIndex);
for (var b = bin.length - 1; b >= 0; b--) {
var blockOfInterest = bin[b];
var blockSize = blockOfInterest.count * thisBinMemorySize;
//
// We've found a continous block this bin that fits the amount we want
//
if (blockSize >= requiredSize) {
//
// We are going to return this block
//
var allocatedMemoryBlock = {start : blockOfInterest.start, count : quantity, bits : bits};
//
// Figure out how many blocks were consumed...
//
var blockConsumed = Math.ceil(requiredSize / thisBinMemorySize);
var totalMemoryConsumed = thisBinMemorySize * blockConsumed;
//
// Perfect amount, so delete whole block from bin
//
if (blockConsumed == blockOfInterest.count) {
bin.splice(b);
}
else {
//
// Otherwise count reduced by consumed block amount and the start address is adjusted to account for consumed block
//
blockOfInterest.count -= blockConsumed;
blockOfInterest.start += thisBinMemorySize * blockConsumed;
}
//
// We may have acquired more memory than we need so we need to put the excess back into their respective bins...
//
var leftOverMemory = totalMemoryConsumed - requiredSize;
if (leftOverMemory > 0) {
//
// adjust the left over memory start address by the amount we have actually used
//
var leftOverMemoryAddressStartsAt = allocatedMemoryBlock.start + requiredSize;
var endOfMemory = allocatedMemoryBlock.start + totalMemoryConsumed;
while (leftOverMemory != 0) {
//
// Previous bin... size and index
//
thisBinMemorySize >>= 1;
binIndex--;
//
// This unused block fits in this bin...
//
if (leftOverMemory - thisBinMemorySize >= 0) {
//
// Register it...
//
endOfMemory -= thisBinMemorySize;
binDataSource[binIndex].push({start : endOfMemory, count : 1});
//
// Reduce the amount of left over memory...
//
leftOverMemory -= thisBinMemorySize;
leftOverMemoryAddressStartsAt += thisBinMemorySize;
}
}
}
return allocatedMemoryBlock;
}
}
}
}
return false; // failed to find any sizable blocks
}
function freeMemoryBlock(memoryBlock) {
var bits = memoryBlock.bits;
delete memoryBlock.bits;
var belongsToBin = Math.log2(bits >> 7);
FRAGMENTED_BINS_OF_BIN[belongsToBin].push(memoryBlock);
}