从围绕 2 的幂构建的嵌套数组结构中获取项目的算法

Question

我对如何在引擎盖下实现数组有一些限制。只能有两个连续元素的幂，最多 32 个元素（1、2、4、8、16、32）。因此，这对如何优化存储 7 或 15 个元素等的数组元素提出了一些限制。从 1 到 32 的示例的完整列表是 here，但接下来是一些示例：

base-3
  a
  b
  c
  null

base-5
  a
  b
  c
  tree
    d
    e

base-6
  a
  b
  c
  d
  e
  f
  null
  null

...

base-10
  a
  b
  c
  d
  e
  f
  g
  tree
    h
    i
    j
    null

...

base-13
  tree
    a
    b
    c
    d
  tree
    e
    f
    g
    h
  tree
    i
    j
    k
    l
  tree
    m

...

base-16
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  o
  p

base-17
  a
  b
  c
  d
  e
  f
  g
  h
  i
  j
  k
  l
  m
  n
  o
  tree
    p
    q

在少数情况下会选择 Null，因为与将其放入适当的树相比，仅具有 null 值所占用的 space 更少（或者使用 null 意味着更少的遍历步骤）。

在 32 处，它应该嵌套模式，如下所示：

base-33
  tree
    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
    aa
    ab
    ac
    ad
    ae
    af
  tree
    ag

tree 键只是显示它是一个链接到另一个数组的地址。

我开始实现一种算法来从下面的树系统中获取所有值。我没有找到通用的方法，所以我不必编写 32 个函数中的每一个。如果您知道 abstract/generic 的写法，那会很酷（不需要完全匹配我划分数组的方式，但它应该接近相同的想法）。但这不是主要问题。主要问题很简单 如何使这个函数对大于 32 的数组重复。 你如何使这个算法（一个 loop/iterative 算法，不使用递归）以便它可以从这样一棵树中取出多达数十亿的项目，并知道如何遍历自定义数组结构？

const map = [
  get1,
  get2,
  get3,
  get4,
  get5,
  get6,
  get7,
  get8,
  get9,
  get10,
  get11,
  get12,
  get13,
  get14,
  get15,
  get16,
  get17,
  get18,
  get19,
  get20,
  get21,
  get22,
  get23,
  get24,
  get25,
  get26,
  get27,
  get28,
  get29,
  get30,
  get31,
  get32,
]

// how to make getItems handle arrays larger than 32 in length?
function getItems(array) {
  return map[array.length](array)
}

function get1(array) {
  return [
    array[0]
  ]
}

function get2(array) {
  return [
    array[0],
    array[1],
  ]
}

function get3(array) {
  return [
    array[0],
    array[1],
    array[2],
  ]
}

function get4(array) {
  return [
    array[0],
    array[1],
    array[2],
    array[3],
  ]
}

function get5(array) {
  return [
    array[0],
    array[1],
    array[2],
    array[3][0],
    array[3][1],
  ]
}

function get6(array) {
  return [
    array[0],
    array[1],
    array[2],
    array[3],
    array[4],
    array[5],
  ]
}

function get7(array) {
  return [
    array[0],
    array[1],
    array[2],
    array[3],
    array[4],
    array[5],
    array[6],
  ]
}

function get8(array) {
  return [
    array[0],
    array[1],
    array[2],
    array[3],
    array[4],
    array[5],
    array[6],
    array[7],
  ]
}

function get9(array) {
  return [
    array[0],
    array[1],
    array[2],
    array[3],
    array[4],
    array[5],
    array[6],
    array[7][0],
    array[7][1],
  ]
}

function get10(array) {
  return [
    array[0],
    array[1],
    array[2],
    array[3],
    array[4],
    array[5],
    array[6],
    array[7][0],
    array[7][1],
    array[7][2],
  ]
}

function get11(array) {
  return [
    array[0],
    array[1],
    array[2],
    array[3],
    array[4],
    array[5],
    array[6],
    array[7][0],
    array[7][1],
    array[7][2],
    array[7][3],
  ]
}

function get12(array) {
  return [
    array[0][0],
    array[1][1],
    array[2][2],
    array[3][3],
    array[4][4],
    array[5][5],
    array[6][6],
    array[6][7],
    array[7][0],
    array[7][1],
    array[7][2],
    array[7][3],
  ]
}

一开始我就迷路了。它可以用递归来实现，也许从中我可以把它理解为命令式。

function getItemsRecursive(tree) {
  if (tree.size <= 32) {
    return map[tree.size](tree)
  }

  // ... I am lost right at the beginning.

  if (tree.size === 33) {
    return [
      ...getItemsRecursive(tree[0]),
      tree[1][0]
    ]
  } else if (tree.size === 34) {
    // ....?
  }
}

tree.size 只是伪代码。如果你愿意，你可以只做伪代码，但我在 JavaScript.

中这样做

Answer 1

在 JavaScript 中，您当然会调用 .flat(Infinity)，这将 return 完全扁平化的数组。但我会假设这些约束：

除了 push 和 pop 之外不使用数组方法（因为您的目标是自定义的、更简单的语言）
不使用递归
不使用生成器或迭代器

我希望堆栈的使用是可以接受的。然后我会想到一个堆栈，其中每个堆叠元素都包含一个数组引用和该数组中的一个索引。但是为了避免“复杂”的堆栈元素，我们也可以使用两个堆栈：一个用于数组引用，另一个用于这些数组中的索引。

为了实现“迭代”，我将使用一个回调系统，这样你就可以指定在每次迭代中应该发生什么。回调可以是console.log，这样迭代后的值就输出。

这是一个实现：

function iterate(arr, callback) {
    let arrayStack = [];
    let indexStack = [];
    let i = 0;
    while (true) {
        if (i >= arr.length || arr[i] === null) {
            if (arrayStack.length == 0) return; // all done
            arr = arrayStack.pop();
            i = indexStack.pop();
        } else if (Array.isArray(arr[i])) {
            arrayStack.push(arr);
            indexStack.push(i + 1);
            arr = arr[i];
            i = 0;
        } else {
            callback(arr[i]);
            i++;
        }
    }
}

let arr = [1, 2, 3, [4, 5]];

iterate(arr, console.log);

从围绕 2 的幂构建的嵌套数组结构中获取项目的算法

Algorithm to get items from nested array structure structured around powers of 2

arrays

algorithm

tree