Break array into multiple arrays based on threshold

Question

I have the following graph, which is a representation of an array [2,8,12,5,3,...]. X axis is in seconds. I want to break this array into multiple parts when y values stays 0 for longer than 2 seconds. So the array in this example would break into 3 parts: x = 0 to 8, x = 8 to 13 and x = 13 to 20 because y stays = 0 for more than 2 seconds from 8 to 13. In practice this array could be huge. What would be fastest method to do this in pure javascript (or if needed lodash/underscore)? Currently I am looping through this array to mark 2 second stop times. Is there a better way of doing this?

maybe you add your code as well as some data input and wanted output. — Nina Scholz
– Nina Scholz, Commented Jul 27, 2017 at 6:32
to split the array you need both x and y... something like [{x: 0, y: 2}, ..... ] — Vanojx1
– Vanojx1, Commented Jul 27, 2017 at 7:25

Nina Scholz · Accepted Answer · 2017-07-28 06:51:44Z

2

You could use an iterative approach with one loop while checking the expected zero value and decide if the threshold is reached or not. of not, then delete the last interval and append the length to the array before.

This proposal yields

with threshold = 2:

[
    [ 1,  7],
    [ 8, 13],
    [14, 20]
]

with threshold = 7:
```
[
    [ 1, 20]
]
```

var y = [2, 8, 12, 5, 3, 2, 0, 0, 3, 4, 8, 10, 8, 10],
    x = [1, 2, 4, 5, 6, 7, 8, 13, 14, 15, 16, 18, 19, 20],
    threshold = 2,
    isZero = false;
    result = [];

y.forEach(function (a, i) {
    var last = result[result.length - 1];

    if ((a === 0) !== isZero) {
        if (last) {
            last[1] = x[i];
        }
        return;
    }
    isZero = !isZero;
    if (last && isZero && x[i] - last[0] < threshold) {
        result.pop();
        if (result[result.length - 1]) {
            result[result.length - 1][1] = x[i];
        }
        return;
    }
    result.push([x[i]]);
});

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

edited Jul 28, 2017 at 6:51

answered Jul 27, 2017 at 16:25

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

pewpewlasers Over a year ago

Great solution! But shouldn't the result be [ [ 1, 7], [ 8, 13], [14, 20] ] ? But let me check your solution carefully again.

Nina Scholz Over a year ago

you are right, i delete the answer and give you tomorrow the right answer.

pewpewlasers Over a year ago

Hi Nina, I see that you have changed your solution. But your solution is giving [ [ 1, 8 ], [ 8, 13 ], [ 13, 20 ] ] when it should be [ [ 1, 7], [ 8, 13], [14, 20] ]. I have made a fiddle based on your solution, could you please check it out? jsfiddle.net/7ymkqvLa

pewpewlasers Over a year ago

But with my fiddle I found one more error. The edge on the beginning. If the first y value is 0, new arrays ignore this value. And the edge on the end, gives one extra array. jsfiddle.net/abkrerdn

Nina Scholz Over a year ago

that is, why i always ask for data and result. please add the data to the question. in the questin, you write 0-8, 8-13, 13-20 ...

Glodenox · Accepted Answer · 2017-07-27 08:25:28Z

2

You'll always need to look at the values of the array, so you won't be able to get further than an O(n) solution. The most efficient would probably be to run through the array with a variable containing the amount of zeros you've passed through at a certain point.

The function below is a hastily made implementation of this. I've also used a variable to store the previous index. This could also be calculated from the split array, but that would be rather inefficient if you're really talking about huge arrays.

function splitArray(array, treshold) {
  var zeros = 0,
      previousIdx = 0,
      splitArrays = [];
  array.forEach(function(point, idx) {
    if (point === 0) {
      zeros++;
      if (zeros == treshold && previousIdx != idx - treshold + 1) {
        splitArrays.push(array.slice(previousIdx, idx - treshold + 1));
        previousIdx = idx - treshold + 1;
      }
    } else if (zeros >= treshold) {
      splitArrays.push(array.slice(previousIdx, idx));
      previousIdx = idx;
      zeros = 0;
    }
  });
  if (previousIdx != array.length -1) {
    splitArrays.push(array.slice(previousIdx));
  }
  return splitArrays;
}

I've created a JSFiddle that shows this function in action with some test data: https://jsfiddle.net/Glodenox/La8m3du4/2/

I don't doubt this code can still be improved though.

If you just want to get the indices of the sections instead of an array with all data in separate arrays, you can replace the three array.slice(a, b) statements with [a, b-1].

answered Jul 27, 2017 at 8:25

Glodenox

3961 gold badge2 silver badges7 bronze badges

2 Comments

pewpewlasers Over a year ago

Great concept! But my only concern is that this disregards the x values, or assumes there is y value for every x value if I am not mistaken? But it is a great work regardless and I will try to change this a bit to consider x values.

Glodenox Over a year ago

I assumed that the x values could just be the index of the array and that this was data that indeed always had data for every second based on the example given. If the input data is in the format [{x:1,y:1}, {x:2,y:6}, ...], you'd just need to adjust point to point.x. Though you'd also need to up the zeros more than just one if there are gaps in the data.

Collectives™ on Stack Overflow

Break array into multiple arrays based on threshold

2 Answers 2

5 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related