from random import randint, random
stream = [randint(1000, 2000) for _ in range(20000)]

# The frugal streaming algorithm.
# Based on https://agkn.wordpress.com/2013/09/16/sketch-of-the-day-frugal-streaming/
# Originally presented in https://arxiv.org/pdf/1407.1121.pdf
# The simplest version is called Frugal-1U. It converges a bit slow, but given a long enough stream it works well.
# The Frugal-2U version modifies the step size along the way, plus other optimizations (not implemented here).

# Frugal streaming median finder.
median_est = 0
for x in stream:
    if median_est < x:
        median_est += 1
    elif median_est > x:
        median_est -= 1

# Frugal streaming 75th percentile finder.
p75_est = 0
for x in stream:
    r = random()
    if p75_est < x and r > 1 - 0.75:
        p75_est += 1
    elif p75_est > x and r > 0.75:
        p75_est -= 1

# Test.
stream.sort()
actual = stream[len(stream) // 2]
print("median actual={}, estimate={}".format(actual, median_est))
actual = stream[int(len(stream)*0.75)]
print("p75 actual={}, estimate={}".format(actual, p75_est))