Given a range of date intervals, create an array of all 1440 minutes in a day with the frequency each minute appears in the source intervals

Question

I'm currently analysing my sleep data (with the help of d3), and I have an array of times/dates from my sleep tracking app representing when a sleep period started and ended.

[
  {
    "startDate": "2017-12-25 00:09:00 +0100",
    "endDate": "2017-12-25 00:50:00 +0100"
  },
  {
    "startDate": "2017-12-25 01:45:00 +0100",
    "endDate": "2017-12-25 02:11:00 +0100"
  },
  {
    "startDate": "2017-12-25 02:26:00 +0100",
    "endDate": "2017-12-25 12:37:00 +0100"
  },
  ...
]

From these entries, I want to create a histogram-type chart that shows how likely it is that I'll be asleep for a given hour and minute of the day. So along the X-axis will be 1,440 ticks representing each minute of a general day, and the height of the bar will be how likely it is (using a simple count) I'll be asleep at that given minute.

Currently, I'm creating an array of all the individual minutes between all of my intervals (i.e. in the first entry above, there would be 41 objects representing each minute between 00:09 and 00:50) and then matching them against all 1,440 minutes in a day. When they match, increase the count for that "minute of the day" by one.

So over time, I can see that I'm likely to be asleep at, say, 01:00, and awake at, say, 12:30.

I have around 3,100 sleep entries, and while my current code appears to work, it takes a long time to go through my entries (understandably as there's a map within a map). If I try to run it on just 1,000 entries in a Codesandbox, I don't get the results back for around a minute.

Also, it… feels inefficient. I'm sure there must be a more efficient way of doing this (I wondered if perhaps there was a d3 function to make it easier, but I couldn't find one).

Part of the problem I've had is knowing what to search for — is it a histogram? A frequency chart? Something else?

import * as d3 from 'd3';
import { add, format, getHours, getMinutes } from 'date-fns';
import { flatMap, map } from 'lodash';


// For each interval in the source data, create an array of the minutes
// in that interval
// e.g. For an interval time 00:10:00 to 00:18:00,
//      return 9 dates (00:10:00, 00:11:00, 00:12:00, etc.)

const minutesFromIntervals = flatMap(data, (interval) =>
  d3.timeMinute.range(
    new Date(interval.startDate),
    new Date(interval.endDate),
  ),
);


// Create an array of all the minutes in a day between midnight and
// midnight (1440 minutes)

const minutesOfDay = d3.timeMinute.range(
  new Date(2020, 0, 1),
  add(new Date(2020, 0, 1), { hours: 24 }),
);


// Map over the minutes of a day and see which interval minutes match

const results = map(minutesOfDay, (o) => {
  let count = 0;

  const outerDate = new Date(o);
  const hour = getHours(outerDate);
  const minute = getMinutes(outerDate);

  map(minutesFromIntervals, (p) => {
    const innerDate = new Date(p);
    if (getHours(innerDate) === hour && getMinutes(innerDate) === minute) {
      count += 1;
    }
  });

  return {
    key: format(o, 'HH:mm'),
    value: count,
  };
});


console.log({ results });

// results (example):
// [
//   { key: "00:00", value: 0 },
//   { key: "00:01", value: 1 },
//   { key: "00:02", value: 1 },
//   { key: "00:03", value: 1 },
//   { key: "00:04", value: 2 },
//   { key: "00:05", value: 2 },
//   { key: "00:06", value: 1 },
//   { key: "00:07", value: 3 },
//   ...
// ]

user_5015356 · Answer

I'm afraid you won't be able to do much about the O(n^2) complexity, but you can greatly reduce the cost of each step by just eliminating the date aspect of it and looking at it from an integer perspective instead.

When you work with time, you always have the problem that you also need to include some date. Then you also have leap years, time zones, and Daylight Savings Time. If you look at it, instead, like 1440 minutes, the ith minute denoting i minutes after midnight, you don't have to work with time any more.

Here, I calculate the offset as the number of minutes since midnight on the day you went to sleep, and then I calculate the duration of your sleep in minutes. If you go to sleep before 12 and wake up after 12, I use % 1440 to start counting from midnight again.

All the while, instead of parsing and calculating O(n^2) dates, I do only 5 date calculations per entry, so O(n). And now you can just plot it as a bar chart, with a tick on every 60th value, and a tick format like d + ":00" or d + "h" that makes it look like a timestamp.

const differenceInMinutes = dateFns.differenceInMinutes;
const parse = dateFns.parse;
const startOfDay = dateFns.startOfDay;

const data = [{
    "startDate": "2017-12-24 23:49:00 +0100",
    "endDate": "2017-12-25 00:03:00 +0100"
  },
  {
    "startDate": "2017-12-25 00:09:00 +0100",
    "endDate": "2017-12-25 00:50:00 +0100"
  },
  {
    "startDate": "2017-12-25 01:45:00 +0100",
    "endDate": "2017-12-25 02:11:00 +0100"
  },
  {
    "startDate": "2017-12-25 02:26:00 +0100",
    "endDate": "2017-12-25 12:37:00 +0100"
  },
].map(d => ({
  startDate: parse(d.startDate),
  endDate: parse(d.endDate),
}));

// This is the result, with minute `x` denoting `x` minutes after midnight
const total = 1440;
const result = new Array(total).fill(0);

data.forEach(d => {
  const offset = differenceInMinutes(d.startDate, startOfDay(d.startDate));
  const duration = differenceInMinutes(d.endDate, d.startDate);

  for (let i = 0; i < duration; i++) {
    result[(i + offset) % total] += 1;
  }
});

for (let i = 0; i < total; i += 60) {
  console.log(i / 60, "    ", result.slice(i, i + 60).join(" "));
}

user_257182 · Answer

I wouldn't use Date objects at all, they're really only necessary on the days that change from standard to daylight saving time and back again. Simpler to either ignore or just not include those days in the data. Or do everything as UTC, but that will mess with the result (perhaps trivially).

So you need to be able to initialise the resulting object with properties for each minute from 00:00 to 23:59, then just increment the ones in a particular sleep period. There are cases where a sleep period will start and end on the same day, or end on the following day. Covering periods that go over more than two days isn't hard, but adds complexity that you likely don't need.

PS. This solution doesn't need to convert the strings to dates, it just uses time. All timestamps are treated as local.

E.g.

// Convert minutes to time as HH:mm
function minsToTime(mins) {
  let z = n => ('0' + n).slice(-2);
  return z(mins / 60 | 0) + ':' + z(mins % 60);
}
// Add one minute to time in HH:mm format
function addMinute(time) {
  let [h, m] = time.split(':');
  return minsToTime(h*60 + m*1 + 1);
}

// Build initial minuteData object {'HH:mm': 0}
function initialiseMinuteData() {
  let minuteData = {};
  for (let i=0; i<1440; i++) {
    minuteData[minsToTime(i)] = 0;
  }
  return minuteData;
}

// Update minuteData with sleepData, initialise minuteData if not provided
function updateMinuteData(sleepData, minuteData = initialiseMinuteData()) {
  sleepData.forEach(p => {
    let [startDate, startTime] = p.startDate.split(' ');
    let [endDate, endTime] = p.endDate.split(' ');
    startTime = startTime.slice(0, 5);
    endTime = endTime.slice(0, 5);
    
    if (startDate == endDate) {
      while (startTime <= endTime) {
        minuteData[startTime] += 1;
        startTime = addMinute(startTime);
      }
      
    } else {
      while (startTime <= '23:59') {
        minuteData[startTime] += 1;
        startTime = addMinute(startTime);        
      }
      startTime = '00:00';
      while (startTime <= endTime) {
        minuteData[startTime] += 1;
        startTime = addMinute(startTime);        
      }
    }
  });
  return minuteData;
}

// Sample sleep data
let sleepData0 = [
  {"startDate": "2017-12-25 12:00:00 +0100", // Midday snooze
    "endDate": "2017-12-25 12:30:00 +0100"},
  {"startDate": "2017-12-25 22:00:00 +0100", // Regular night's sleep
    "endDate": "2017-12-26 06:30:00 +0100"},
  {"startDate": "2017-12-26 22:00:00 +0100",
   "endDate": "2017-12-27 06:30:00 +0100"},
  {"startDate": "2017-12-27 22:00:00 +0100",
   "endDate": "2017-12-28 06:30:00 +0100"}
];

let sleepData1 = [
  {"startDate": "2017-12-29 14:05:00 +0100", // Afternoon snooze
    "endDate": "2017-12-29 14:45:00 +0100"}
];


// Generate and display minuteData from sleepData
let minuteData = updateMinuteData(sleepData0)
console.log(minuteData);

// Update with afternoon nap
updateMinuteData(sleepData1, minuteData);
console.log(minuteData);

Given a range of date intervals, create an array of all 1440 minutes in a day with the frequency each minute appears in the source intervals

2 Answers