Блог

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

 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
  

означает.

Спасибо!

Короткий ответ заключается в том, что 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 больше, а количество вычислений растет экспоненциально, это становится очень важной проблемой для производительности как с точки зрения требуемого объема памяти, так и с точки зрения требуемого времени.

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

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

 if v then return v end
  

означает, что if 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

  

если бы эта функция была вызвана, она всегда возвращала бы «hi» вместо «hello», потому что myVar имеет значение true, потому что оно имеет значение. Также print приведенная ниже функция, которая никогда не будет вызвана, потому что она прекращает выполнение функции после return вызова a .

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