javascript - 双for循环性能问题

Question

对模糊标题表示歉意，不太确定如何描述该问题。

我最近遇到了一种情况，我必须循环遍历一个对象数组来比较多个值，我选择在 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]);
}

看到较大数组的性能非常糟糕，我想知道是否有更好的解决方案来做到这一点？

Answer 1

这是想法( Demo ):

1. 您需要某种支持 O(log n) 插入和删除操作的自平衡树。为了简单起见，我使用了红黑树。
2. 您需要使用间隔的中点作为键，即 (from + to)/2。
3. 假设您已将 k 项“插入”到树中，并且即将插入 k+1。您的步骤是:
4. 如果 k+1 覆盖根 - 忽略它。
5. 如果 k+1 被根覆盖 - 从树中删除根并再次尝试。
6. 否则，通过将 k+1 的中点与根的中点进行比较，继续查找左子树或右子树。
7. 插入所有内容后，遍历生成的树，收集每个节点。
8. 利润...我通过将其与自身连接起来使用了您的数组的 4 倍。我的机器在 Chrome 下的结果是 116 毫秒(冷启动)和 64 毫秒(预热后)。

代码

 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);
}

顺便说一句，我用过这个RBTree implementation 。不确定这是否是最好的:)