Comparison of different approaches to summing dict values with 'sparse' keys.

sparse_summation_benchmarks.py

"""Comparison of different approaches to summing dict values with 'sparse' keys.

Sparse here means the keys of all dicts are drawn from a common set but only a few
keys (compared to the total number) are present in each.
"""

import pandas as pd
import numpy as np
import timeit
from string import ascii_lowercase
from itertools import product
from collections import Counter


def sparse_series_from_dict(data, index):
    index_map = {k: i for i, k in enumerate(index)}
    data_indices = [index_map[k] for k in data.keys()]
    sorted_data_indices, sorted_data_values = zip(
        *sorted(zip(data_indices, data.values())))
    sparse_index = pd.core.arrays.sparse.IntIndex(len(index), sorted_data_indices)
    return pd.Series(
        pd.arrays.SparseArray(sorted_data_values, sparse_index, fill_value=0),
        index=index
    )


def series_from_dict(data, index):
    series = pd.Series(data, index=index)
    series.fillna(0, inplace=True)
    return series


def sum_inplace(iterable, total=0):
    for val in iterable:
        total += val
    return total


def sum_update(iterable, total):
    for val in iterable:
        total.update(val)
    return total


def print_results_string(results_dict, key, num_iter):
    times = np.array([t / num_iter for t in results_dict[key]])
    print(f"{key:>20} times: min = {times.min():.2f}s, max = {times.max():.2f}s")


seed = 20210610
num_events = 10000
max_num_officers_per_event = 6
num_repeats = 7
num_iter = 1

rng = np.random.default_rng(seed)

# make list of three a-z character keys of same length as officer index
keys = list(''.join(t) for t in product('abc', ascii_lowercase, ascii_lowercase))[:1428]

# simulate random appointment footprint dictionaries with non-negative time requests of
# [1, max_num_officers_per_event] officers chosen randomly without replacement
dicts = [
    {
        k: np.exp(rng.standard_normal())
        for k in rng.choice(
            keys, replace=False, size=rng.integers(1, max_num_officers_per_event + 1))
    }
    for _ in range(num_events)
]

# mapping functions and initial values for summations
func_init_and_sum_funcs = {
    'Counter': (
        lambda d: Counter(d),
        lambda: Counter(),
        lambda s1, s2: s1 == s2,
        (sum, sum_inplace, sum_update)
    ),
    'Series': (
        lambda d: series_from_dict(d, index=keys),
        lambda: pd.Series(0, index=keys),
        lambda s1, s2: (s1 == s2).all(),
        (sum, sum_inplace)
    ),
    'SparseSeries': (
        lambda d: sparse_series_from_dict(d, keys),
        lambda: sparse_series_from_dict({keys[0]: 0}, keys),
        lambda s1, s2: (s1 == s2).all(),
        (sum,)
    )
}

results = {}
for label, (func, init, equaity_func, sum_funcs) in func_init_and_sum_funcs.items():
    ref_sum = sum((func(d) for d in dicts), init())
    for sum_func in sum_funcs:
        the_sum = sum_func((func(d) for d in dicts), init())
        if not equaity_func(ref_sum, the_sum):
            breakpoint()
        combination = f"{sum_func.__name__}({label})"
        results[combination] = timeit.repeat(
            lambda: sum_func((func(d) for d in dicts), init()),
            repeat=num_repeats,
            number=num_iter
        )
        print_results_string(results, combination, num_iter)

results["DataFrame.sum"] = timeit.repeat(
    lambda: pd.DataFrame({i: d for i, d in enumerate(dicts)}, index=keys).sum(axis=1),
    repeat=num_repeats,
    number=num_iter
)
print_results_string(results, "DataFrame.sum", num_iter)

results["SparseDataFrame.sum"] = timeit.repeat(
    lambda: pd.DataFrame(
        {i: sparse_series_from_dict(d, keys) for i, d in enumerate(dicts)},
        index=keys
    ).sum(axis=1),
    repeat=num_repeats,
    number=num_iter
)
print_results_string(results, "SparseDataFrame.sum", num_iter)