

In [5]:

    
from random import shuffle



In [6]:

    
def frugal_1U(stream, original_est=0):
    median_est = original_est
    for val in stream:
        if val > median_est:
            median_est += 1
        elif val < median_est:
            median_est -= 1
    return median_est



In [7]:

    
linear_stream = range(1, 100000)



In [8]:

    
random_stream = range(1, 100000)
shuffle(random_stream)

Test with linear data



In [10]:

    
frugal_1U(linear_stream)









    Out[10]:





99999



In [11]:

    
frugal_1U(linear_stream, 50000)









    Out[11]:





99999

Test with randomized data



In [12]:

    
frugal_1U(random_stream)









    Out[12]:





43395



In [13]:

    
frugal_1U(random_stream, 50000)









    Out[13]:





50159