Что означает этот код (если v, то вернуть v end)?

Итак, у меня есть этот фрагмент кода, и он таков:

do 

    local function index(n,m)
        return n*(n+1)//2 + m
    end

    local binomtable = {}

    function binom3(n,m)
        if n<0 or m<0 or m>n then return 0 end
        if n=0 or m=0 or m=n then return 1 end
        local i = index(n,m)
        local v = binomtable[i]
        if v then return v end
        v = binom3(n-1,m-1) + binom3(n-1,m)
        binomtable[i] = v
        return v
    end

end

и я хотел бы знать, что

if v then return v end

означает.

Благодарю вас!


memoization lua
person Community    schedule 30.10.2020    source источник
comment
если он уже вычислил значение для binomtable[i], то он возвращает это значение, в противном случае он продолжит выполнение скрипта и сгенерирует значение для этой позиции в таблице.   -  person Doyousketch2    schedule 31.10.2020
comment
Вы получили принятый ответ. Поэтому я отменяю редактирование тестового вопроса.   -  person Yunnosch    schedule 01.11.2020

Ответы (2)


arrow_upward
2
arrow_downward

Короткий ответ заключается в том, что if v then return v end возвращает значение v, если оно истинно, т. е. если оно не является ни false, ни nil. В противном случае функция продолжает вычислять значение для v, сохранять это значение в binomtable и, наконец, возвращать его. Более интересный вопрос: зачем функция все это делает?

В опубликованном коде binom3 является рекурсивной функцией. С рекурсивными вызовами v = binom3(n-1,m-1) + binom3(n-1,m) будет много дублирования усилий, что означает много потраченного впустую места и времени. Рассмотреть возможность:

binom3(4, 2)
--> binom3(3, 1) + binom3(3, 2)
--> binom3(2, 0) + binom3(2, 1) + binom3(2, 1) + binom3(2, 2)
--> 1 + binom3(1, 0) + binom3(1, 1) + binom3(1, 0) + binom3(1, 1) + 1

Обратите внимание, что во второй редукции два одинаковых термина:

binom3(2, 1) + binom3(2, 1)

Нет причин вычислять термин binom3(2, 1) дважды, и это означает, что пара терминов:

binom3(1, 0) + binom3(1, 1)

также должен быть рассчитан дважды, как видно из третьего сокращения. Было бы разумно вычислить binom3(2, 1) только один раз и сохранить результат для последующего использования в более крупном расчете. Когда m и n больше, а количество вычислений увеличивается экспоненциально, это становится очень важной проблемой для производительности как с точки зрения требуемого объема памяти, так и с точки зрения требуемого времени.

В опубликованном коде используется memoization для повышения производительности. Когда расчет сделан, он сохраняется в таблице binomtable. Прежде чем производить какие-либо расчеты, консультируются с binomtable. Во-первых, v устанавливается равным binomtable[i]; если это значение является любым истинным значением (любое целое число является истинным в Lua), то это значение просто возвращается без необходимости рекурсивного вычисления. В противном случае, если возвращается nil (т. е. значение для вычисления еще не сохранено), функция продолжает рекурсивное вычисление. После завершения расчета новое значение сохраняется в binomtable для использования в следующий раз, когда оно понадобится. Эта стратегия экономит много ненужных вычислительных усилий и может иметь огромное значение в производительности таких рекурсивных алгоритмов.

person ad absurdum    schedule 30.10.2020

arrow_upward
0
arrow_downward

На ваш конкретный вопрос о том, что

if v then return v end

означает, что если v, переменная, не является nil или false, она должна вернуть значение переменной v и прекратить выполнение этой функции.


--Similar
function myfunc(input)
  local MyVar = "I am a string and am not nil!"
  if MyVar then
    return "hi"
  else
    return "hello"
  end

  print("I am not seen because I am unreachable code!")
end

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

Теперь для вашего случая кодов он проверяет table, чтобы увидеть, есть ли у него запись в определенном index, и если это так, он возвращает значение.

person Michael Marshall    schedule 31.10.2020