这道 JS 题目最快的办法是什么？

[hoythan]

use case1:
Input:['aa','bb','cc'],['dd','ee']
Output:["aadd", "aaee", "bbdd", "bbee", "ccdd", "ccee"]

use case2:
Input:['aa','bb','cc'],['dd','ee'],['ff','gg','hh']
Output:["aaddff", "aaddgg", "aaddhh", "aaeeff", "aaeegg", "aaeehh", "bbddff", "bbddgg", "bbddhh", "bbeeff", "bbeegg", "bbeehh", "ccddff", "ccddgg", "ccddhh", "cceeff", "cceegg", "cceehh"]

输入参数不定

方式 1 大概 250 - 300ms:

var mergeArr = (...args) => {
	
	const mergeString = (a,b) => {
		var s = '';

		for (var i = 0 , len = b.length; i < len; i++){
			if(i !== 0) s += ',';
			s += a.join(b[i] + ',') + b[i];
		}
		
		var arr = s.split(',');
		return arr;
	}

	var arrs = Array.apply(null, args);

	var arrData = arrs[0];
	for (var i = 1,len = arrs.length ; i < len; i++)
		arrData = mergeString(arrData,arrs[i]);

	// console.log(arrData);
};

方式 2 180 - 250 ms

function all() {
    var pro = ''
    for (var i = 0; i < arguments.length; i++) {
        var obj = JSON.stringify(arguments[i]);
        if(i !== arguments.length-1){
            pro = pro + `
                var outArr = []
                function p${i}(str) {
                    for (var i = 0; i < ${obj}.length; i++) {
                        var obj = str + ${obj}[i];
                        p${i+1}(obj)
                    }
                };`
        }else{
            pro = pro + `
                function p${i}(str) {
                    for (var i = 0; i < ${obj}.length; i++) {
                        var obj = str + ${obj}[i];
                        outArr.push(obj)
                    }
                };
                p0('')
                console.log(outArr)
                `
            eval(pro)

        }
    }
}

测试数据：

var time = new Date().getTime();
// mergeArr(['aa','bb','cc'],['dd'],['ee','ff']);
mergeArr(['aa','bb','cc'],['dd','ee'],['ff','gg','hh'],['dd','ee'],['ff','gg','hh'],['dd','ee'],['ff','gg','hh'],['dd','ee'],['ff','gg','hh'],['dd','ee'],['ff','gg','hh'],['ff','gg','hh'],['dd','ee'],['ff','gg','hh']);
console.log(new Date().getTime() - time);

还有更好的办法吗？

@shiyouming91

function mergeArr() { 
	var output = []; 
	doMerge(arguments, 0, "", output); 
	return output; 
} 
function doMerge(data, depth, prev, output) { 
	if(depth == data.length) { 
		output.push(prev); 
	} else { 
		let curr = data[depth]; 
		for (let i = 0; i < curr.length; i++) { 
			doMerge(data, depth + 1, prev + curr[i], output); 
		} 
	} 
}
var time = new Date().getTime();
mergeArr(['aa','bb','cc'],['dd','ee'],['ff','gg','hh'],['dd','ee'],['ff','gg','hh'],['dd','ee'],['ff','gg','hh'],['dd','ee'],['ff','gg','hh'],['dd','ee'],['ff','gg','hh'],['ff','gg','hh'],['dd','ee'],['ff','gg','hh']);
console.log(new Date().getTime() - time);

这个真的快，不用情况浏览器调试缓存，最快99ms

[yemenchun1]

js 不懂，但理论上，从后往前生成中间结果，保存成表，如 case2 的 ddff，ddgg，ddhh，再用第一个 array 中的元素连接它，可以节约一些时间。

[notreami]

难道我感觉错误，这才几个值，超过 50ms，都觉得奇怪

[hoythan]

@notreami 有 42 万个结果呢。

[Chingim]

题目链接发一下？不然很难评估提出来的方案的耗时

[hoythan]

@Chingim 上面面的就是题目提供的所有内容了。我这边提供的两个是两个不同思路的解决方案和耗时。

[Chingim]

@hoythan 漏看了最后一段， 好尴尬

[misaka19000]

这不是算矩阵的乘积嘛

[hoythan]

@misaka19000 有更好的思路吗通过 js

[whileFalse]

有啊，使用代理，也就是不实际生成数组。

[hoythan]

@whileFalse 大哥给个路子？

[jatai]

用系统内置函数 forEach 就比自己写 for 快不少，教程上是这么说的 😄

[lonhongg]

顺手写了个 望赐教.
```
function fn(...arr) {
let x = arr
const res = []
x[0].map(i => {
x[1].map(j => {
res.push(i+j)
})
})
if (x.length > 2) {
x = x.splice(2)
return fn(res, ...x)
} else {
return res
}
}
fn(['a','b'],['A','B'],['x','y'],[1,2])
// ["aAx1", "aAx2", "aAy1", "aAy2", "aBx1", "aBx2", "aBy1", "aBy2", "bAx1", "bAx2", "bAy1", "bAy2", "bBx1", "bBx2", "bBy1", "bBy2"]
```

[lonhongg]

接上条 不会贴代码-，-
思路是每次取参数的前两个数组进行 map 后生成 res，比如[1,2][3,4][5,6] 第一次 res=[13,14,23,24]
然后用这个 res 和剩下的参数[5,6]进行递归，最终参数 length 不大于 2 后返回 res

[yung]

@hoythan 大概是类似懒加载的思路吧，只在迭代或者 get 的时候生成具体的值

[shiyouming91]

function mergeArr() {
var output = [];
doMerge(arguments, 0, "", output);
return output;
}

function doMerge(data, depth, prev, output) {
if(depth == data.length) {
output.push(prev);
} else {
let curr = data[depth];
for (let i = 0; i < curr.length; i++) {
doMerge(data, depth + 1, prev + curr[i], output);
}
}
}

经典递归实现，在我的电脑上大概 120-150ms

[hoythan]

@jatai 循环中效率最高的应该是 for(var i = 0,len = arr.length; i < len; i++) 别人的测试结果

[hoythan]

@lonhongg 这个和我第一个效率差不多
@shiyouming91 哇，这个真的快！！！！！

[billgreen1]

~~~javascript

function product() {
var args = Array.prototype.slice.call(arguments); // makes array from arguments
return args.reduce(function tl (accumulator, value) {
var tmp = [];
accumulator.forEach(function (a0) {
value.forEach(function (a1) {
tmp.push(a0.concat(a1));
});
});
return tmp;
}, [[]]);
}

console.log(product([1], [2, 3], ['a', 'b']));

~~~

[hoythan]

@billgreen1 400-600ms

[xiangyuecn]

```
function run(list){
var rtv=[""];
for(var i=0;i<list.length;i++){
rtv=create(list[i],rtv);
};
return rtv;
};
function create(list,src){
var rtv=[];
for(var i=0,l1=src.length,l2=list.length;i<l1;i++){
for(var j=0;j<l2;j++){
rtv.push(src[i]+list[j]);
};
};
return rtv;
};

console.time(1);
console.log(run([['aa','bb','cc'],['dd','ee'],['ff','gg','hh'],['dd','ee'],['ff','gg','hh'],['dd','ee'],['ff','gg','hh'],['dd','ee'],['ff','gg','hh'],['dd','ee'],['ff','gg','hh'],['ff','gg','hh'],['dd','ee'],['ff','gg','hh']]).length);
console.timeEnd(1);
```


非递归，第一次写了两个函数
测试 chrome41 古董首次执行 150ms，第二次以后 70-92ms
chrome55 首次 109ms，第二次以后 50-60ms

不知道为什么第一次运行会慢一倍，编译吗？


------------
第二次把第二个函数去掉了，其实没有必要要第二个函数，发现比第一次写的慢一点，chrome 内核的执行方式完全不符合可想而知的常理（滑稽

[hoythan]

@xiangyuecn chrome 调试工具自带数据结果缓存的。

[hoythan]

@xiangyuecn 我这边跑起来 150 - 200 左右

[xiangyuecn]

@hoythan 原来如此，怪不得以前测试速度经常飘来飘去，我去耍耍研究一下

[glacer]

笛卡尔积，MySQL 的 Nested Loop Join 了解一下

[whileFalse]

@hoythan https://gist.github.com/Just4test/47fae6e447bbc1e8dec00f3dbf60f3df

用 nodejs 8.11.2 跑过。

[baelish]

```javascript
function mergeArr(...args) {
return args.reduceRight((sum, items, i)=>{
let tt = [];
items.forEach(a=>{
sum.forEach(b=>{
tt.push(a+""+b);
})
})
return tt;
}, [""]);
}
```

[RqPS6rhmP3Nyn3Tm]

用 C 的指针写，然后上 WebAssembly

[Exin]

我来一个简短好读一点的：

```js
function mergeArr(...groups) {
const results = []
~(function merge(prefix, nextGroup, ...groups) {
if (nextGroup) nextGroup.forEach(word => merge(prefix + word, ...groups))
else results.push(prefix)
})('', ...groups)
return results
}
```

性能比楼主 append 的那一版略低一点点，但如果把 forEach 换成 for 就几乎一样了

[yichinzhu]

https://pastebin.com/GdU8EHNf
应该不慢

[hoythan]

@yichinzhu 100 - 150 左右我这里