如何快速分配範圍集合之間的值

使用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

如何快速分配範圍集合之間的值

回答

相關問題