Ytukyg

I have a file with 1,000,000 Bytes. I want to chunk 200,000 bytes of the file randomly with a min and max chunk size while ensuring all 200,000 bytes are chunked without going under the min chunk byte size.

Ex:

const min = 20000, max = 50000

const result = [[0,20000], [25000,50000], [72000,110000], ...]

I have tried to wrap my mind around this for the last half hour. No luck finding any content on the internet.

So if I understand correctly, you need to retrieve a subset of data, where the subset is broken up into blocks between a min/max size, and you to select both the offsets and block sizes at random. The trick is that you want to ensure that you dont run out of memory before the criteria is met.

Well lets start with determining the block sizes themselves. This is actually quite a difficult problem, because of the min chunk size constraint, and the need to sum exactly to some value. So you can imagine that there are N sets of possible chunk sizes to fit the desired total, where each chunk size can be any value within the constraint range. However, not every set will contain chunk sizes that adhere to the min/max constraint. I have hacked together a working example below, but beware that it brute forces a desirable answer by retrying in the event that a failed set is found.

const randInt = (min,max) => {

  return Math.floor(Math.random() * (max - min + 1) + min)

}



const getSizeArray = (min, max, total) => {

  const output = 

  var leftovers = total

  while(leftovers > max){

    const nextSize = randInt(min, max)

    output.push(nextSize)

    leftovers -= nextSize

  }

  // if the leftovers are less than min, this set is impossible

  if(leftovers < min){ return getSizeArray(min, max, total) }

  // cater to the final amount to get exact size

  if(leftovers > 0){ output.push(leftovers) }

  return output

}



const sizes = getSizeArray(20000, 50000, 200000)

console.log(sizes)

All we do here is keep choosing random sizes within the range, and taking the final value as the difference to the total constraint. I'm not exactly sure how this will effect the distribution though.

So once you have the chunk sizes, then you just need to work out the offsets. You could do this many ways, but the way I did it below tries to enforce fairly uniform gaps for the chunks. It works by splitting the mem total up by the number of chunks, and finding a range of the memory with which each chunk is free to randomly choose an offset from. For example:

const randInt = (min,max) => {

  return Math.floor(Math.random() * (max - min + 1) + min)

}



const getSizeArray = (min, max, total) => {

  const output = 

  var leftovers = total

  while(leftovers > max){

    const nextSize = randInt(min, max)

    output.push(nextSize)

    leftovers -= nextSize

  }

  // if the leftovers are less than min, this set is impossible

  if(leftovers < min){ return getSizeArray(min, max, total) }

  // cater to the final amount to get exact size

  if(leftovers > 0){ output.push(leftovers) }

  return output

}



const sizes = getSizeArray(20000, 50000, 200000)



const getOffsets = (arr, memSize) => {

  const result = 

  const sum = arr.reduce((r, i) => r + i, 0)

  const gap = (memSize - sum) / arr.length

  arr.forEach((item, i) => {

    const min = arr.reduce((r, a, index) => {

      if(index < i){

        return r + gap + a

      }

      return r

    }, 0)

    const max = min + Math.floor(gap / 2)

    const offset = randInt(min, max)

    result.push([offset, item])    

  })

  return result  

}



const result = getOffsets(sizes, 1000000)

console.log(result)

Just generate random values between 25000 and 50000, that sum up to 200000:

 const range = (min, max) => min + Math.floor(Math.random() * (max - min));



function sizes(size, min, max) {

  const sizes = ;

  let pos;

  for(pos = 0; pos < size - max;) {

    const curr = pos + range(min, Math.min(max, size - max));

    sizes.push(curr);

    pos += curr;          

  }



  sizes.push(size - pos);

  return sizes;

}

Now generate chunk sizes and the sizes of the parts between the chunks, then map them to indices:

const toChunk = range(1000000 - 200000, 1000000), 

  leftOver = 1000000 - toChunk,

  chunkSizes = sizes(toChunk, 25000, 50000),

  spaceSizes = sizes(leftOver, 0, range(10, leftOver)),

  chunks = ;



while(spaceSizes.length > chunkSizes.length + 1)

  spaceSizes.splice(range(0, spaceSizes.length), spaceSizes.pop() + spaceSizes.pop());



let start = 0;

for(const chunkSize of chunkSizes) {

chunks.push([start, start + chunkSize - 1]);

  start += chunkSize;

  start += spaceSizes.pop() || 0;

}