基于2幂结构的嵌套数组结构项获取算法

Question

对于如何在幕后实现数组，我有一些限制。只能有最多32个元素(1，2，4，8，16，32)的两个连续元素的幂。因此，这对如何最优地存储类似7或15个元素的数组元素等设置了一些约束。从1到32的完整示例列表是这里，但下面是一些示例：

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意味着更少的遍历步骤)。

在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个函数中的每一个。如果您知道一种抽象/通用的方法来编写这个数组，那么知道它是很酷的(不需要完全匹配我是如何划分数组的，但是它应该接近于相同的想法)。但这不是主要问题。主要问题是如何使这个函数对大于32的数组重复。如何使这个算法(一种循环/迭代算法，而不是递归)能够从这样的树中获取数十亿项，并知道如何遍历自定义数组结构？

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)，它将返回完全扁平的数组。但我假设这些约束：

• 除了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);

​