Может ли эта функция быть реорганизована в O (1)

Question

У меня есть эта функция, которая используется для вычисления значения с убывающей отдачей. Он подсчитывает, как часто постоянно увеличивающееся значение может быть вычтено из входного значения, и возвращает количество вычитаний. В настоящее время он реализован итеративно с бесконечным циклом:

// inputValue is our parameter. It is manipulated in the method body.
// step counts how many subtractions have been performed so far. It is also our returned value.
// loss is the value that is being subtracted from the inputValue at each step. It grows polynomially with each step.
public int calculate(int inputValue) {
    for (int step = 1; true; step++) {// infinite java for-each loop
        int loss = (int) (1 + 0.0006 * step*step + 0.2 * step);
        if (inputValue > loss) {
            inputValue -= loss;
        } else {
            return step;
        }
    }
}

Эта функция используется в различных местах более крупного приложения, а иногда и в коде, критичном к производительности. Я бы предпочел, чтобы он был реорганизован таким образом, чтобы больше не требовался цикл.

Я вполне уверен, что можно как-то посчитать результат более напрямую. Но мои математические навыки кажутся недостаточными для этого.

Кто-нибудь может показать мне функцию, которая дает идентичные результаты без необходимости цикла или рекурсии? Это нормально, если измененный код может давать разные результаты для экстремальных значений и угловых случаев. Отрицательные входные данные не должны учитываться.

Спасибо всем заранее.

Answer 1

Я не думаю, что вы можете сделать код быстрее, сохраняя точную логику. В частности, вам трудно подражать округлению на

   int loss = (int) (1 + 0.0006 * step*step + 0.2 * step);

Если это требование вашей бизнес-логики, а не ошибка, я не думаю, что вы можете добиться значительно лучше. С другой стороны, если то, что вы действительно хотите, является чем-то вроде (из синтаксиса, который я предполагал, что вы используете Java):

public static int calculate_double(int inputValue) {
    double value = inputValue;
    for (int step = 1; true; step++) {// infinite java for-each loop
        double loss = (1 + 0.0006 * step * step + 0.2 * step); // no rounding!
        if (value > loss) {
            value -= loss;
        } else {
            return step;
        }
    }
}

т.е. та же логика, но без округления на каждом шагу, тогда есть некоторые надежды.

Примечание : к сожалению, это округление имеет значение. Например, согласно моему тесту выходные данные calculate и calculate_double немного отличаются для каждого inputValue в диапазоне [4, 46465] (иногда даже больше, чем +1, например для inputValue = 1000 это calculate = 90 против calculate_double = 88). Для больших inputValue результаты более последовательны. Например, для результата 519 / 520 разница составляет всего [55294, 55547]. Тем не менее, для каждого результата есть ряд различных результатов.

Прежде всего, сумма loss в случае отсутствия округления для данного максимума step (назовем это n) имеет закрытую формулу:

sum(n) = n + 0.0006*n*(n+1)*(2n+1)/6 + 0.2*n*(n+1)/2

Таким образом, теоретически найти такое n, чтобы sum(n) < inputValue < sum(n+1) можно было сделать, решив кубическое уравнение sum(x) = inputValue, которое имеет замкнутую формулу , а затем проверив такие значения, как floor(x) и ceil(x). Однако математика немного сложнее, поэтому я не пошел этим путем.

Обратите также внимание, что, поскольку int имеет ограниченный диапазон, теоретически даже ваша реализация алгоритма равна O(1) (потому что он никогда не будет выполнять больше шагов, чем вычисление calculate(Integer.MAX_VALUE), которое является константой). Так что, вероятно, то, что вы действительно хотите, - это просто значительное ускорение.

К сожалению, коэффициенты 0.0006 и 0.2 достаточно малы, чтобы сделать различные слагаемые доминирующей частью суммы для различных n. Тем не менее, вы можете использовать бинарный поиск для гораздо лучшей производительности:

static int sum(int step) {
    // n + 0.2 * n*(n+1)/2  + 0.0006 * n*(n+1)*(2n+1)/6
    // ((0.0001*(2n+1) + 0.1) * (n+1) + 1) * n
    double s = ((0.0001 * (2 * step + 1) + 0.1) * (step + 1) + 1) * step;
    return (int) s;
}

static int calc_bin_search2(int inputValue) {
    int left = 0;
    // inputValue / 2 is a safe estimate, the answer for 100 is 27 or 28
    int right = inputValue < 100 ? inputValue : inputValue / 2;

    // for big inputValue reduce right more aggressively before starting the binary search
    if (inputValue > 1000) {
        while (true) {
            int test = right / 8;
            int tv = sum(test);
            if (tv > inputValue)
                right = test;
            else {
                left = test;
                break;
            }
        }
    }
    // just usual binary search
    while (true) {
        int mid = (left + right) / 2;
        int mv = sum(mid);
        if (mv == inputValue)
            return mid;
        else if (mid == left) {
            return mid + 1;
        } else if (mv < inputValue)
            left = mid;
        else
            right = mid;
    }
}

Примечание : return mid + 1 - это копия вашей исходной логики, которая возвращает одну step после вычитания последней loss.

В моих тестах эта реализация соответствовала выводу calculate_double и имела примерно одинаковую производительность для inputValue при 1000, в x50 быстрее для значений около 1_000_000 и x200 быстрее для значений около 1_000_000_000