Оптимизация решения численной задачи

Question

Решаю задачку (https://www.codewars.com/kata/5b5ce2176d0db7331f0000c0/train/python). Вот моё решение:

def get_rope_length(field_diameter, eaten_ratio):
    import math
    
    R = field_diameter/2
    eps = 10**(-(len(str(field_diameter)))-1)
    
    def square(r):
        import math
        alpha = (math.asin(r/(2*R)))*2
        beta = math.acos(r/(2*R))

        square_alpha = (R**2)*(alpha - 0.5*math.sin(alpha*2))
        square_beta = (r**2)*(beta - 0.5*math.sin(beta*2))

        square = square_alpha + square_beta

        return(square)
    
    if (R > 0) and (eaten_ratio < 1):
        S = math.pi*R*R
        
        step = R
        r = step
        
        while True:
            delta = (S * eaten_ratio) - square(r)
            if abs(delta) < eps:
                break
            if delta > 0:
                r = r + step
            else:
                r = r - step
            step = step/2
        return (int(r))
    elif (R == 0):
        return(0)
    elif (eaten_ratio == 1):
        return(int(R*2))

Вкратце. Функция square определяет площадь фигуры, образованной наложением окружностей (центр "искомой" окружности лежит на одной из точек "зафиксированной" окружности). Далее идет само решение задачи. Решал методом деления отрезка пополам. Искомый радиус последовательно приближается к искомому значению, при котором площадь наложения не отличается от требуемой на заданную точность (переменная eps). Однако такой метод медленно работает при больших входных величинах. Не подскажете, как решать данную задачу и вообще задачи подобного типа, когда составить какую-то зависимость достаточно проблематично. Как мне кажется, ускориться можно, если выбрать другое начальное приближение и шаг сближения (В моем решении я начинаю безусловно решать при step == R == r)

Answer 1

Почему бы не задействовать двоичный поиск?

class Solution:
    def __init__(self, diameter):
        self.diameter = diameter

    def __len__(self):
        return self.diameter + 1

    def __getitem__(self, rope_length):
        # процент отъеденный от поля диаметром self.diameter при длине веревки rope_length
        return ...

А потом, бац,

import bisect

def get_rope_length(field_diameter, eaten_ratio):
    return bisect.bisect_right(Solution(field_diameter), eaten_ratio)

БЛОГ НА HUSL

Оптимизация решения численной задачи

Ответы (1 шт):