javascript - Fill missing numeric values in an array - Stack Overflow

admin管理员组

文章数量:1341426

Let's say I have an array [0, null, null, 3, null, null, null, 11].

I want to fill null values with numbers based on previous and next known number (and index?), so I get [0, 1, 2, 3, 5, 7, 9, 11]. What is the most efficient way to do so?

I'm thinking about something that could count nulls between two known numbers and then just get the size of one step. But these steps will be different between pairs

I'm working on a chart where some values may be missing so I have to fill possible values.

This is what I've tried, but I think it's extremely inefficient and messy. I would prefer to use ramda.js or some functional approach.

const data = [0, null, null, 3, null, null, null, 11]

const getStep = (arr, lastKnown = 0, counter = 1) => {
    const val = arr[0];

    if (val !== null) {
        return (val - lastKnown) / counter
    } else {
        return getStep(arr.slice(1), lastKnown, ++counter)
    }
}

let lastKnown = null
let currentStep = null

const filledData = data.map((x, i) => {
    if (x !== null) {
        lastKnown = x
        currentStep = null
        return x
    }
  
    if (currentStep !== null) {
        lastKnown = lastKnown + currentStep
    } else {
        currentStep = getStep(data.slice(i), lastKnown)
    }

    return currentStep + lastKnown
})

console.log(filledData)

Let's say I have an array [0, null, null, 3, null, null, null, 11].

I want to fill null values with numbers based on previous and next known number (and index?), so I get [0, 1, 2, 3, 5, 7, 9, 11]. What is the most efficient way to do so?

I'm thinking about something that could count nulls between two known numbers and then just get the size of one step. But these steps will be different between pairs

I'm working on a chart where some values may be missing so I have to fill possible values.

This is what I've tried, but I think it's extremely inefficient and messy. I would prefer to use ramda.js or some functional approach.

const data = [0, null, null, 3, null, null, null, 11]

const getStep = (arr, lastKnown = 0, counter = 1) => {
    const val = arr[0];

    if (val !== null) {
        return (val - lastKnown) / counter
    } else {
        return getStep(arr.slice(1), lastKnown, ++counter)
    }
}

let lastKnown = null
let currentStep = null

const filledData = data.map((x, i) => {
    if (x !== null) {
        lastKnown = x
        currentStep = null
        return x
    }
  
    if (currentStep !== null) {
        lastKnown = lastKnown + currentStep
    } else {
        currentStep = getStep(data.slice(i), lastKnown)
    }

    return currentStep + lastKnown
})

console.log(filledData)

// UPDATE: I've selected THIS ANSWER as correct, but If you're interested in a solution you should definitely check all answers here. There are some very interesting ideas.

• javascript
• ramda.js

Share Improve this question Follow edited Jan 21, 2018 at 15:10 BorisTB asked Jan 19, 2018 at 11:46 BorisTBBorisTB 1,81611 gold badge1919 silver badges2727 bronze badges 3

• Can you add the code (an minimal reproducible example) you've already attempted. – Andy Commented Jan 19, 2018 at 11:50
• I've added my attempt, but I'm kinda ashamed of this code :D – BorisTB Commented Jan 19, 2018 at 12:41
• 1 And what would be the expected behavior if the list started or ended with null? – Scott Sauyet Commented Jan 19, 2018 at 13:44

Add a ment  | 

7 Answers 7

Sorted by: Reset to default 3

You could iterate the array and if a null value is found, a look ahead is made for the next numbers and the gaps until the number are filled by taking a linear approach.

var array = [0, null, null, 3, null, null, null, 11],
    i = 0, j, delta;

while (i < array.length) {
    if (array[i] !== null) {
        i++;
        continue;
    }
    j = i;
    while (array[++j] === null);
    delta = (array[j] - array[i - 1]) / (j - i + 1);
    do {
        array[i] = delta + array[i - 1];
        i++;
    } while (i < j)
}

console.log(array);

ES6 with a closure over the next index with a numerical value, the real last value of the predecessor and the delta for adding for the next value if not given.

var array = [0, null, null, 3, null, null, null, 11],
    result = array.map(((j, last, delta) => (v, i, a) => {
        if (v !== null) return last = v;
        if (i < j) return last += delta;
        j = i;
        while (++j < a.length && a[j] === null) ;
        delta = (a[j] - last) / (j - i + 1);
        return last += delta;
    })());

console.log(result);

One way to do this using for loops and counting:

var skips = 0;
var last;

for (var i=0; i<arr.length; i++){
  var current = arr[i]

  if (current !== null) {

    // If there are skipped spots that need to be filled...
    if (skips > 0){

      // Calculate interval based on on skip count, and difference between current and last
      var interval = (current-arr[last])/(skips+1);

      // Fill in the missing spots in original array
      for (var j=1; j<=skips; j++){
        arr[last+j] = arr[last]+(interval*j)
      }

    }

    last = i; // update last valid index
    skips = 0; // reset skip count
  }
  // If null, just increment skip count
  else { 
    skips++
  }
}

Another approach to this is to convert your input array into a list of "segments" capturing the start value, end value and size of each segment. You can then use R.chain to build up the list with a linear step between the start and end values of each segment.

const input = [0, null, null, 3, null, null, null, 11]

// recursively convert the sparse list of numbers into a list of segments
const segmentNull = xs => {
  if (xs.length === 0) {
    return []
  } else {
    const [y, ...ys] = xs
    const count = R.takeWhile(R.isNil, ys).length + 1
    const next = R.dropWhile(R.isNil, ys)
    
    return next.length > 0
      ? R.prepend({ start: y, end: next[0], count }, segmentNull(next))
      : []
  }
}

// segmentNull(input)
//=> [{"count": 3, "end": 3, "start": 0}, {"count": 4, "end": 11, "start": 3}]

// produce a list of `count` values linearly between `start` and `end` values
const linearRange = (start, end, count) =>
  R.times(n => (end - start) * (n + 1) / count + start, count)

// linearRange(3, 11, 4)
//=> [5, 7, 9, 11]

// convert the list of segments into a list of linear values between segments
const buildListFromSegments = R.chain(({ start, end, count }) =>
  linearRange(start, end, count))

// buildListFromSegments(segmentNull(input))
//=> [1, 2, 3, 5, 7, 9, 11]
//    ^-- note the leading 0 is missing

// prepend the initial value to the result of `buildListFromSegments`
const fn = xs => R.prepend(xs[0], buildListFromSegments(segmentNull(xs)))

console.log(fn(input))

<script src="//cdnjs.cloudflare./ajax/libs/ramda/0.25.0/ramda.min.js"></script>

An O(n*m) solution where n is the count of all elements and m is the count of nulls.

Algorithm assumes there will always be valid digita at index positions 0 and length-1.

function fillInTheBlanks(a){
  var s, //step
      r = a.reduce(function([t,ns,r], e){  // [temp, nulls array, result accumulator]
                     e === null ? ns.push(e)
                                : t === void 0 ?  t = e
                                               : (s = (e-t)/(ns.length+1),
                                                  r.push(t,...ns.map((_,i) => t+(i+1)*s)),
                                                  ns = [],
                                                  t = e);
                     return [t,ns,r];
                   }, [void 0,[],[]]);
  return r[2].concat(r[0]);
}
var arr = [0, null, null, 3, null, null, null, 11],
    res = fillInTheBlanks(arr);


console.log(JSON.stringify(res));

Here is my quick solution with ramda:

const xs = [0, null, null, 3, null, null, null, 11]
const scanWithIndex = R.addIndex(R.scan)
const notNil = R.plement(R.isNil)
const mapWithIndex = R.addIndex(R.map)
const zipArrays = R.zipWith(R.concat)

// number of cons nulls for nth element
const consNulls = R.drop(1, R.scan((acc, x) => R.isNil(x) ? (acc + 1) : 0, 0, xs))

// length of ongoing null sequence for each element
const consNullsSeqLens = R.drop(1, scanWithIndex((acc, x, ind) =>{
  if (x !== 0 && acc !== 0) return acc
  const rest = R.drop(ind, consNulls)
  return R.findIndex(R.equals(0), rest)
}, 0, consNulls))

// previous non null value for each el
const prevNonNulls = R.scan((acc, x) => R.isNil(x) ? acc : x, 0, xs)

// next non null value for each el
const nextNonNulls = mapWithIndex((x, ind) => {
  const rest = R.drop(ind, xs)
  return R.find(notNil, rest)
}, xs)

// function to calculate missing values based on zipped arrays
const calculateMissingValue = ([x, seqN, seqLen, next, prev]) =>
  R.isNil(x) ? prev + (next - prev) / (seqLen + 1) * seqN : x 

R.map(
  calculateMissingValue,
  // zips 5 lists together
  zipArrays(
    zipWith(R.append, consNullsSeqLens, R.zip(xs, consNulls)),
    R.zip(nextNonNulls,prevNonNulls)
 )
)

Repl link

While the answer from @bubulik42 shows that you can use Ramda in doing this, I'm not sure Ramda is going to be much of a help. (Disclaimer: I'm one of Ramda's authors.)

My first pass at this looked like this:

const intersperseNulls = pipe(
  reduce(
    ({vals, prev, nilCount}, curr) => isNil(curr) 
       ? {vals: vals, prev: prev, nilCount: nilCount + 1} 
       : (nilCount < 1) 
         ? {vals: append(curr, vals), prev: curr, nilCount: 0}
         : {
             vals: append(curr, concat(vals, times(n => prev + (n + 1) * (curr - prev) / (nilCount + 1), nilCount))), 
              prev: curr, 
              nilCount: 0
           },
    {vals: [], prev: undefined, nilCount: 0},
  ),
  prop('vals')
);

This uses the usually-functional reduce call, but it is a somewhat odd use of it, choosing to pass state through all the iterations rather than a simple accumulator. Note how similar it looks if I remove the Ramda infrastructure:

const steps = (b, e, c) => {
  const results = []
  for (let i = 0; i < c; i++) {results.push(b + (i + 1) * (e - b) / (c + 1));}
  return results;
}

const intersperseNulls = array => array.reduce(
  ({vals, prev, nilCount}, curr) => (curr == null) 
    ? {vals: vals, prev: prev, nilCount: nilCount + 1} 
    : (nilCount < 1) 
      ? {vals: vals.concat(curr), prev: curr, nilCount: 0}
      : {
          vals: vals.concat(steps(prev, curr, nilCount)).concat(curr), 
          prev: curr, 
          nilCount: 0
        },
  {vals: [], prev: undefined, nilCount: 0},
).vals

only times was difficult to replace.

But in the end, I prefer the non-Ramda solution from @Nina Scholz. It's simpler, more easily readable, and doesn't try any trickery.

You can see these in the Ramda REPL.

To expand a little bit the question: Fill missing numeric values in an array?.

The following will fill any zero, in the most natural way, related to others numbers in the array.

To create referential scales

本文标签： javascriptFill missing numeric values in an arrayStack Overflow