Algorithm: Efficiently Count Recent Occurrences

Question

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.

Answer 1

As you point out some of the input data is sorted, which can be taken advantage of. And as you suspect, sorting the other array will be helpful. Further, as you have described it, the output array corresponds 1:1 to one of the already-sorted the inputs.

This suggests iterating over that sorted input to produce the output. So, we want to do something that looks more like this:

define CountEventsWithinInterval(MeasurementDates, EventDates, Interval):
    for i in 0:length(MeasurementDates)
        aMeasurementDate = MeasurementDates [ i ]
        eventCount =  ??? ( aMeasurementDate, EventDates )
        result [ i ] := eventCount
    return result

Now, we need to an algorithm to compute the number times that one given measurement date falls within the interval of the given events. To do this, if the events were also sorted, we would seek to the first position in the events that is within one given measurement date - interval (e.g. the early end of the interval range), then count the number of events until we are past the given measurement date. We can then ignore the rest of the given events beyond that because they occur in the future (relative to one given measurement date of current interest).

The expensive part here is the seek to find the low end of the interval window for that one given measurement range. The seek on average seeks, say, half the events array, and occurs as a nested loop with the measurements, we still have an O(m * n) cost here (well, * (n/2) but that's all in the noise).

However, we know that we can traverse (are traversing in my the above snippet) the measurement dates in forward time order, so, once we find the event window position for a given iteration (i.e. for a given measurement date), we can use that as the start position for the (next iteration's) seek in the above worded algorithm. Thus, the seeks will be minimized, and we will effectively only traverse (via the seek) the Events array once, from start to ~finish. Thus, the seek will not even be the cost of a nested loop, which converts the cost to something like O(m + n) instead of O(m * n) (this big O is ignoring the interval size, which adds to the cost, of course, so this is only m + n for the minimal interval.)

---

This effectively marches forward over two input arrays (and one output array); one (the measurement dates) goes linearly from start to finish; linear scans enjoy a good measure of the systems caching behavior (CPU cache, and memory paging). For the other (event dates) we advance the seek position as we can, and traverse an range of the elements in a sliding window. Generally speaking the effectiveness of the CPU cache should be even higher on using this kind of sliding window because a smaller range/window is repeatedly hit as long as it is reasonably sized (though at some larger interval size will exceed the cache and then suffer tremendously).

Answer 2

Store this data in a database, and then query it using a query language like SQL.

This will make the data much easier to store and manipulate, and you will be able to get the answer to this and other questions from the data very easily and efficiently.

In your example you could put the measurement dates in a table and then run a query like this:

select measurement_date,count(*) 
   from measurement_dates
   join stock_price_data on 
      stock_date between measurement_date - interval days and measurement
   group by measurement_date

Note that in the above query, you don't have to actually specify how to achieve the result, only what you want (in technical terms SQL is a declarative language). This is easier for you, and because of extensive optimisations to ensure efficient manipulation of data, it will typically perform much better than any algorithm you would write.

Adding a database to your application might seem intimidating if you haven't worked with one before, but it will really pay off in the long run. After the initial overhead, it will make everything you do easier. And, there are several good free databases available, and all major languages have readily available database tools.

Answer 3

Slightly different approach than what has been provided already.

You start by sorting both sets of inputs. Then take the first measurement date and do a binary search on the event date spans (i.e. an artificial data set of spans from the event dates). If you were simply to do this, you are no longer doing MN comparisons. You are doing MlogN comparisons.

But we can do better. Since your measurements are sorted, once you know the earliest event that relates to your measurements, you can set the beginning of your binary search for the next element to that element (I'm assuming you can have duplicate measurement dates.) Then each search is successively quicker.

But wait, there's more! Instead of moving the second measurement after the first, go to the end and do a search on the last measurement. Now use that result as the new end of the search window. Then go to the second, and then the second to last, etc. continuing to close the window as you get towards the middle of the measurements. For example, if you have ten elements you would go in this order, 0,9,1,8,2,7,3,6,4,5, each time updating the search window start or end.