В java, программа "запомнит" результат, если вы вызовете ту же функцию во второй раз?

Question

Этот вопрос возник, когда я думал об алгоритме для быстрого вычисления мощности числа, скажем, вычисления x^n.

В Java рекурсивная часть выглядит примерно так:

return power(x,n/2) * power(x,n/2);

Таким образом, после того, как программа вернула значение power(x,n/2), пройдёт ли она весь рекурсивный процесс снова, чтобы вычислить значение для второй power(x,n/2)?

Если да, то должны ли мы сначала сохранить значение в некоторой переменной, а затем вернуть квадрат этого значения?

Answer 1

То, что вы имеете в виду, называется памятка : чистая функция (то есть функция, возвращаемое значение которой зависит только от значений аргумента) может запомнить результат для аргументов, с которыми она сталкивалась ранее.

Мемоизация выполняется некоторыми высокоуровневыми специализированными языками, такими как Maple. Однако языки общего назначения по умолчанию не имеют такого (довольно сложного) поведения.

Однако в вашем случае это не обязательно. Вместо использования рекурсии ваш алгоритм лучше реализован как итерация . Двоичное возведение в степень путем многократного возведения в квадрат является стандартным алгоритмом.

Вот некоторый C-подобный псевдокод (мой Java не на 100%):

// compute pow(base, exponent)

int result = 1;
int term = base;

while (exponent != 0)
{
  if (exponent % 2 != 0) { result *= term; }
  term = term * term;
  exponent /= 2;
}

return result;

В некоторых примерах 7 равно 111 в двоичном виде, поэтому b ⁷ = b ¹ & times; b ² & times; b ⁴ , и нам нужно только отслеживать одну копию текущего термина. Еще один: 5 = 101b, поэтому b ⁵ = b ¹ & times; 1 & раз; б ⁴ .

_{В C ++ довольно просто создать универсальную оболочку для заметок для любой функции R f(T1, T2, ..., TN), которая хранит память в хэш-карте std::unordered_map<std::tuple<T1, ..., TN>, R>; при вызове обертка проверяет, существует ли уже аргумент-кортеж, и если да, возвращает значение из карты, а если нет, выполняет вычисление и вставляет результат в карту. Я уверен, что нечто подобное может быть установлено в Java.}

Answer 2

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

Таким образом, конкретная реализация power может знать достаточно для кэширования значения конкретной функции мощности.(Я подозреваю, что это маловероятно.) ИЛИ реализация Java может «просто знать», что power работает таким образом, и делать специальные сочетания клавиш с этим знанием.

В противном случае ответ в основном"Нет".

Answer 3

это домашнее задание?

Java, как и большинство языков программирования, не запоминает результаты вызовов методов по умолчанию, так как вызов метода может иметь другие побочные эффекты.Другими словами, JVM не может предположить, что эти два оператора эквивалентны:

 return power(x, n/2) * power(x, n/2)

и

 int sqrtPower = power(x, n/2);
 return sqrtPower * sqrtPower;

JVM не может выполнить эту оптимизацию - вы должны сделать это явно.

Answer 4

Это общая проблема с множеством рекурсивных решений.(также для ряда Фибоначчи).

Обычно вы используете то, что называется «Динамическое программирование», где вы повторяете, но проверяете, было ли вычислено значение раньше («памятка»).Крайне сомнительно, что компилятор оптимизирует это для вас.

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

Answer 5

Вы можете добиться этого в общем, используя AOP. Вот оно,

• Перехватить вызов метода
• Возвращать результат, если его можно найти на основе значений класса, метода и аргумента.в кеше.
• Если нет, продолжите вызов и поместите возвращаемое значение в кэш.
• Вернуть результат.

Answer 6

Оценка арифметического выражения, такого как это, сохраняется в стеке. Существует стек для различных рекурсивных вызовов, а затем для каждого вызова есть стек, используемый для оценки выражения внутри функции. Это механизм «запоминания» частичных результатов в каждой точке оценки.

Это то, что вы спрашиваете?

Answer 7

Как правило, Java не кэширует значение вызовов методов.JIT-компилятор может оптимизировать некоторые выражения, если код достаточно прост, чтобы рассуждать, но это не может быть сделано в общем случае, так как могут быть побочные эффекты (Кроме того, некоторые функциональные языки, такие как Haskell, не допускают побочные эффекты).Эффекты могут избежать этой проблемы).

Однако, если у вас есть алгоритм, который много делает подобные вычисления, вы можете захотеть заглянуть в памятку, чтобы кэшировать результаты предыдущих вычислений.Динамическое программирование использует это много.