Решение задачи про шарды на stepik.org

simulation.py

from intervals import IntInterval
from infinity import inf

def request_range(now, n):
    if n < now/10:
        return IntInterval.closed_open(now-(n+1)*10, now-n*10)
    else:
        return IntInterval([max(0, now-10), now])

'''
Актуальное содержимое его логического шарда делится ровно пополам,
на середине своего актуального диапазона.
"Нижняя" часть (вместе с медианным элементом, если записей нечетное количество)
уходит обслуживаться на вновь созданный узел.
'''
def split_range(r):
    centre = r.centre
    median = round(centre)
    l = r.lower
    u = r.upper
    if r.is_open:
        return (
            IntInterval.open_closed(l, median),
            IntInterval.open(median, u),
        )
    elif r.is_closed:
        return (
            IntInterval.closed(l, median),
            IntInterval.open_closed(median, u),
        )
    elif r.lower_inc and not r.upper_inc: # closed_open
        return (
            IntInterval.closed(l, median),
            IntInterval.open(median, u),
        )
    elif not r.lower_inc and r.upper_inc: # open_closed
        return (
            IntInterval.open_closed(l, median),
            IntInterval.open_closed(median, u),
        )
    else:
        raise RuntimeError('Неопознанный тип интеравала в split_range. Такого никогда не должно произойти.')

assert split_range(IntInterval.closed(10, 20)) == (IntInterval.closed(10, 15), IntInterval.open_closed(15, 20))
assert split_range(IntInterval.open_closed(15, 20)) == (IntInterval.open_closed(15, 18), IntInterval.open_closed(18, 20))
assert split_range(IntInterval.closed_open(0, 10)) == (IntInterval.closed(0, 5), IntInterval.open(5, 10))
assert split_range(IntInterval.open(5, 10)) == (IntInterval.open_closed(5, 8), IntInterval.open(8, 10))


def simulation(clients_number, split_request_count_limit):
    TIME_STEP = 300
    MAX_STEPS = 10000000
    now = TIME_STEP
    shards = [
        {
            'range': IntInterval([0, TIME_STEP]),
        }
    ]
    for i in range(0, MAX_STEPS):
        newShards = []
        for shard in shards:
            request_count = 0
            for client_n in range(0, clients_number):
                client_request_range = request_range(now, client_n)
                if client_request_range in shard['range']:
                    request_count += 1
            if request_count >= split_request_count_limit:
                lowerRange,upperRange = split_range(shard['range'])
                newShards.append(
                    {
                        'range': lowerRange,
                    }
                )
                newShards.append(
                    {
                        'range': upperRange,
                    }
                )
            else:
                newShards.append(shard)
        if len(shards) == len(newShards):
            break
        now += TIME_STEP
        newShards[-1]['range'].upper += TIME_STEP
        shards = newShards
    return now - TIME_STEP

if __name__ == "__main__":
    clients_number = 300
    # Если узел в течение 5 минут непрерывно получает нагрузку более чем 100 запросов в секунду,
    # то актуальное содержимое его логического шарда делится ровно пополам
    split_request_count_limit = 100
    answer = simulation(clients_number, split_request_count_limit)
    print('Ответ:', answer/60, 'мин.')