2
\$\begingroup\$

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.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Hmm, you tag this with "performance" and then for this, you pick the only solution that doesn't divide by 32 or shift by 5? \$\endgroup\$ – superb rain Sep 18 '20 at 10:39
  • \$\begingroup\$ Why do you even create that array at all? Is that you the Y to your X? \$\endgroup\$ – superb rain Sep 18 '20 at 10:45
  • \$\begingroup\$ Also, how about proper test cases? Right now, all of them can be solved with just return [i >> 5, i & 31]. \$\endgroup\$ – superb rain Sep 18 '20 at 10:51
  • \$\begingroup\$ I have no idea what you are talking about, all over my head. Please show more of what you are saying. If you already know the answer then that would be helpful, this was the best I could do, feel free to shift things around and reframe things. \$\endgroup\$ – Lance Pollard Sep 18 '20 at 10:55
  • \$\begingroup\$ 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"? This is not an attack - just an attempt to understand. \$\endgroup\$ – iAmOren Sep 24 '20 at 0:57
4
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ @Lance, if you find my answer useful, please accept it. Accepting an answer increases reputation points. Thank you. \$\endgroup\$ – iAmOren Sep 25 '20 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.