Как быстро распределить значения между коллекциями с диапазонами

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.

Array colA просто повторил. Array 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>');

Answer 2

Предполагая, что значения являются целыми числами и диапазон чувствителен (не слишком большой).

Определить sums[x] сумму всех значений от 0 до x. Чтобы вычислить его, начинайте с colA. Для значения colA[i] -> sums [colA [i]] + = colA [i]. Затем выполняйте корытовые суммы и складывайте все так, чтобы оно соответствовало определению.

Теперь для каждого элемента в colB, value = sums[max - 1] - sums[min - 1]. (-1 из-за условий на границах).

Итак, теперь вы O (диапазон + colB + colA) (или максимум 3).

Если диапазон большой, вы все равно можете сделать то же самое, но сначала нормализовать значения. Это принимает все значения в cola, colB.min и colB.max, сортирует и удаляет дубликаты и заменяет их своим индексом в отсортированном массиве. Для вычислений это не имеет значения, но диапазон становится целым числом, размером с cola + colB.

Answer 3

Не уверен, если это имеет лучшую временную сложность, но это не более «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() находит объекты от colA, которые соответствуют текущему объекту colB.
• sumBy() вычисляет сумму, исходя из свойства value.