Algorithm to find bucket and item indices from power of two bins?

Question

So this is building off of Algorithm for dividing a number into largest "power of two" buckets?. Here is a slight modification of the answer from there:

let numbers = [1, 2, 3, 4, 5, 6, 7, 30, 31, 32, 33, 20, 25, 36, 50, 100, 201]
numbers.forEach(n => console.log(`${n} =`, split(n).join(', ')))

function split(number) {
  const result = [0, 0, 0, 0, 0, 0]
  let unit = 32
  let index = 5
  while (unit > 0) {
    while (number >= unit) {
      result[index]++
      number -= unit
    }
    index -= 1
    unit >>= 1
  }
  return result
}

The split function creates "power of two" buckets from an overall array of items of length n. That is, it divides a single large array into multiple small arrays. The result array is 6 items long, accounting for buckets of sizes [1, 2, 4, 8, 16, 32]. Each item in the array is how many buckets of that size need to exist.

Given that, the goal is to then take an index i, and return the bucket and bucket index where you will find that corresponding item. So for example, here are some outputs, and here is my attempt at an algorithm:

let numbers = [1, 2, 3, 4, 5, 6, 7, 30, 31, 32, 33, 20, 25, 36, 50, 100, 201]
numbers.forEach(n => {
  const [c, i] = getCollectionIndexAndItemIndex(n, 300)
  console.log(`${n} = ${c}:${i}`)
})

function getCollectionIndexAndItemIndex(i, size) {
  const parts = split(size).reverse() // assume this is memoized or something
  let j = 0
  let last = 0
  let map = [1, 2, 4, 8, 16, 32].reverse()
  let k = 0
  let bucket = 0
  main:
  while (k <= i) {
    let times = parts[j]
    while (times--) {
      let value = map[j]
      last = 0
      while (value--) {
        k++
        if (value > 0) {
          last++
        } else {
          last = 0
          bucket++
        }
        if (k == i) {
          break main
        }
      }
    }
    j++
  }

  return [ bucket, last ]
}

function split(number) {
  const result = [0, 0, 0, 0, 0, 0]
  let unit = 32
  let index = 5
  while (unit > 0) {
    while (number >= unit) {
      result[index]++
      number -= unit
    }
    index -= 1
    unit >>= 1
  }
  return result
}

That outputs this:

1 = 0:1
2 = 0:2
3 = 0:3
4 = 0:4
5 = 0:5
6 = 0:6
7 = 0:7
30 = 0:30
31 = 0:31
32 = 1:0
33 = 1:1
20 = 0:20
25 = 0:25
36 = 1:4
50 = 1:18
100 = 3:4
201 = 6:9

So basically, for index i == 1, we go to the first bucket (bucket 0), second index (i == 1), represented as 1 = 0:1. For the 32nd index i == 32, that is the 33rd item, so we fill up 1 32-item bucket, and spill over 1, so index 0 in the second bucket, represented 32 = 1:0. For index 201, equals 6:9, which you can calculate as ((32 * 6) - 1) + 10 == 192 - 1 + 10 == 201.

The problem is, this algorithm is O(n), it counts k++ for every item up to k == i. I think there might be a way to optimize this so it can do larger jumps (32, 16, 8, 4, 2, 1 jumps), and cut out a lot of the iterations, I'm just not sure how. Can you find a way to maximally optimize this to the fewest number of steps, using only primitive operations and values (i.e. not fancy array.map and such, but just low-level while or for loops, and bitwise operations)? Basically, how can you optimize the getCollectionIndexAndItemIndex operation, and also simplify it so it's easier to follow.

The size parameter is set to 300, but that is the size of the array. But it could be any size, and we would then want to find the corresponding index within that array, jumping to the appropriate bucket and offset.

Answer 1

I think your code is too complex and can be simplified.
Also, you wrote "using only primitive operations and values (i.e. not fancy array.map and such...", yet you use array.forEach. Where is the "line"?
I hope this is what you are looking for.
Note:

• up-to 32 -> one bucket
• 32 up-to 32*32 -> another bucket
• 3232 up-to 3232*32 -> another bucket
• etc.

Only after done, I got @superb rain's [i >> 5, i & 31]...
Perhaps I'll implement that in the future.
However, my code allows for "bucket-of-buckets".

The heart of my code is the recursive function:

function recBucket(number, size) {
  if(number<size) return [number];
  else {
    var whole=Math.floor(number/size);
    return [recBucket(whole, size), number-whole*size].flat();
  }
};

Here is a snippet that uses and builds on that:

var numbers = [1, 2, 3, 31, 32, 33, 100, 201, 1023, 1024, 5555];

function recBucket(number, size) {
  if(number<size) return [number];
  else {
    var whole=Math.floor(number/size);
    return [recBucket(whole, size), number-whole*size].flat();
  }
};

console.log("as is:");
numbers.forEach(n=>console.log(n+" = "+recBucket(n, 32).join(":")));

function minBuckets(number, size, buckets) {
  var result=recBucket(number, size);
  while(result.length<buckets) result.unshift(0);
  return result;
};

console.log("min 2 buckets:");
numbers.forEach(n=>console.log(n+" = "+minBuckets(n, 32,2).join(":")));

console.log("min 4 buckets:");
numbers.forEach(n=>console.log(n+" = "+minBuckets(n, 32,4).join(":")));

.as-console-wrapper { max-height: 100% !important; top: 0; }