Эффективна ли вложенная функция?

Ответ 1

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

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

Я могу говорить только от имени Scala, а именно от вкуса, нацеленного на JVM, поскольку другие вкусы могут действовать по-разному.

Мы можем разделить этот вопрос на два, в зависимости от того, что вы на самом деле имели в виду.

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

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

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

Например, рассмотрим следующую факториальную реализацию в Scala:

def factorial(num: Int): Int = {
  @tailrec
  def fact(num: Int, acc: Int): Int = num match {
    case 0 => acc
    case n => fact(n - 1, acc * n)
  }

  fact(num, 1)
}

На первый взгляд мы имеем рекурсивный метод. Посмотрим, как выглядит байт-код JVM:

private final int fact$1(int, int);
  Code:
   0: iload_1
   1: istore        4
   3: iload         4
   5: tableswitch   { // 0 to 0
                 0: 24
           default: 28
      }
  24: iload_2
  25: goto          41
  28: iload         4
  30: iconst_1
  31: isub
  32: iload_2
  33: iload         4
  35: imul
  36: istore_2
  37: istore_1
  38: goto          0
  41: ireturn

Мы видим здесь, что рекурсия превратилась в итеративный цикл (a tablewitch + инструкция перехода).

Что касается создания экземпляра метода, если наш метод не был хвостовым рекурсивным, время выполнения JVM должно было бы интерпретировать его для каждого вызова, пока C2 compiler находит достаточным такое, чтобы JIT скомпилировал его и снова использовал машинный код для каждого вызова метода.

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

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

Ответ 2

Позвольте проверить его в Lua с/без вложенных функций.

Вариант 1 (внутренний функциональный объект создается при каждом вызове)

local function factorial1(n)
   local function _fac1(n, acc)
      if n == 0 then
         return acc
      else
         return _fac1(n-1, acc * n)
      end
   end

   return _fac1(n, 1)
end

Вариант 2 (функции не вложены)

local function _fac2(n, acc)
   if n == 0 then
      return acc
   else
      return _fac2(n-1, acc * n)
   end
end

local function factorial2(n)
   return _fac2(n, 1)
end

Код бенчмаркинга (рассчитать 12! 10 млн. раз и отобразить время работы процессора в секундах):

local N = 1e7

local start_time = os.clock()
for j = 1, N do
   factorial1(12)
end
print("CPU time of factorial1 = ", os.clock() - start_time)

local start_time = os.clock()
for j = 1, N do
   factorial2(12)
end
print("CPU time of factorial2 = ", os.clock() - start_time)

Выход для Lua 5.3 (интерпретатор)

CPU time of factorial1 = 8.237
CPU time of factorial2 = 6.074

Выход для LuaJIT (JIT-компилятор)

CPU time of factorial1 = 1.493
CPU time of factorial2 = 0.141

Ответ 3

Ответ зависит, конечно, от языка.

В частности, что происходит в Scala, это то, что внутренние функции скомпилированы, поскольку они стояли вне сферы действия функции, в которой они определены.

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

Мы можем легко проверить это, скомпилировав два варианта

Первый - довольно верный порт вашего кода Lua:

class Function1 {

  def factorial(n: Int): Int = {
    def _fac(n: Int, acc: Int): Int =
      if (n == 0)
        acc
      else
        _fac(n-1, acc * n)

    _fac(n, 1)
  }

}

Второй вариант более или менее одинаковый, но хвостовая рекурсивная функция определена вне области factorial:

class Function2 {

  def factorial(n: Int): Int = _fac(n, 1)

  private final def _fac(n: Int, acc: Int): Int =
    if (n == 0)
      acc
    else
      _fac(n-1, acc * n)

}

Теперь мы можем скомпилировать эти два класса с помощью scalac, а затем использовать javap, чтобы посмотреть вывод компилятора:

javap -p Function*.scala

который даст следующий выход

Compiled from "Function1.scala"
public class Function1 {
  public int factorial(int);
  private final int _fac$1(int, int);
  public Function1();
}
Compiled from "Function2.scala"
public class Function2 {
  public int factorial(int);
  private final int _fac(int, int);
  public Function2();
}

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

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

Ответ 4

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

Lua 5.2 Изменения

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

Поскольку вы закодировали (предположив Lua) функцию, назначенную глобальному или локальному, объявленному в более высокой области, вы можете закодировать короткое замыкание самостоятельно (предполагая, что никакой другой код не устанавливает его на что-либо иное, кроме nil или false):

function factorial(n)
  _fac = _fac or function (n, acc)
  …
  end
  …
end

Ответ 5

Я не знаю о lua, но в Scala очень распространены и используются в рекурсивных функциях для обеспечения оптимальной оптимизации:

def factorial(i: Int): Int = {
      @tailrec
     def fact(i: Int, accumulator: Int): Int = {
        if (i <= 1)
           accumulator
        else
           fact(i - 1, i * accumulator)
     }
     fact(i, 1)
  }

Дополнительная информация о хвостохранилище и рекурсии здесь