infinite-median.py

from collections import defaultdict
import statistics
import random


class InfiniteMedian:
    """
    Works well if the number of possible values is low.
    Otherwise, nicht sehr gut
    """

    def __init__(self):
        self.histogram = defaultdict(lambda: 0)

    def add_number(self, number):
        self.histogram[number] += 1
        return self

    def add_numbers(self, numbers):
        for number in numbers:
            self.histogram[number] += 1
        return self

    def get_median(self):

        total = sum(self.histogram.values())
        midpoint = total / 2

        numbers = sorted(self.histogram.keys())

        for n, number in enumerate(numbers):

            frequency = self.histogram[number]

            midpoint -= frequency
            if midpoint < 0:
                # midpoint is in current number. median is current number
                return number
            if midpoint == 0:
                return (number + numbers[n + 1]) / 2


while True:

    numbers = [random.randint(0, 100) for i in range(0, 11)]

    im = InfiniteMedian().add_numbers(numbers)

    im_median = im.get_median()
    stats_median = statistics.median(numbers)

    assert im_median == stats_median, {"im": im_median, "stats": stats_median, "numbers": numbers}
    print("okay")