数组的懒惰笛卡尔积（任意嵌套循环）

Question

数组的懒惰笛卡尔积（任意嵌套循环）

9

关于此问题还有其他问题在其他语言以及其他非惰性的 JavaScript版本，但我没有找到任何惰性的JavaScript版本。

给定一个由任意数量、任意大小的数组组成的数组：

var sets = [ [2,3,4,5], ['sweet','ugly'], ['cats','dogs','hogs'] ];

以及回调函数：

function holla( n, adj, noun ){
  console.log( [n,adj,noun].join(' ') );
}

有没有一种优雅的方法可以迭代整个产品空间，而不必先创建一个所有可能组合的巨大数组？

lazyProduct( sets, holla );
// 2 sweet cats
// 2 sweet dogs
// 2 sweet hogs
// 2 ugly cats
// 2 ugly dogs
// 2 ugly hogs
// 3 sweet cats
// 3 sweet dogs
// 3 sweet hogs
// 3 ugly cats
// 3 ugly dogs
// 3 ugly hogs
// 4 sweet cats
// 4 sweet dogs
// 4 sweet hogs
// 4 ugly cats
// 4 ugly dogs
// 4 ugly hogs
// 5 sweet cats
// 5 sweet dogs
// 5 sweet hogs
// 5 ugly cats
// 5 ugly dogs
// 5 ugly hogs

请注意，这些组合与嵌套循环的结果相同：

var counts     = [2,3,4,5];
var adjectives = ['sweet','ugly'];
var animals    = ['cats','dogs','hogs'];
for (var i=0;i<counts.length;++i){
  for (var j=0;j<adjectives.length;++j){
    for (var k=0;k<animals.length;++k){
      console.log( [ counts[i], adjectives[j], animals[k] ].join(' ') );
    }
  }
}

笛卡尔积的好处包括：

允许您嵌套任意数量的循环（也许您不知道要迭代多少项）
使您能够更改循环顺序（例如，首先按形容词循环），而无需编辑代码或编写所有可能的循环顺序组合。

基准测试

您可以在下面查看答案的基准测试：
http://jsperf.com/lazy-cartesian-product/26

- Phrogz

好奇：你问这个问题是为什么？ - Rob W

1

@RobW 因为我需要它，但找不到。具体来说，我的独特颜色生成器正在获得使用HSV或Lab的能力，并以任意顺序迭代这些轴（这对算法有影响），我不想手写12个不同的3层嵌套循环。现在我已经写好了，但我并不确定我的实现是否最优雅。 :) - Phrogz

1

懒惰的笛卡尔积、幂集、排列和组合在js-combinatorics模块中得到了实现：https://github.com/dankogai/js-combinatorics - Erel Segal-Halevi

4个回答

6

恰巧周末我也在研究同一件事情。我试图找到替代我的基于[].every的算法实现，结果在Firefox中表现非常糟糕（但在Chrome中表现很好——比下一个快了两倍以上）。

最终结果是http://jsperf.com/lazy-cartesian-product/19。它类似于Tomalak的方法，但只有一个参数数组，它会随着符号的移动而发生变化，而不是每次生成新的数组。

我相信使用其他算法中的聪明数学技巧可以进一步改进它。然而，我并不完全理解它们，所以我把这个工作留给别人去尝试。

编辑：实际代码与Tomalak的接口相同。我喜欢这个接口，因为它随时可以被break。它只比在函数本身内联循环略慢一点。

var xp = crossProduct([
  [2,3,4,5],['angry','happy'], 
  ['monkeys','anteaters','manatees']]);
while (xp.next()) xp.do(console.log, console);

function crossProduct(sets) {
  var n = sets.length, carets = [], args = [];

  function init() {
    for (var i = 0; i < n; i++) {
      carets[i] = 0;
      args[i] = sets[i][0];
    }
  }

  function next() {
    if (!args.length) {
      init();
      return true;
    }
    var i = n - 1;
    carets[i]++;
    if (carets[i] < sets[i].length) {
      args[i] = sets[i][carets[i]];
      return true;
    }
    while (carets[i] >= sets[i].length) {
      if (i == 0) {
        return false;
      }
      carets[i] = 0;
      args[i] = sets[i][0];
      carets[--i]++;
    }
    args[i] = sets[i][carets[i]];
    return true;
  }

  return {
    next: next,
    do: function (block, _context) {
      return block.apply(_context, args);
    }
  }
}

- monzee

非常好。我会给你 accept，因为你的速度非常快，并且在回调函数中包含了可选的上下文。为什么每次调用 next() 都要检查 args.length，而不是保证在构造时运行 init() 一次呢？ - Phrogz

如果您感兴趣，请查看我的答案，了解一种执行产品的随机惰性访问的方法。 - Phrogz

这是因为我需要第一次调用next()时不要增加最后一个插符。也可以通过在外部进行初始化并将最后一个插符设置为-1来解决此问题。但不管怎样，我看到你大大改进了第二个实现！干得好！我一直避免使用递归，因为我认为这正是减慢我的第一个算法的原因，但你的确更快！ - monzee

啊，明白了。是的，可以重复使用同一个数组来加速递归版本的执行，这个想法真的很好。 :) - Phrogz

顺便说一句，这是我的实现的几个变体的性能比较：http://jsperf.com/lazycartesianiterator/2。做得好！ - Tomalak

5

以下是我的解决方案，使用递归。我不喜欢它在第一次遍历时创建了一个空数组，也不喜欢它在for循环内部使用if（而不是将测试展开成两个循环以提高速度，代价是DRY性），但至少它有点简洁：

function lazyProduct(arrays,callback,values){
  if (!values) values=[];
  var head = arrays[0], rest = arrays.slice(1), dive=rest.length>0;
  for (var i=0,len=head.length;i<len;++i){
    var moreValues = values.concat(head[i]);
    if (dive) lazyProduct(rest,callback,moreValues);
    else      callback.apply(this,moreValues);
  }
}

实际效果演示：http://jsfiddle.net/RRcHN/

编辑：下面的版本速度更快，比上面的版本大约快了 2倍-10倍：

function lazyProduct(sets,f,context){
  if (!context) context=this;
  var p=[],max=sets.length-1,lens=[];
  for (var i=sets.length;i--;) lens[i]=sets[i].length;
  function dive(d){
    var a=sets[d], len=lens[d];
    if (d==max) for (var i=0;i<len;++i) p[d]=a[i], f.apply(context,p);
    else        for (var i=0;i<len;++i) p[d]=a[i], dive(d+1);
    p.pop();
  }
  dive(0);
}

不需要为每个递归调用创建自定义数组，而是重复使用单个数组（p）来处理所有参数。它还允许您为函数应用传递上下文参数。

编辑2：如果您需要对Cartesian乘积进行随机访问，包括执行反向迭代的能力，则可以使用以下内容：

function LazyProduct(sets){
  for (var dm=[],f=1,l,i=sets.length;i--;f*=l){ dm[i]=[f,l=sets[i].length] }
  this.length = f;
  this.item = function(n){
    for (var c=[],i=sets.length;i--;)c[i]=sets[i][(n/dm[i][0]<<0)%dm[i][1]];
    return c;
  };
};

var axes=[[2,3,4],['ugly','sappy'],['cats','dogs']];
var combos = new LazyProduct(axes);

// Iterating in reverse order, for fun and profit
for (var i=combos.length;i--;){
  var combo = combos.item(i);
  console.log.apply(console,combo);
}
//-> 4 "sappy" "dogs"
//-> 4 "sappy" "cats"
//-> 4 "ugly" "dogs"
...
//-> 2 "ugly" "dogs"
//-> 2 "ugly" "cats"

将上述内容解码后，对于数组的笛卡尔积[a,b,...,x,y,z]，第n个组合为：

[
  a[ Math.floor( n / (b.length*c.length*...*y.length*z.length) ) % a.length ],
  b[ Math.floor( n / (c.length*...*x.length*y.length*z.length) ) % b.length ],
  ...
  x[ Math.floor( n / (y.length*z.length) ) % x.length ],
  y[ Math.floor( n / z.length ) % y.length ],
  z[ n % z.length ],
]

您可以在我的网站上查看上述公式的漂亮版本：链接。

通过反向迭代集合，可以预先计算股息和模数：

var divmod = [];
for (var f=1,l,i=sets.length;i--;f*=l){ divmod[i]=[f,l=sets[i].length] }

有了这个，查找特定组合只需要映射集合即可：

// Looking for combination n
var combo = sets.map(function(s,i){
  return s[ Math.floor(n/divmod[i][0]) % divmod[i][1] ];
});

然而，就速度和正向迭代而言，建议参考被接受的答案。即使我们预先计算了股息和模数列表，使用上述技术也比那个答案慢2-4倍。

- Phrogz

5

我创建了这个解决方案：

function LazyCartesianIterator(set) {
  var pos = null, 
      len = set.map(function (s) { return s.length; });

  this.next = function () {
    var s, l=set.length, p, step;
    if (pos == null) {
      pos = set.map(function () { return 0; });
      return true;
    }
    for (s=0; s<l; s++) {
      p = (pos[s] + 1) % len[s];
      step = p > pos[s];
      if (s<l) pos[s] = p;
      if (step) return true;
    }
    pos = null;
    return false;
  };

  this.do = function (callback) { 
    var s=0, l=set.length, args = [];
    for (s=0; s<l; s++) args.push(set[s][pos[s]]);
    return callback.apply(set, args);
  };
}

它的使用方法如下：

var iter = new LazyCartesianIterator(sets);
while (iter.next()) iter.do(callback);

它似乎运行良好，但测试不够充分，如果您发现错误，请告诉我。

看看它与其他的比较：http://jsperf.com/lazy-cartesian-product/8

- Tomalak

非常有趣，感谢分享。虽然我通常不喜欢迭代器，但我喜欢使用回调函数返回值轻松停止迭代的方法。我已在 OS X 上的 Chrome / Safari / FF / Opera 上运行了测试，包括你的基准测试和一个修改后使用字符串的基准测试。不同浏览器之间的性能差异令人惊讶！ - Phrogz

@Phrogz 我认为在迭代过程中能够停止是惰性求值的全部意义。;) 无论如何，由于某种原因，在我的Firefox 9上速度非常慢，而且与之相比过于复杂。如果集合包含空数组，它也会失败。 - Tomalak

不错的方法。在Chrome中，这是所有列出方法中最快的方法。在其他所有浏览器中，它与其他方法一样快/慢。我猜当你将“do”移动到while的主体中，并将“reset”移动到“next”时（因为它仅使用一次），你的代码可以（更）快速。以良好的方式使用注释仍将保持您的代码可读性，同时消除每次迭代的两个函数调用。 - Rob W

@RobW 将 do 移动到 while 的主体中会破坏可用性。此外，重置每次迭代只调用一次，这肯定不会影响总体速度。无论如何，如果您想要改进，可能有方法可以实现。我也会再考虑一下。 - Tomalak

@RobW 我已经优化了代码，现在使用了一个适当的对象。尽管如此，它只在Chrome中运行得很快。我认为next()可以变得更加智能一些，for循环浪费了时间。 - Tomalak

显示剩余4条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rob W · Accepted Answer

递归和迭代的组合可以完成这项工作。

function lazyProduct(sets, holla) {
    var setLength = sets.length;
    function helper(array_current, set_index) {
        if (++set_index >= setLength) {
            holla.apply(null, array_current);
        } else {
            var array_next = sets[set_index];
            for (var i=0; i<array_next.length; i++) {
                helper(array_current.concat(array_next[i]), set_index);
            }
        }
    }
    helper([], -1);
}

示例: http://jsfiddle.net/nV2XU/

var sets = [ [2,3,4,5], ['sweet','ugly'], ['cats','dogs','hogs'] ];
function holla( n, adj, noun ){
  console.log( [n,adj,noun].join(' ') );
}

lazyProduct(sets,holla);