V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐关注
Meteor
JSLint - a JavaScript code quality tool
jsFiddle
D3.js
WebStorm
推荐书目
JavaScript 权威指南第 5 版
Closure: The Definitive Guide
hoythan
V2EX  ›  JavaScript

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

  •  
  •   hoythan · 2018-06-09 10:58:59 +08:00 · 4844 次点击
    这是一个创建于 2358 天前的主题,其中的信息可能已经有所发展或是发生改变。
    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);
    

    还有更好的办法吗?

    第 1 条附言  ·  2018-06-09 14:00:11 +08:00

    @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

    30 条回复    2018-06-09 16:45:18 +08:00
    yemenchun1
        1
    yemenchun1  
       2018-06-09 11:09:14 +08:00 via iPhone
    js 不懂,但理论上,从后往前生成中间结果,保存成表,如 case2 的 ddff,ddgg,ddhh,再用第一个 array 中的元素连接它,可以节约一些时间。
    notreami
        2
    notreami  
       2018-06-09 11:29:43 +08:00
    难道我感觉错误,这才几个值,超过 50ms,都觉得奇怪
    hoythan
        3
    hoythan  
    OP
       2018-06-09 11:30:29 +08:00
    @notreami 有 42 万个结果呢。
    Chingim
        4
    Chingim  
       2018-06-09 11:40:26 +08:00
    题目链接发一下?不然很难评估提出来的方案的耗时
    hoythan
        5
    hoythan  
    OP
       2018-06-09 11:41:18 +08:00
    @Chingim 上面面的就是题目提供的所有内容了。我这边提供的两个是两个不同思路的解决方案和耗时。
    Chingim
        6
    Chingim  
       2018-06-09 11:45:06 +08:00
    @hoythan 漏看了最后一段, 好尴尬
    misaka19000
        7
    misaka19000  
       2018-06-09 11:45:08 +08:00
    这不是算矩阵的乘积嘛
    hoythan
        8
    hoythan  
    OP
       2018-06-09 11:46:03 +08:00
    @misaka19000 有更好的思路吗通过 js
    whileFalse
        9
    whileFalse  
       2018-06-09 11:51:05 +08:00
    有啊,使用代理,也就是不实际生成数组。
    hoythan
        10
    hoythan  
    OP
       2018-06-09 12:00:30 +08:00
    @whileFalse 大哥给个路子?
    jatai
        11
    jatai  
       2018-06-09 12:23:10 +08:00 via Android
    用系统内置函数 forEach 就比自己写 for 快不少,教程上是这么说的 😄
    lonhongg
        12
    lonhongg  
       2018-06-09 12:55:04 +08:00   ❤️ 1
    顺手写了个 望赐教.
    ```
    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
        13
    lonhongg  
       2018-06-09 13:01:52 +08:00
    接上条 不会贴代码-,-
    思路是每次取参数的前两个数组进行 map 后生成 res,比如[1,2][3,4][5,6] 第一次 res=[13,14,23,24]
    然后用这个 res 和剩下的参数[5,6]进行递归,最终参数 length 不大于 2 后返回 res
    yung
        14
    yung  
       2018-06-09 13:18:56 +08:00 via Android
    @hoythan 大概是类似懒加载的思路吧,只在迭代或者 get 的时候生成具体的值
    shiyouming91
        15
    shiyouming91  
       2018-06-09 13:19:56 +08:00   ❤️ 1
    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
        16
    hoythan  
    OP
       2018-06-09 13:55:33 +08:00   ❤️ 1
    @jatai 循环中效率最高的应该是 for(var i = 0,len = arr.length; i < len; i++) 别人的测试结果
    hoythan
        17
    hoythan  
    OP
       2018-06-09 13:57:43 +08:00
    @lonhongg 这个和我第一个效率差不多
    @shiyouming91 哇,这个真的快!!!!!
    billgreen1
        18
    billgreen1  
       2018-06-09 14:05:20 +08:00
    ~~~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
        19
    hoythan  
    OP
       2018-06-09 14:08:49 +08:00
    @billgreen1 400-600ms
    xiangyuecn
        20
    xiangyuecn  
       2018-06-09 14:21:49 +08:00
    ```
    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
        21
    hoythan  
    OP
       2018-06-09 14:23:55 +08:00
    @xiangyuecn chrome 调试工具自带数据结果缓存的。
    hoythan
        22
    hoythan  
    OP
       2018-06-09 14:24:49 +08:00
    @xiangyuecn 我这边跑起来 150 - 200 左右
    xiangyuecn
        23
    xiangyuecn  
       2018-06-09 14:29:56 +08:00
    @hoythan 原来如此,怪不得以前测试速度经常飘来飘去,我去耍耍研究一下
    glacer
        24
    glacer  
       2018-06-09 15:24:42 +08:00
    笛卡尔积,MySQL 的 Nested Loop Join 了解一下
    whileFalse
        25
    whileFalse  
       2018-06-09 15:35:49 +08:00   ❤️ 1
    baelish
        26
    baelish  
       2018-06-09 15:37:03 +08:00
    ```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
        27
    RqPS6rhmP3Nyn3Tm  
       2018-06-09 15:41:17 +08:00 via iPad
    用 C 的指针写,然后上 WebAssembly
    Exin
        28
    Exin  
       2018-06-09 15:44:18 +08:00
    我来一个简短好读一点的:

    ```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
        29
    yichinzhu  
       2018-06-09 15:59:54 +08:00   ❤️ 1
    hoythan
        30
    hoythan  
    OP
       2018-06-09 16:45:18 +08:00
    @yichinzhu 100 - 150 左右我这里
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2759 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 12:09 · PVG 20:09 · LAX 04:09 · JFK 07:09
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.