如何快速分配范围集合之间的值

使用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} 
];

注：此功能已经从目前的形式被大大简化。这是我想要做的基本理论的代表。

来源

2016-01-20 Jonathan

应该输出什么样的？ –

您可以对colA进行排序，然后使用二分搜索查找每个colB的范围内的值 - 不会是线性的，而是改善的 –

是的，这是二次方，但我很惊讶，在这个时代它只需要“大于约** 20 **值“之前”此功能需要很长时间。“这种设置中的函数调用是否涉及大量开销？ – AakashM

排序数组和非重叠范围的解决方案，显然不是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>');

来源

2016-01-20 17:58:58

这工作完美！正是我在找什么。它花费了我在OP中写出的函数将近5秒钟迭代50次。但是在这个版本中，它花了不到250ms。事实上，在我开始看到可观的增长之前，我必须将它推到100以上。非常感谢！ – Jonathan

假设值是整数，范围是合理的（不是太大）。

定义sums[x]从0到x的所有值的总和。要计算它从colA开始。对于值colA[i] - >总和[colA [i]] + = colA [i]。然后运行低谷总和并加上一切，以便它符合定义。

现在针对colB中的每个元素，value = sums[max - 1] - sums[min - 1]。（因为边界条件，-1）。

所以现在你是O（范围+ colB + colA）（或者最大的3）。

如果范围很大，您仍然可以执行相同的操作，但首先需要规范化值。这是将colA，colB.min和colB.max中的所有值排序并删除重复项，并将它们替换为已排序数组中的索引。计算无关紧要，但范围变成与colA + colB一样大的整数。

来源

2016-01-20 13:13:54 Sorin

好的，您的答案似乎可能适用，但我感觉非常愚蠢，因为我非常难以遵循逻辑。你介意写一下这个代码的样子吗？ – Jonathan

另外，对于你的假设 - 假设值是整数是安全的，但假设范围不是太大则是不安全的。实际上我正在处理UTC时间戳值，而范围实际上可能相当大。 – Jonathan

如果使用时间戳，请执行归一化。 – Sorin

不知道这是否有更好的时间复杂度，但它更“lodashy”：

_.map(colB, function(b) { 
    return _.defaults({ value: _(colA).filter(function(a) { 
     return a.point >= b.min && a.point < b.max; 
    }).sumBy('value') }, b); 
});

map()返回一个新数组，新的对象（无副作用）
defaults()用于将新的value分配给来自colB的对象。
filter()找到适合当前colB对象的colA中的对象。
sumBy()根据value属性计算总和。

来源

2016-01-20 14:21:54

肯定是更“lodashy”！然而，正如你所建议的可能是这样 - 它没有更好的时间复杂度...... – Jonathan

如何快速分配范围集合之间的值

回答

相关问题