文章/答案/技术大牛

发布

社区首页 >问答首页 >如何有效地将预定义大小的大块分割为小块，这些块是影响JavaScript大小的因素？

问如何有效地将预定义大小的大块分割为小块，这些块是影响JavaScript大小的因素？
EN

Stack Overflow用户

提问于 2021-02-18 04:02:51

回答 2查看 253关注 0票数 6

假设我们有这样的结构：

// 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中的每个bin都持有一组节点，表示内存中的槽。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启动时，只有顶部的回收站有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_OF_BINS中获得1256个价值，我们就会不断上升，直到我们到达顶端，才能找到任何价值。然后我们迭代地划分。从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

问题是，如何有效地实施这一目标？对我来说，这是非常令人困惑和困难的。

如果不存在，则尝试从父类取取并将其分成两部分。如果父级没有parent.

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预先分配了一堆块，所以当它没有找到任何块时，它就会批量地分配，作为一种优化。理想情况下，它不需要创建任何其他临时数组就可以做到这一点。

我一直在想：

降低下一个级别。
我们还剩下多少？
降低下一个级别。
我们还剩下多少？

F 232

以一种更递归的方式尝试，我仍然停留在同一点上：

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
        }
      }
    }
  }
}

这就好像它必须在每个列表中的第一项，然后第二项，等等，所以它只划分它需要的第一项。

回答 2

Stack Overflow用户

回答已采纳

发布于 2021-02-23 04:44:25

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 = 0; 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 enoughMemory = thisBinMemorySize >= bits;


            if (!enoughMemory) {
                //
                // This bin is too small, but it may have continuous blocks, so lets find a continuous block big enough to accomodate the size we want...
                //
                for (var b = 0; b < bin.length; b++) {
                    var blockOfInterest = bin[b];
                    var blockSize = blockOfInterest.count * thisBinMemorySize;
                    //
                    // We've found a continous block in the lower size bin that fits the amount we want
                    //
                    if (blockSize >= bits) {
                        //
                        // We are going to return this block
                        //
                        var allocatedMemoryBlock = {start : blockOfInterest.start, count : 1};
                        //
                        // Perfect size, we are simply going to delete the whole block
                        //
                        if (blockSize == bits) {
                            bin.splice(b);
                        }
                        else {
                            //
                            // Otherwise we'll take what we need and adjust the count and adjust the start address
                            //
                            blockOfInterest.start += bits;
                            blockOfInterest.count -= bits / thisBinMemorySize; // because we are working in power of 2 we'll never get remainder
                        }

                        return allocatedMemoryBlock;
                    }
                }
                //
                // Failed to find a block big enough so keep searching
                //
            }
            else {
                //
                // This big enough even with just 1 block...
                //
                console.log(thisBinMemorySize);

                //
                // We are going to return this block
                //
                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...
}

console.log("Memory returned:", allocate((128 << 1)));
for (i = 0; i < BIN_OF_BINS.length; i++) {
    console.log(JSON.stringify(BIN_OF_BINS[i]));
}

分配4096x128块

//
// Allocate 524288 bytes...
//
var memorySize = 128 << 12; 
var memoryAllocated = allocate(memorySize); 

// Adjust the count to 524288 / 128 to give 4096 blocks of 128
memoryAllocated.count = (memorySize / 128);

// Put the allocated memory back on the BIN_OF_BINS stack
BIN_OF_BINS[0].push(memoryAllocated);


for (i = 0; i < BIN_OF_BINS.length; i++) {
    console.log(JSON.stringify(BIN_OF_BINS[i]));
}

添加了

下面的版本非常类似于第一个版本，只是它不经过较小的回收箱。

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...
}

票数 1

Stack Overflow用户

发布于 2021-02-22 23:39:29

一种无需递归的方法是“遵循”降序块。因此，您循环起来，直到找到一个具有块的父级(idx将增加)，然后向下循环，直到您到达子节点(idx将减少)。

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
]

function blockCount(binNumber) {
    return BIN_OF_BINS[binNumber].length
}

function totalBlockCount(binNumber) {
    let count = 0
    for (let idx = 0; idx < blockCount(binNumber); idx++) {
        count += BIN_OF_BINS[binNumber][idx].count
    }
    return count
}

function noBlocks(binNumber) {
    return blockCount(binNumber) === 0
}

function bitsPerBlock(binNumber) {
    return 2 ** (binNumber + 7)
}

function largestBlockIdx(binNumber) {
    if (noBlocks(binNumber)) {
        return -1
    }
    let largestIdx = 0
    for (let idx = 1; idx < blockCount(binNumber); idx++) {
        if (BIN_OF_BINS[binNumber][idx].count > BIN_OF_BINS[binNumber][largestIdx].count) {
            largestIdx = idx
        }
    }
    return largestIdx
}

function lastBlockIdx(binNumber) {
    return blockCount(binNumber) - 1
}

function descendBlock(binNumber) {
    // attempt to descend a block to the next bin, return true if successful and false otherwise

    let largestIdx = largestBlockIdx(binNumber)
    if (largestIdx < 0 || binNumber == 0) {
        return false
    }

    BIN_OF_BINS[binNumber][largestIdx].count--
    BIN_OF_BINS[binNumber][largestIdx].start += bitsPerBlock(binNumber)

    if (BIN_OF_BINS[binNumber][largestIdx].count == 0) {
        // we cab safely reset here because we know that it was the biggest and now it has no blocks
        BIN_OF_BINS[binNumber] = []
    }


    // count = 2 because a block from the next highest bin is always twice the size of the block from the current bin
    let lastIdx = lastBlockIdx(binNumber - 1)
    if (lastIdx < 0) {
        BIN_OF_BINS[binNumber - 1][0] = { start: 0, count: 2}
    } else {
        BIN_OF_BINS[binNumber - 1][lastIdx].count += 2
    }

    return true
}

function descendAllBlocks(binNumber) {
    while (descendBlock(binNumber));
}

function allocate(binNumber, minBlockCount) {
    while (totalBlockCount(binNumber) < minBlockCount) {
        // allocate to the binNumber bin from its earliest parent, cascading allocations down the chain if required
        // conceptually, we are looping in two directions - up until we find a bin that can descend a block, then back down
        // as we descend it
        for (let binIndexA = binNumber + 1; binIndexA < BIN_OF_BINS.length; binIndexA++) {
            if (descendBlock(binIndexA)) {
                for (let binIndexB = binIndexA - 1; binIndexB > binNumber; binIndexB--) {
                    descendAllBlocks(binIndexB) // to achieve the example result
                    // descendBlock(binIndexA) // take only what you need, leaving behind 1 block in each bin
                }
                break
            }
        }
    }
}


allocate(1, 1)
console.log(BIN_OF_BINS)
/*
[
  [],
  [ { start: 0, count: 16384 } ],
  [],
  [],
  [],
  [],
  [],
  [],
  [],
  [],
  [],
  [],
  [],
  [],
  [],
  [ { start: 4194304, count: 99 } ]
]
*/

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/66253424

复制

相似问题

问如何有效地将预定义大小的大块分割为小块，这些块是影响JavaScript大小的因素？
EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何有效地将预定义大小的大块分割为小块，这些块是影响JavaScript大小的因素？EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何有效地将预定义大小的大块分割为小块，这些块是影响JavaScript大小的因素？
EN