Javascript: заполнить пробелы между массивами

Question

Я ищу высокопроизводительный способ нулевого заполнения значений, которые являются взаимоисключающими между двумя массивами. Эти данные предназначены для диаграммы JS, которые должны иметь записи для каждого значения x. Примером может объяснить это лучше:

До:

obj1 = [{x:1, y:1}, {x:3, y:2}]; 
obj2 = [{x:2, y:2}, {x:4, y:4}]; 

После:

obj1 = [{x:1, y:1}, {x: 2, y:0}, {x:3, y:2}, {x:4, y:0}]; 
obj2 = [{x:1, y:0}, {x: 2, y:2}, {x:3, y:0}, {x:4, y:4}]; 

Я использовал вложенные для петель, чтобы сделать это сам, но так как количество объектов & записей увеличивается, стенки время становится неприемлемо высоким. В наборе данных, который закончился нулевым заполнением до нескольких тысяч записей, время стены составляло более 10 секунд.

Я рассмотрел некоторые библиотеки JS, такие как jQuery и подчеркивание, но неясно, что для этого они выполняют более эффективные функции.

Обновление: Спасибо за все ответы. Я попробую их и помету лучший вариант в качестве ответа. Замечание о значениях x: они не обязательно монотонно возрастают (obj1 & 2 может пропустить значение x до тех пор, пока они оба). Ось X не обязательно является числом, это также могут быть даты. Надеюсь, один или несколько ответов будут адаптированы к этому.

Answer 1

В основном создайте хэш всех значений вместе с хэшем всех значений в каждом объекте. Затем заполнить объект с хэшей в «все» хэш, которые не существуют в «индивидуальном» хэш

// hash of unique x values 
var xValues = {}; 

// store each distinct x value 
walk(obj1, 'obj1'); 
walk(obj2, 'obj2'); 

// fill each array with missing values 
fill(obj1, 'obj1'); 
fill(obj2, 'obj2'); 

function walk(obj, nm){ 
    xValues[ nm ] || (xValues[ nm ] = {}); 
    xValues.all || (xValues.all = {}); 

    for(var i=0, l=obj.length; i<l; i++){ 
     xValues[ nm ][ obj[ i ].x ] = 1; 
     xValues.all [ obj[ i ].x ] = 1; 
    } 
} 

function fill(obj, nm){ 
    for(var key in xValues.all){ 
     if(!(key in xValues[ nm ])){ 
      obj.push({ x : key, y : 0 }); 
     } 
    } 
} 

Answer 2

Вот еще один способ сделать это. Использовать изначально внедренные методы в максимально возможной степени для производительности.

var obj1 = [{x:1, y:1}, {x:3, y:2}]; 
var obj2 = [{x:2, y:2}, {x:4, y:4}]; 

// get the x values from each array 
var xGetter = function(i) { return i.x; }; 
var obj1xs = obj1.map(xGetter); 
var obj2xs = obj2.map(xGetter); 

// get the joined array 
var joined = obj1.concat(obj2); 

// get all x values 
var xs = joined.map(xGetter); 

// get the min and max values of x from both arrays combined 
var min = Math.min.apply(null, xs), max = Math.max.apply(null, xs), i = min; 

// fill the missing x values with zero y value 
if(min < max) { 
    while(i<=max) { 
    if(obj1xs.indexOf(i) === -1) obj1.push({x: i, y: 0}); 
    if(obj2xs.indexOf(i) === -1) obj2.push({x: i, y: 0}); 
    i++; 
    } 
} 

// sort the arrays 
var mySorter = function(a, b) { return a.x - b.x; }; 
obj1 = obj1.sort(mySorter); 
obj2 = obj2.sort(mySorter); 

выход будет:

obj1 => [{"x":1, "y":1}, {"x":2, "y":0}, {"x":3, "y":2}, {"x":4, "y":0}] 
obj2 => [{"x":1, "y":0}, {"x":2, "y":2}, {"x":3, "y":0}, {"x":4, "y":4}] 

Answer 3

Добавление другого ответа, что делает предположение, что ваши данные предварительно отсортированы. Если он не предварительно отсортирован, сортируйте его, и это будет работать. Он имеет преимущество минимального использования памяти, очень быстро, и Ваши данные будут отсортированы, когда сделаны:

var maxX = Math.max(
     obj1[ obj1.length-1 ].x 
    , obj2[ obj2.length-1 ].x 
); 

fill(obj1, maxX); 
fill(obj2, maxX); 

function fill(obj, max){ 
    for(var i=0; i<max; i++){ 
     if(!obj[i] || (obj[i].x !== i+1)){ 
      obj.splice(i, 0, { x:i+1, y:0 }); 
     } 
    } 
} 

Answer 4

Как насчет следующего подхода (с псевдокодом)

1) преобразовать его в массив с x - индекс.

var arr = []; 
for each object in input_list 
    arr[object.x] = object.y 

2) Loop через выше массив и заполнить undefined нулями

arr2 = arr.map -> return (typeof value !== 'undefined') value : 0 

3) Преобразовать массив обратно в объект

result = arr2.map -> return { x : index, y: value } 

PS: Вы можете оптимизировать его далее, комбинируя шаги 2 и 3, чтобы сохранить другой цикл.