Javascript：填充数组之间的缺失值

我正在寻找一种高性能的方式来填充两个数组之间互斥的值。该数据适用于必须具有每个x值的条目的JS图表。一个例子可以说明这更好：Javascript：填充数组之间的缺失值

前：

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

后：我用嵌套的for循环

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轴不一定是数字，也可能是日期。希望有一个或多个答案适用于此。

来源

2014-01-18 pmont

基本上创建所有值的散列，以及每个对象中所有值的散列。然后填写与哈希对象中不中“个人”散

// 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 }); 
     } 
    } 
}

来源

2014-01-18 05:43:26

该方法将该测试数据集和CPU的零填充时间从5秒缩短到毫秒。我创建了每个数组（数据层）的所有x值的字典。我还为每个数据层创建了临时字典以加快查找速度（避免迭代数组或使用indexOf）。查找非常快：for（var in all_x_vals）{if（typeof tmp_dict [entry] =='undefined'）ZeroFillArrayEntry（）; } -----不是确切的代码，但希望得到点 – pmont

-1

这里存在的“所有”哈希是这样做的另一种方式。尽可能使用本机实施的方法来提高性能。

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}]

来源

2014-01-18 05:54:15 techfoobar

由于indexof的 –

添加另一种答案，使一个假设，即你的数据是预先排序。如果它没有预先排序，则对其进行排序，这将起作用。它有最小的内存使用情况的优势，速度非常快，并在完成后您将数据排序：

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 }); 
     } 
    } 
}

来源

2014-01-18 05:59:54

我会发现我发布的答案基本上是这样的，这会对OP的“失败”代码产生类似的性能问题与你的一样。尽管你不明白你的失望。这似乎是最简单的尝试。 +1 – basilikum

如何采取下列措施（用伪代码）

1）将其转换成一个数组x是索引。

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

2）循环经过上述阵列和填充undefined用零

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

3）转换所述阵列回对象

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

PS：可以优化它进一步通过组合步骤2和3来保存另一个循环。

来源

2014-01-18 06:22:24

请不要在coffeescript中回答，除非OP要求它...像arr.map - > return'这样的东西对于不熟悉语法的人不清楚 –

它是一个伪代码（如在我的回答中提到）。 OP正在寻求指导，而不是“teh codez”。 –

Javascript：填充数组之间的缺失值

回答

相关问题