在Javascript中创建多维数组和矩阵

Question

尝试创建一个名为mCreate()的函数，该函数接收一组数字并返回一个多维数组（矩阵）：

mCreate(2, 2, 2)    
//   [[[0, 0], [0, 0]], [[0, 0], [0, 0]]]

当此函数仅处理2层深度时，例如：mCreate(2, 2) //[[0, 0], [0, 0]]。我知道可以使用2个嵌套的for循环来处理2层深度，但问题是如何处理第n个参数。

这个问题最好用递归方法解决，否则如何动态确定需要多少个嵌套的for循环，取决于所需参数的数量？

注：最高效的方法很好，但不是必要的。

RE-EDIT - 使用Benchmark.js检查性能后，结果如下：

BenLesh x 82,043 ops/sec ±2.56% (83 runs sampled)
Phil-P x 205,852 ops/sec ±2.01% (81 runs sampled)
Brian x 252,508 ops/sec ±1.17% (89 runs sampled)
Rick-H x 287,988 ops/sec ±1.25% (82 runs sampled)
Rodney-R x 97,930 ops/sec ±1.67% (81 runs sampled)
Fastest is Rick-H

@briancavalier也提出了一个不错的解决方案JSbin:

const mCreate = (...sizes) => (initialValue) => _mCreate(sizes, initialValue, sizes.length-1, 0)

const _mCreate = (sizes, initialValue, len, index) =>
    Array.from({ length: sizes[index] }, () => 
        index === len ? initialValue : _mCreate(sizes, initialValue, len, index+1))
mCreate(2, 2, 2)(0)

- cmdv

---

你能解释一下你想要实现什么吗？ - Rajesh

@cmdv：你可以获取n个参数，然后使用一些方法来实现你想要的功能。 - Pranav C Balan

尝试复制 math.zeros(2,2,2) 但具有添加第n个值的能力。这是用于矩阵的。http://mathjs.org/docs/datatypes/matrices.html - cmdv

@RickHitchcock 它将包含1个元素。 - cmdv

@cmdv 请查看我的更新答案。 - Rajesh

Answer 1

一个简单的递归答案是这样的（使用ES2015）：

const mCreate = (...sizes) => 
    Array.from({ length: sizes[0] }, () => 
        sizes.length === 1 ? 0 : mCreate(...sizes.slice(1)));

这里是JS Bin

编辑：我认为我会将初始化器与高阶函数一起添加：

const mCreate = (...sizes) => (initialValue) => 
    Array.from({ length: sizes[0] }, () => 
        sizes.length === 1 ? initialValue : mCreate(...sizes.slice(1))(initialValue));

这可以像这样使用：

mCreate(2, 2, 2)('hi'); 
// [[["hi", "hi"], ["hi", "hi"]], [["hi", "hi"], ["hi", "hi"]]]

JSBin of that

- Ben Lesh

Answer 2

以下是一种非递归的解决方案：

function mCreate() {
  var result = 0, i;

  for(i = arguments.length - 1; i >= 0 ; i--) {
    result = new Array(arguments[i]).fill(result);
  }

  return JSON.parse(JSON.stringify(result));
}

JSON函数被用于模拟深克隆，但这会导致函数性能不佳。

function mCreate() {
  var result = 0, i;
  
  for(i = arguments.length - 1; i >= 0 ; i--) {
    result = new Array(arguments[i]).fill(result);
  }

  return JSON.parse(JSON.stringify(result));
}


console.log(JSON.stringify(mCreate(2, 2, 2)));
console.log(JSON.stringify(mCreate(1, 2, 3, 4)));
console.log(JSON.stringify(mCreate(5)));
console.log(JSON.stringify(mCreate(1, 5)));
console.log(JSON.stringify(mCreate(5, 1)));

var m = mCreate(1, 2, 3, 4);
m[0][1][1][3] = 4;
console.log(JSON.stringify(m));

- Rick Hitchcock

---

这看起来很不错，你觉得它比递归选项更高效吗？ - cmdv

哇，看起来真的很干净，而且性能也有所提升！虽然我没有期望，不过我正在运行的测试非常糟糕，而且还在 jsfiddle 上进行！ - cmdv

这个解决方案有一个小问题，一旦您开始修改生成的数组的值。对于 var x = mCreate(2, 1);，以下是正确的：x[0] === x[1]。因此，如果您执行 x[0][0] = 1；您也会得到 x[1][0] === 1。在“克隆”数组时使用 .slice() 就可以解决这个问题。 - rodneyrehm

@rodneyrehm，非常好的观点！不幸的是，.slice()只能进行浅复制，而我们需要进行深复制。我的解决方案还需要进一步完善。 - Rick Hitchcock

@RickHitchcock，你对浅拷贝的理解是正确的。但由于每次迭代都会创建一个浅拷贝，因此您将在每个级别上得到唯一的数组。如果这个问题与运行时性能无关而是与代码大小有关，您也可以在最后运行return JSON.parse(JSON.stringify(result));。 - rodneyrehm

Answer 3

递归算法可能更容易理解，但通常并不是必需的。在这种特殊情况下，迭代方法足够简单。

你的问题包含两个部分：

1. 创建一个具有可变数量的“0”值元素的数组
2. 创建之前创建的数组的可变数量的数组

下面是我认为你尝试创建的内容的实现：

function nested() {
  // handle the deepest level first, because we need to generate the zeros
  var result = [];
  for (var zeros = arguments[arguments.length - 1]; zeros > 0; zeros--) {
    result.push(0);
  }

  // for every argument, walking backwards, we clone the
  // previous result as often as requested by that argument
  for (var i = arguments.length - 2; i >= 0; i--) {
    var _clone = [];
    for (var clones = arguments[i]; clones > 0; clones--) {
      // result.slice() returns a shallow copy
      _clone.push(result.slice(0));
    }

    result = _clone;
  }

  if (arguments.length > 2) {
    // the shallowly copying the array works fine for 2 dimensions,
    // but for higher dimensions, we need to compensate
    return JSON.parse(JSON.stringify(result));
  }

  return result;
}

编写算法只是解决问题的一半，下面是测试代码，验证我们的函数是否按照我们的期望运行。通常我们会使用众多测试运行器之一（例如mocha或AVA），但由于不知道你的设置情况（如果有的话），我们将手动进行：

var tests = [
  {
    // the arguments we want to pass to the function.
    // translates to nested(2, 2)
    input: [2, 2],
    // the result we expect the function to return for
    // the given input
    output: [
      [0, 0],
      [0, 0]
    ]
  },
  {
    input: [2, 3],
    output: [
      [0, 0, 0],
      [0, 0, 0]
    ]
  },
  {
    input: [3, 2],
    output: [
      [0, 0],
      [0, 0],
      [0, 0]
    ]
  },
  {
    input: [3, 2, 1],
    output: [
      [
        [0], [0]
      ],
      [
        [0], [0]
      ],
      [
        [0], [0]
      ]
    ]
  },
];

tests.forEach(function(test) {
  // execute the function with the input array as arguments
  var result = nested.apply(null, test.input);
  // verify the result is correct
  var matches = JSON.stringify(result) === JSON.stringify(test.output);
  if (!matches) {
    console.error('failed input', test.input);
    console.log('got', result, 'but expected', rest.output);
  } else {
    console.info('passed', test.input);
  }
});

由您自己定义和处理边缘情况，例如nested(3, 0)、nested(0, 4)、nested(3, -1)或nested(-1, 2)。

- rodneyrehm

---

非常感谢您的详细解释，我将快速设置适当的性能测试，但使用Phil-plückthun的快速jsfiddle，看起来@rick-hitchcock是最优秀的 :-) https://jsfiddle.net/2v4zj76t/ - cmdv

Rick的解决方案没有克隆数组，因此产生了一个不能被改变而不带副作用的结果。如果这是个问题并且你修复了它，两个函数将会做同样的事情，性能应该是相等的。 - rodneyrehm

我更希望它克隆数组，因为我正在尝试将此函数用于我一直在编写的FP库https://github.com/Cmdv/linearJs。 - cmdv

您的解决方案还需要进行深拷贝。请参见 https://jsfiddle.net/8k5w0gvh/。应该只有一个“2”。 - Rick Hitchcock

哦，天啊。我只测试了2维的参考问题，而不是3维的。你是正确的，我已经在我的回答中加入了一个深度克隆的变通方法... - rodneyrehm

Answer 4

根据 @Pranav 的建议，您应该使用 arguments 对象。

递归 + arguments 对象

function mCreate() {
  var args = arguments;
  var result = [];
  if (args.length > 1) {
    for (var i = 1; i < args.length; i++) {
      var new_args = Array.prototype.slice.call(args, 1);
      result.push(mCreate.apply(this, new_args));
    }
  } else {
    for (var i = 0; i < args[0]; i++) {
      result.push(0)
    }
  }
  return result;
}

function print(obj) {
  document.write("<pre>" + JSON.stringify(obj, 0, 4) + "</pre>");
}
print(mCreate(2, 2, 2, 2))

- Rajesh

---

谢谢，唯一让我不太满意的就是使用apply，因为这个过程比较慢，但是我喜欢递归 :) - cmdv

Answer 5

要点是将 create 的结果作为 create 的第二个参数传递，除了最后一个（或者根据您的看法，第一个）实例：

function create(n, v) {
  let arr = Array(n || 0);
  if (v !== undefined) arr.fill(v);
  return arr;
}

create(2, create(2, 0)); // [[0,0],[0,0]]
create(2, create(2, create(2, 0))); // [[[0,0],[0,0]],[[0,0],[0,0]]]

演示

使用循环，我们可以构建数组维度：

function loop(d, l) {
  var out = create(d, 0);
  for (var i = 0; i < l - 1; i++) {
    out = create(d, out);
  }
  return out;
}

loop(2,2) // [[0,0],[0,0]]
loop(2,3) // [[[0,0],[0,0]],[[0,0],[0,0]]]
loop(1,3) // [[[0]]]

演示

- Andy