Calculate of the average of time discounted values

Question

Given the current table:

+------------+-------+
|    date    | value |
+------------+-------+
| 01/01/2000 |     1 |
| 03/04/2000 |     3 |
| 05/08/2000 |     4 |
| 07/11/2000 |     2 |
+------------+-------+

For each date I'm looking to get an average of the values for the preceding dates where each value is discounted by a time factor. The time factor is calculated as follows:

discount_constant ** (date - date_of_value)

So if I want to calculate the average for 07/11/2000 then I would first get the time discounted value for 05/08/2000:

date_diff_0508 = 07/11/2000 - 05/08/2000
time_discount_0508 = discount_constant ** date_diff
time_discounted_value_0508 = time_discount * 4

Then the time discounted value for 03/04/2000

date_diff_0304 = 05/08/2000 - 03/04/2000
time_discount_0304 = discount_constant ** date_diff
time_discounted_value_0304 = time_discount * 3

Then the time discounted value for 01/01/2000

date_diff_0101 = 03/04/2000 - 01/01/2000
time_discount_0101 = discount_constant ** date_diff
time_discounted_value_0101 = time_discount * 1

Where td = time_discount and tdv = time_discount_value I can then calculate the average as follows:

sum_tdv = sum([tdv_0508, tdv_0304, tdv_0101])
sum_td = sum([td_0508, td_0304, td_0101])
avg_stat = sum_tdv / sum_td

The final output would be:

+------------+-------+-----------------------+
|    date    | value |  avg_discounted_value |
+------------+-------+-----------------------+
| 01/01/2000 |     1 |                  NULL |
| 03/04/2000 |     3 |                1.0000 |
| 05/08/2000 |     4 |                2.0465 |
| 07/11/2000 |     2 |                2.7732 |
+------------+-------+-----------------------+

In reality though there is another layer of complexity as the actual table has a class column and the time discounted averages need to be calculated by class. Below is the final output:

+------------+-------+-------+-----------------------+
|    date    | class | value |  avg_discounted_value |
+------------+-------+-------+-----------------------+
| 01/01/2000 |     1 |     1 |  NULL                 |
| 03/04/2000 |     1 |     3 |  1.0000               |
| 05/08/2000 |     1 |     4 |  2.0465               |
| 07/11/2000 |     1 |     2 |  2.7732               |
| 01/01/2000 |     2 |     2 |  NULL                 |
| 03/04/2000 |     2 |     7 |  2.0000               |
| 05/08/2000 |     2 |     3 |  4.6162               |
| 07/11/2000 |     2 |     9 |  4.0150               |
+------------+-------+-------+-----------------------+

Via a for loop I currently query a database to extract all the records for each class and convert them into a dictionary:

values_by_date = [
    {"datetime": dt.datetime(2000, 1, 1), "value": 1},
    {"datetime": dt.datetime(2000, 4, 3), "value": 3},
    {"datetime": dt.datetime(2000, 8, 5), "value": 4},
    {"datetime": dt.datetime(2000, 11, 7), "value": 2},
]

I then run the following code over it:

import copy

discount_constant = 0.999
desc_values_by_date = sorted(values_by_date, key=lambda d: d["datetime"], reverse=True)
iter_values_by_date = copy.deepcopy(desc_values_by_date)
for isbd in iter_values_by_date[:-1]:
    del desc_values_by_date[0]
    for dsbd in desc_values_by_date:
        date_diff = (isbd["datetime"] - dsbd["datetime"]).days
        dsbd["discount_factor"] = discount_constant ** date_diff
        dsbd["discount_value"] = dsbd["discount_factor"] * dsbd["value"]
    sum_discount_factor = sum(dsbd["discount_factor"] for dsbd in desc_values_by_date)
    sum_discount_value = sum(dsbd["discount_value"] for dsbd in desc_values_by_date)
    avg_discounted_value = sum_discount_value / sum_discount_factor
    # some code to update the original database record with avg_discounted_value

Some additional notes:

1. There are circa 1 million records in the database table with around 50k class variations which each have 1 - 2000 records
2. The class column is indexed
3. In the non-MRE version of my code I already make use of parallel processing

The process above can take several minutes and there are currently over a hundred different value columns so the whole process can take hours to run.

I've been reading about how numpy can be used to take advantage of vectorisation and speed up for loops. However, the examples I've found are rather simple and I can't extrapolate them into a solution for the above especially when my end point is inserting calculated values back into a database. I'm also conscious that I think in Python and that the solution may actually lie with keeping all the calculations in the database via an SQL query.

Solution thoughts I've had:

1. Use numpy and vectorisation on a 'per class' basis
2. Use numpy and vectorisation on all class variations at the same time
3. Convert everything into a single SQL UPDATE query

Would anyone here have any ideas on the best approach?

Answer 1

You expect the subtraction of date and date_of_value to be in fractional days. This doesn't do what you think it does:

date_diff = (isbd["datetime"] - dsbd["datetime"]).days

Rather than the total fractional days, that produces the "days field" of a timedelta. Instead, you'll want to divide by another timedelta of one day. This will appear to produce the same results, until you introduce non-midnight times into your data. They're not the same thing.

Using Numpy and Pandas will allow you to vectorise and avoid loops.

I don't understand why you think there should be a NULL in a rolling average. Surely the first row's average discounted value should be equal to the discounted value for that date.

Via a for loop I currently query a database to extract all the records for each class and convert them into a dictionary:

does not sound like a good idea. Avoid the intermediate dictionary, and use the Pandas built-in SQL support - or more likely, just run a SQL query that will accomplish the same calculation as what you're currently doing in Python.

If you're determined to use in-application computation, I would expect something like

from datetime import date

import numpy as np
import pandas as pd


ONE_DAY = pd.to_timedelta(1, 'd')


def running_discount(
    df: pd.DataFrame,
    discount_factor: float = 1e-3,
) -> None:
    delta = (df.date.iloc[-1] - df.date) / ONE_DAY
    weights = (1 - discount_factor) ** delta

    def weighted_mean(value: pd.Series) -> float:
        return np.average(value, weights=weights[value.index])

    mean = (
        df.groupby('class')
        .value
        .expanding()
        .apply(weighted_mean)
    )
    df['avg_discounted_value'] = mean.droplevel(0)


def test() -> None:
    cat_type = pd.CategoricalDtype((1, 2))

    df = pd.DataFrame({
        'date': (
            date(2000, 1, 1), date(2000, 3, 4), date(2000, 5, 8), date(2000, 7, 11),
            date(2000, 1, 1), date(2000, 3, 4), date(2000, 5, 8), date(2000, 7, 11),
        ),
        'value': (
            1, 3, 4, 2,
            2, 7, 3, 9,
        ),
        'class': pd.Series(
            (
                1, 1, 1, 1,
                2, 2, 2, 2,
            ), dtype=cat_type,
        )
    })

    running_discount(df)

    assert np.all(np.isclose(
        df.avg_discounted_value.to_numpy(),
        (
            1.000000, 2.031505, 2.730338, 2.529812,
            2.000000, 4.578763, 4.018289, 5.386094,
        )
    ))

    print(df)


if __name__ == '__main__':
    test()

The results are not equivalent to yours and that's deliberate. With the above example the produced dataframe looks like

         date  value class  avg_discounted_value
0  2000-01-01      1     1              1.000000
1  2000-03-04      3     1              2.031505
2  2000-05-08      4     1              2.730338
3  2000-07-11      2     1              2.529812
4  2000-01-01      2     2              2.000000
5  2000-03-04      7     2              4.578763
6  2000-05-08      3     2              4.018289
7  2000-07-11      9     2              5.386094