I'm doing some datetime manipulation, and I've implemented a really slow algorithm. I'm hoping for some suggested improvement. I'm asking here (instead of StackOverflow) and keeping it language agnostic because this is a question about choosing the right algorithm, not about how to implement it.
The function has three inputs: MeasurementDates : DateTime, EventDates : DateTime, and Interval: Timespan.
The return type is an int of the same length as MeasurementDates. The goal is to compute the number of events from EventDates that occurred within Interval time before Measurement dates.
For context: Let's say MeasurementDates are the dates on which a stock price for some company is recorded, and EventDates are the dates on which the company featured in the news. I want to calculate a value, "Number of Times the company was in the news in the last X days" as a potential predictor of the stock price. (This is meant to illustrate the function, not describe the real use case.)
Example: I pass in MeasurementDates =[Aug 3, Aug 4, Aug 5], EventDates =[Aug 2], and Interval = (2 days), and I expected to get [1,1,0] because the first element of MeasurementDates has one event within two days before it, the second element of MeasurementDates has one event within two days before it, and the third element has zero events within two days before it.
My current algorithm works like this:
define CountEventsWithinInterval(MeasurementDates, EventDates, Interval): result := repeat(0, length(MeasurementDates)) for Event in EventDates: bool toIncrement := MeasurementDates.map(event is within interval before date) for i in 0:length(toIncrement): if toIncrement[i]: result[i] := result[i] + 1 return result
This produces the correct result, but it is slow. It has to compare every date in MeasurementDates to every date in EventDates, resulting in O(m * n). Maybe there is a way to use sorting that keeps the algorithm from having to compare every date in one input to every date in the other, or maybe I am missing something entirely.
Given that MeasurementDates and EventDates are likely to be very long in practice (1000s of entries), I'm hoping that there's something I'm missing that could make the algorithm run more quickly.
The order of MeasurementDates is already chronological; EventDates can be sorted if that helps.