param_cache.py

from math import log2
from collections import deque
from bisect import bisect_right

class Memory:
    
    def __init__(self, f):
        self.func = f
        self.xs = deque()
        #self.pos = deque()
        self.count = 0
        self.first = 0
        
    @property
    def size(self):
        return int(log2(self.count) + 1)
    
    @property
    def pos(self):
        size = self.size
        return [self.count + 1 - 2**(size - n) for n in range(1, size)]
    
    def retrieve(self, xi, verbose=False):
        index = bisect_right(dobra.pos, xi)
        if index == 0:
            startpos = 0
            start = self.first
        else:
            startpos = dobra.pos[index - 1]
            start = self.xs[index - 1]
        steps = xi - startpos
        if verbose:
            print(f'{steps} steps to retrieve x{xi} from stored x{startpos}')
        result = start
        for _ in range(steps):
            result = self.func(result)
        return result
    
    def __call__(self, parameter):
        if self.count == 0:
            self.first = parameter
        self.count += 1
        for i in range(len(self.xs)):
            #self.pos[i] += 1
            self.xs[i] = self.func(self.xs[i])
        if len(self.xs) < self.size - 1:
            #self.pos.appendleft(1)
            self.xs.appendleft(self.func(self.first))
        return self.func(parameter)
    
    
@Memory
def dobra(x):
    return x+x


xn = dobra(1)
for i in range(99):
    xn = dobra(xn)
print(xn)

print(dobra.retrieve(2, verbose=True))
print(dobra.retrieve(40, verbose=True))
print(dobra.retrieve(69, verbose=True))
print(dobra.retrieve(100, verbose=True))

param_cache_out.txt

1267650600228229401496703205376
2 steps to retrieve x2 from stored x0
4
3 steps to retrieve x40 from stored x37
1099511627776
0 steps to retrieve x69 from stored x69
590295810358705651712
1 steps to retrieve x100 from stored x99
1267650600228229401496703205376

unbalanced.py

from bisect import bisect_right

class Memory:
    
    def __init__(self, f):
        self.func = f
        self.xs = []
        self.pos = []
        self.count = 0
        self.binary_shift = 0
        
    
    def retrieve(self, xi, verbose=False):
        index = bisect_right(dobra.pos, xi)
        if index == 0:
            startpos = 0
            start = self.first
        else:
            startpos = dobra.pos[index - 1]
            start = self.xs[index - 1]
        steps = xi - startpos
        if verbose:
            print(f'{steps} steps to retrieve x{xi} from stored x{startpos}')
        result = start
        for _ in range(steps):
            result = self.func(result)
        return result
    
    def __call__(self, parameter):
        if self.binary_shift % 2 == 0:
            for i in range(1, len(self.pos)):
                if self.binary_shift & (2**i):
                    self.pos.pop(-i)
                    self.pos.append(self.count)
                    self.xs.pop(-i)
                    self.xs.append(parameter)
                    break
            else:
                self.pos.append(self.count)
                self.xs.append(parameter)
                self.binary_shift = 0
        self.count += 1
        self.binary_shift += 1
        return self.func(parameter)
    
    
@Memory
def dobra(x):
    return x+x


xn = dobra(1)
for i in range(99):
    xn = dobra(xn)
print(xn)

print(dobra.retrieve(2, verbose=True))
print(dobra.retrieve(68, verbose=True))
print(dobra.retrieve(80, verbose=True))
print(dobra.retrieve(100, verbose=True))
print(dobra.pos)

unbalanced_out.txt

1267650600228229401496703205376
2 steps to retrieve x2 from stored x0
4
4 steps to retrieve x68 from stored x64
295147905179352825856
0 steps to retrieve x80 from stored x80
1208925819614629174706176
2 steps to retrieve x100 from stored x98
1267650600228229401496703205376
[0, 64, 80, 88, 96, 98]