dict_contain.py

import random
import uuid
import time
from typing import Dict

def timeit(f):
    def _(*args, **kwargs):
        start = time.time()
        ret = f(*args, **kwargs)
        elapsed = time.time() - start
        return elapsed, ret
    return _


@timeit
def contains(x: Dict[str, float], y: Dict[str, float]) -> bool:
    """Determines whether ``x`` contains ``y``.

    ``x`` contains ``y`` if for all keys ``k`` in ``y``, ``k`` in ``x`` and
    ``y[k] <= x[k]``.
    """
    for k, v in y.items():
        if k not in x or x[k] < v:
            return False
    return True


def generate_dicts(size):
    x, y = {}, {}
    for _ in range(size):
        k = str(uuid.uuid4())
        v = random.random()
        x[k], y[k] = v, v / 2
    return x, y


class AverageMeter:
    def __init__(self):
        self.num_samples = 0
        self.total = 0

    def tell(self, x):
        self.num_samples += 1
        self.total += x

    def ask(self):
        return self.total / self.num_samples


def main():
    ntrials = 10
    sizes = [10**i for i in range(1, 6)]

    for size in sizes:
        avg = AverageMeter()
        for _ in range(ntrials):
            x, y = generate_dicts(size)
            elapsed, y_in_x = contains(x, y)
            avg.tell(elapsed)
            assert y_in_x
        print(f'Expected worst-case runtime for {size:10d} keys: {avg.ask():.2E} s')


if __name__ == '__main__':
    main()