What would be an efficient algo in JavaScript to merge date time series?

SkyWalker
June 26, 2023
148 views
3 votes
3 Answers

I have the following time series list as input:

const ts1 = [
  ['2023-01-20', 1],
  ['2023-01-21', 2],
  ['2023-01-22', 3],
  ['2023-01-23', 4],
];

const ts2 = [
  ['2023-01-18', 5],
  ['2023-01-19', 6],
  ['2023-01-20', 7],
  ['2023-01-21', 8]
];

const ts3 = [
  ['2023-01-21', 9],
  ['2023-01-22', 10],
  ['2023-01-23', 11],
  ['2023-01-24', 12]
];

I’d like the output to be the merged (column stacked) version like so:

const output = [
  ['2023-01-18', null,    5, null],
  ['2023-01-19', null,    6, null],
  ['2023-01-20',    1,    7, null],
  ['2023-01-21',    2,    8,    9],
  ['2023-01-22',    3, null,   10],
  ['2023-01-23',    4, null,   11],
  ['2023-01-24', null, null,   12]
];

To give a bit more context, I’m reusing a REST API which provides the individual time-series and I need to compile the AnyChart required tableData format.

Answers

I’d go with something like

const merged = {};

let tses = [ts1, ts2, ts3];
for (let i = 0; i < tses.length; i++) {
  for (const [t, v] of tses[i]) {
    if (!merged[t]) merged[t] = new Array(tses.length).fill(null);
    merged[t][i] = v;
  }
}

console.log(Object.entries(merged).map(([t, vs]) => [t, ...vs]));

This outputs

[
  [ '2023-01-20', 1, 7, null ],
  [ '2023-01-21', 2, 8, 9 ],
  [ '2023-01-22', 3, null, 10 ],
  [ '2023-01-23', 4, null, 11 ],
  [ '2023-01-18', null, 5, null ],
  [ '2023-01-19', null, 6, null ],
  [ '2023-01-24', null, null, 12 ]
]

as expected.

For sorted order (since the keys are lexicographically sortable), do

console.log(Object.keys(merged).sort().map(key => [key, ...merged[key]]));

instead:

[
  [ '2023-01-18', null, 5, null ],
  [ '2023-01-19', null, 6, null ],
  [ '2023-01-20', 1, 7, null ],   
  [ '2023-01-21', 2, 8, 9 ],      
  [ '2023-01-22', 3, null, 10 ],  
  [ '2023-01-23', 4, null, 11 ],
  [ '2023-01-24', null, null, 12 ]
]

An alternative method with Array#reduce and nullish coalescing assignment:

const ts1=[["2023-01-20",1],["2023-01-21",2],["2023-01-22",3],["2023-01-23",4],],ts2=[["2023-01-18",5],["2023-01-19",6],["2023-01-20",7],["2023-01-21",8]],ts3=[["2023-01-21",9],["2023-01-22",10],["2023-01-23",11],["2023-01-24",12]];
const res = Object.entries([ts1, ts2, ts3].reduce((acc, curr, i, t) => {
  curr.forEach(([k, v]) => (acc[k] ??= Array(t.length).fill(null))[i] = v);
  return acc;
}, {})).sort().map(([k, v]) => [k, ...v]);
console.log(res);

You can create an efficient algorithm to merge the time series by first putting all the dates and values in a hash map and then converting it into an array.

This is an efficient approach because hash map operations (insertion and lookup) are generally O(1), which makes the algorithm faster than directly comparing and inserting into arrays.

Here is an example:

const ts1 = [
  ['2023-01-20', 1],
  ['2023-01-21', 2],
  ['2023-01-22', 3],
  ['2023-01-23', 4],
];

const ts2 = [
  ['2023-01-18', 5],
  ['2023-01-19', 6],
  ['2023-01-20', 7],
  ['2023-01-21', 8]
];

const ts3 = [
  ['2023-01-21', 9],
  ['2023-01-22', 10],
  ['2023-01-23', 11],
  ['2023-01-24', 12]
];

function mergeTimeSeries(...timeSeries) {
  const hashMap = {};
  let seriesIndex = 1;
  
  for (const ts of timeSeries) {
    for (const [date, value] of ts) {
      if (!hashMap[date]) {
        hashMap[date] = Array(timeSeries.length + 1).fill(null);
        hashMap[date][0] = date;
      }
      hashMap[date][seriesIndex] = value;
    }
    seriesIndex++;
  }

  // Convert hashMap into array and sort by date
  const result = Object.values(hashMap).sort((a, b) => new Date(a[0]) - new Date(b[0]));

  return result;
}

const output = mergeTimeSeries(ts1, ts2, ts3);

console.log(output);

Please signup or login to give your own answer.

Click here to cancel reply.