分区N，其中零件的数量和每个零件的数量为2的幂，并且零件尺寸和数量受限制 [英] Partition N where the count of parts and each part are a power of 2, and part size and count are restricted

查看：75 发布时间：2020/9/20 21:49:13 javascript arrays algorithm math binary

本文介绍了分区N，其中零件的数量和每个零件的数量为2的幂，并且零件尺寸和数量受限制的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

如何获取代表项目列表的数字并将其划分为块，其中块的数量为2的幂，并且每个块也具有2的幂为数字(大小最大为2的最大幂，所以1，2，4，4，8，16，32，32为最大)?这有可能吗?

How do you take a number representing a list of items, and divide it into chunks, where the number of chunks is a power-of-two, AND where each chunk also has a power-of-two number of items (where size goes up to a max power of two, so 1, 2, 4, 8, 16, 32, 32 being the max)? Is this even possible?

例如，可以将8个项目分为1个桶(两个桶的幂)和8个项目(两个桶的幂):

So for example, 8 items could be divided into 1 bucket (power of two bucket) with 8 items (power of two items):

[8]

9个项目可能是:

[8, 1]

之所以可行，是因为两个数字都是2的幂，并且数组的大小是2(也是2的幂).

That works because both numbers are powers of two, and the size of the array is 2 (also a power of two).

让我们尝试11:

[8, 2, 1]

否不起作用.因为数组的大小是3，即使增加了11，也不是2的幂.

Nope that doesn't work. Because the size of the array is 3 which is not a power of two, even though it adds to 11. How about this?

[4, 4, 2, 1]

那行得通！这是4个元素，是2的幂.

That works! It's 4 elements which is a power of two.

[2, 2, 2, 1, 1, 1, 1, 1]

这也是可行的，因为有8个存储桶(8个是2的幂)，每个都有1或2个项(每个都是2的幂).但是[4, 4, 2, 1]更好，因为它更短.

That also works, since there are 8 buckets (8 is a power of two), with 1 or 2 items each (each a power of two). But [4, 4, 2, 1] is better because it's shorter.

我想(在收到评论后)会更好，尽管我第一次没有看到它:

I guess an even better one (after getting comments) would be this, though I didn't see it the first time around:

[8, 1, 1, 1]

那是短的，也以最大的数字开头.

That one is short, and also starts with the largest number.

因此，遵循此模式，以下是一些其他数字:

So following this pattern, here are some other numbers:

13:

[8, 1, 1, 1, 1, 1] // no, 6 not power of 2
[8, 2, 1, 1, 1] // no, 5 not power of 2
[8, 2, 2, 1] // yes, 4 is power of 2
[8, 4, 1] // no, 3 not power of 2

14:

[8, 2, 2, 2]

15:

[8, 4, 2, 1]

16:

[16]

18:

[16, 2]

200:

[32, 32, 32, 32, 32, 32, 4, 4]

当存储桶 tree 中存储桶的第一层的大小大于32时，它会嵌套.因此，以数字1234为例.可以用38 32表示，后跟16表示，再用4表示.

When the size of the first layer of buckets in the bucket tree grows to longer than 32, then it nests. So take the number 1234 for example. This can be represented by 38 32's followed by 16 followed by 4.

[32, 32, 32, 32, 32, 32, 32, 32,
 32, 32, 32, 32, 32, 32, 32, 32,
 32, 32, 32, 32, 32, 32, 32, 32,
 32, 32, 32, 32, 32, 32, 32, 32,
 32, 32, 32, 32, 32, 32, 16, 4]

但是现在存储桶的大小是40个项目，不是2的幂，而且大于32.因此，应该将其嵌套！ 我不太清楚这个想法，很抱歉，如果这不是一个完美的例子，我想您可以理解我的意思了.

But now the bucket size is 40 items long, which isn't a power of two AND it's greater than 32. So it should be nested! I can't quite visualize this in my head, so sorry if this isn't a perfect example, I think you can get the gist of what I mean though.

// the parent "x" is 2 in length
x = [a, b]
// child "a" is 32 in length
a = [32, 32, 32, 32, 32, 32, 32, 32,
     32, 32, 32, 32, 32, 32, 32, 32,
     32, 32, 32, 32, 32, 32, 32, 32,
     32, 32, 32, 32, 32, 32, 32, 32]
// child "b" is 8 in length
b = [32, 32, 32, 32, 32, 32, 16, 4]

再加一层，说我们有一个很大的数字(我不知道最小的最大数字是多少)，这需要另一个嵌套层.关于这一层，我们可以说的是x的长度为32，但是我们也会有一个至少为1的y.

Taken another layer up, say we have a very large number (I don't know what the minimum large number is) that requires another layer of nesting. What we can say about this layer is that, x will be 32 in length, but we will also have a y that is at least 1.

_x_ = [a, b, c, d, e, f, g, h,
       i, j, k, l, m, n, o, p,
       q, r, s, t, u, v, w, x,
       y, z, a2, b2, c2, d2, e2, f2]
_y_ = [a3]
a   = [32, 32, 32, ..., ?]
...
f2   = [32, ..., ?]

然后，当我们有了_x_，_y_，_z_，...总共32个这些时，我们会在顶部再建一层.

Then once we have _x_, _y_, _z_, ... 32 total of these, we build another layer on top.

什么是算法/方程式，需要一个数字并将其划分为所有都是2的幂(最大为32)的桶/物品大小树?

What is an algorithm/equation that will take a number and divide it into this tree of buckets / item sizes that are all powers of two, up to a max (in this case, 32)?

子目标是最大程度地减少等级数量.没有具体限制，但是我想在整个运行时中不超过100万个节点或最多10亿个节点，所以看来您可能只有3或4个级别，我不知道具体如何计算它.

A subgoal is to minimize the number of levels. There isn't a specific limit, but I am imagining no more than 1 million or very max 1 billion nodes in the entire runtime, so it seems like you'll only have 3 or 4 levels probably, I don't know exactly how to calculate it.

这将用于数组查找.从本质上讲，我是在分解一个单独的，大的，任意大小的连续"对象.排列成连续的小块，长度为2的幂，最大为32.这样可以平衡查询性能(即适合CPU缓存)和内存碎片.

This is going to be used for array lookup. Essentially I am breaking apart a single, large, arbitrarily sized "contiguous" array into small contiguous chunks with size power-of-2 up to 32 in length. This balances lookup performance (i.e. fits within cpu cache), with memory fragmentation.

更新:

我认为尝试合并以某种方式构建我要描述的嵌套树会有所帮助. 现在遗漏的最后一件事是使嵌套数组的大小正确到两个幂的值...

I think trying to incorporate this somehow to build up that nested tree I'm trying to describe will help. The last thing now missing is getting the nested arrays to be properly sized to power-of-two values...

到目前为止，我能做的最好的事情是:

The best I have been able to do so far is this:

console.log(spread(74))
console.log(spread(85))
console.log(spread(87))
console.log(spread(127))
console.log(spread(1279))
console.log(spread(12790))
console.log(spread(127901))

function spread(n) {
  if (n == 0) {
    return [0, 0, 0, 0, 0, 0]
  }
  let array = []
  let r = split(n)
  while (r[0] > 31) {
    array.push([32, 0, 0, 0, 0, 0])
    r[0] -= 32
  }
  array.push(r)
  let s = sum(r)
  if (!isPowerOf2(s)) {
    let x = pow2ceil(s)
    let i = 1
    while (i < 5) {
      if (r[i] > 1) {
        i++
        break
      }
      i++
    }
    if (i == 5) {
      i = 0
    }
    main:
    while (true) {
      while (r[i]) {
        r[i + 1] += 2
        r[i]--
        s += 1
        if (s == x) {
          break main
        }
      }
      i++
    }
  }

  if (array.length == 1) {
    return array[0]
  } else if (array.length < 33) {
    return array
  } else {
    return divide(array, 32)
  }
}

function sum(arr) {
  let i = 0
  arr.forEach(x => {
    i += x
  })
  return i
}

function split(n) {
  const r = [0, 0, 0, 0, 0, 0]
  let u = 32
  let i = 0
  while (u > 0) {
    while (n >= u) {
      r[i]++
      n -= u
    }
    i += 1
    u >>= 1
  }
  return r
}

function isPowerOf2(v) {
  return v && !(v & (v - 1))
}

function pow2floor(v) {
  var p = 1;
  while (v >>= 1) {
    p <<= 1;
  }
  return p;
}

function pow2ceil(v) {
  var p = 2
  while (v >>= 1) {
    p <<= 1
  }
  return p
}

function divide(data, size) {
  const result = []
  const upSize = data.length / size;

  for (let i = 0; i < data.length; i += size) {
    const chunk = data.slice(i, i + size);
    result.push(chunk)
  }

  if (result.length > size) {
    return divide(result, size)
  }

  return result;
}

分区N，其中零件的数量和每个零件的数量为2的幂，并且零件尺寸和数量受限制 [英] Partition N where the count of parts and each part are a power of 2, and part size and count are restricted

问题描述

推荐答案

相关文章

前端开发最新文章

热门教程

热门工具

登录关闭

分区N，其中零件的数量和每个零件的数量为2的幂，并且零件尺寸和数量受限制 [英] Partition N where the count of parts and each part are a power of 2, and part size and count are restricted

问题描述

推荐答案

相关文章

前端开发最新文章

热门教程

热门工具

登录 关闭

登录关闭