为循环性能问题加倍

woutr_be 发表于 Dev

woutr_be

对模糊的标题表示歉意，还不确定是否还能用其他方式来描述问题。

我最近遇到一种情况，我必须遍历对象数组以比较多个值，因此我选择在for循环中使用for循环来比较每个对象与其他每个对象。

尽管这在小型阵列上可以正常工作，但是一旦我的阵列变大（例如10,000个对象），性能就会成为一个大问题。

此数组包含以下类型的对象：

[{ char: '_', from: 0, to: 2, chrLength: 2 },
{ char: '_', from: 0, to: 7, chrLength: 7 },
{ char: 'a', from: 1, to: 3, chrLength: 2 },
{ char: 'a', from: 1, to: 6, chrLength: 5 },
{ char: '_', from: 2, to: 7, chrLength: 5 },
{ char: 'a', from: 3, to: 6, chrLength: 3 }]

我的想法是，我只能选择from和to之间不与任何其他对象重叠的对象。（from并且to是另一个数组中的索引）

因此，对于示例数组，可能的结果将是：

[{ char: '_', from: 0, to: 2, chrLength: 2 },
 { char: 'a', from: 1, to: 3, chrLength: 2 },
 { char: 'a', from: 1, to: 6, chrLength: 5 },
 { char: 'a', from: 3, to: 6, chrLength: 3 }]

我的处理方式如下：

var canUse = true,
    posibilities = [];
for(i = 0; i < l; i++) {
    canUse = true;
    for(var j = 0; j < l; j++) {
        if((results[i].from < results[j].from && results[i].to > results[j].to)) {
            canUse = false;
            break;
        }
    }

    if(canUse) posibilities.push(results[i]);
}

看到较大的阵列的性能非常糟糕，我想知道是否有更好的解决方案？

尤里·塔拉班波（Yury Tarabanko）

这是想法（Demo）：

您需要某种自平衡树来支持O（log n）的插入和删除操作。为了简单起见，我使用了红黑树。
您需要使用间隔的中点作为键，即(from + to)/2。
假设您已经将k项目“插入”到树中并准备插入k+1。您的步骤是：
如果k+1覆盖根-忽略它。
如果k+1根目录覆盖了-从树中删除根目录，然后再尝试一次。
否则，通过比较k+1的中部和根的中部，继续到左或右子树。
插入所有内容后，遍历生成的树，收集每个节点。
利润...通过将其自身隐藏起来，我已经使用了4倍的阵列。我的计算机在Chrome下的结果是116ms（冷启动）和64ms（预热后）。

码

 function process() {
    console.log('Processing results of length: ' + l);

    console.time('Processing');

    var comparator = function(a, b) { //Comparator to build a tree
           return a.mid - b.mid;
        },
        isAinB = function(a, b) { //util function to check if a is inside b
            return b.from < a.from && b.to > a.to;    
        },
        rbtree = new RBTree(comparator), //Build an empty tree
        i = results.length - 1, item, posibilities = [];

    function check(root, x) { //Recursive checker
        var data;        

        if(!root) { //Either tree is empty or we've reached a leaf
            rbtree.insert(x);
            return;
        }

        data = root.data;

        if(isAinB(data, x)) { //4
            return;    
        }
        if(isAinB(x, data)) { //5
            rbtree.remove(data);
            check(rbtree._root, x);
            return;
        }    

        check(root[comparator(data, x) > 0 ? 'left' : 'right'], x); //6
    }

    for(; i >= 0; i--) { 
        item = results[i];
        item.mid = (item.from + item.to)/2; //2
        check(rbtree._root, item); //3
    }

    rbtree.each(function(item) { //7
        posibilities.push(item);
    });
    console.timeEnd('Processing');

    console.log(posibilities.length);
}