javascript - 如何在具有范围的集合之间快速分配值

Question

使用 lodash 和 javascript。我有两个集合，我试图将其中一个集合的值分配到另一个集合中的相关范围。我的最佳尝试在下面展示了如何解决这种情况，但它很快就会遇到我所了解到的时间问题，称为“quadratic complexity”。对于我的函数，一旦我开始获取大于大约 20 个值的数组，此函数就会花费大量时间。

我怎样才能更快地做到这一点？关于如何以线性方式执行此操作的任何想法？

var colA = [
    {point: 3, value: 5},
    {point: 10, value: 8},
    {point: 6, value: 18},
    {point: 12, value: 13},
    {point: 11, value: 2},
    {point: 19, value: 4},
    {point: 7, value: 2},
    {point: 8, value: 12},
];


var colB = [
    {min: 1, max: 5, value: 0},
    {min: 5, max: 10, value: 0},
    {min: 10, max: 15, value: 0},
    {min: 15, max: 20, value: 0}
];

_.forEach(colA,function(source){
    var resume = true; 
    _.forEach(colB,function(dest){

        if(resume === true && source.point >= dest.min && source.point < dest.max){
            dest.value += source.value;
            resume = false;
        }
    });
}); 

==== 输出 ====

var colB = [
    {min: 1, max: 5, value: 5},
    {min: 5, max: 10, value: 32},
    {min: 10, max: 15, value: 23},
    {min: 15, max: 20, value: 4}
];

注意:此函数已从当前形式大大简化。这代表了我正在尝试做的事情的基本理论。

Answer 1

排序数组和非重叠范围的解决方案，显然不适用于 lodash。

数组 colA 只是迭代。数组 colB 与正确范围的索引一起使用。当这个数组被排序时，下一个合适的范围是在实际的元素或者在后面的元素。如果索引位于正确位置或数组末尾，则 while 循环结束。以下检查查看元素是否存在以及值是否大于或等于最小范围。

var colA = [{ point: 3, value: 5 }, { point: 10, value: 8 }, { point: 6, value: 18 }, { point: 12, value: 13 }, { point: 11, value: 2 }, { point: 19, value: 4 }, { point: 7, value: 2 }, { point: 8, value: 12 }, ],
    colB = [{ min: 1, max: 5, value: 0 }, { min: 5, max: 10, value: 0 }, { min: 10, max: 15, value: 0 }, { min: 15, max: 20, value: 0 }];

colA.sort(function (k, l) { return k.point - l.point; });
colB.sort(function (k, l) { return k.min - l.min || k.max - l.max; });

colA.reduce(function (i, aa) {
    while (i < colB.length && aa.point > colB[i].max) {
        i++;
    }
    if (colB[i] && colB[i].min <= aa.point) {
        colB[i].value += aa.value;
    }
    return i;
}, 0);

document.write('<pre>' + JSON.stringify(colB, 0, 4) + '</pre>');