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

Question

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

3

我正在寻找一种高效的方法，用于在两个数组之间互相排斥的数值进行零填充。这些数据是为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}];

我自己使用了嵌套的for循环，但随着对象和条目数量的增加，墙上时间变得不可接受高。在一个最终填充到几千个条目的数据集中，墙上时间超过了10秒。

我已经查看了一些JS库，如jQuery和underscore，但它们没有更好的执行此操作的函数。

更新：感谢所有的回应。我会尝试它们，并将表现最佳的标记为答案。关于x值的说明：它们不一定单调递增（obj1和2可以跳过x值，只要它们都这样做）。x轴不一定是数字，也可能是日期。希望其中一个或多个答案适用于此。

- pmont

4个回答

1

以下是关于编程的建议（伪代码）：

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

将数组转换回对象。

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

注意: 你可以通过将步骤2和3合并来进一步优化，以节省另一个循环。

- Chetan S

1

除非有人要求，否则请不要用咖啡代码回答，那样对不熟悉语法的人来说是不清楚的。 - user578895

2

这是伪代码（如我在回答中所提到的）。OP正在寻求指导，而不是“代码”。 - Chetan S

0

添加另一个答案，假设您的数据已经预先排序。如果没有预先排序，请对其进行排序，然后这将起作用。它具有最小的内存使用优势，速度非常快，并且在完成时您的数据将被排序：

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

- user578895

我刚意识到我发布的答案本质上与你的相同。不过，我不明白为什么你的答案会被踩。这似乎是最简单的尝试。+1 - basilikum

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

- techfoobar

1

这段代码由于 indexOf 的存在，将会和 OP 的“失败”代码有类似的性能问题。 - user578895

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user578895 · Accepted Answer

基本上，创建所有值的哈希以及每个对象中所有值的哈希。然后，在“all”哈希中填充对象，其中包含在“individual”哈希中不存在的哈希。

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