递归 Lua 函数中循环和条件的优化

Question

The following is the code of my function 


function myfunction ( ... )
  local tbl = table.pack(...)
  for _, v in ipairs(tbl) do
  if type(v) ~= 'number' then
  print('Error: Something different is expected.') 
  return
  elseif v~= math.abs(v) then
   print('Error: Your input needs slight modification.')
   return
  end
  end
 
    if some condition then 
      **recursive call to myfunction**
    else
      some result
    end
  end

该功能运行良好，并为我提供了预期的结果。但是可以观察到函数以递归方式调用自身的问题。因此，我在下面给出的代码的第一部分在每次递归调用期间也会重复多次。显然我只想检查一次输入，如果输入不正确则退出函数。如果输入正确，则不应在每次递归调用时都检查它。那么如何为此目的优化代码。是否可以将某个值分配给全局变量，然后在函数内部的某处使用它（在 if else 条件下）以避免重复。但是再次检查价值将得到重复（尽管与当前方法相比成本更低。问题是避免重复以下代码（这是上面代码的一部分）。

for _, v in ipairs(tbl) do
  if type(v) ~= 'number' then
  print('Error: Something different is expected.') 
  return
  elseif v~= math.abs(v) then
   print('Error: Your input needs slightly modified')
   return
  end
  end

例如，考虑以下函数。

function factorial(n)
    if (n == 0) then
        return 1
    else
        return n * factorial(n - 1)
    end
end

当执行factorial(9.3)时，由于不涉及错误输入检查，它会导致堆栈溢出。为了处理这个问题，添加了以下错误机制。

function factorialwithinputcheck(n)
  if type(n) ~= 'number' then
    error('only numbers are expected')
    return
elseif n~= math.floor(n)  or n~=math.abs(n) then
  error('only positive integers are expected')
  return
end
    if (n == 0) then
        return 1
    else
        return n * factorialwithinputcheck(n-1)
    end
end

此函数会在输入不正确时给出错误并停止执行。 factorialwithinputcheck(9.3) 不会导致堆栈溢出。但是再次在每次递归调用中进行输入检查。如何优化此代码？

Answer 1

在我的评论中更具体，我建议这样：

function _factorial(n)
    if (n == 0) then
        return 1
    else
        return n * _factorial(n-1)
    end
end

function factorialwithinputcheck(n)
  if type(n) ~= 'number' then
    error('only numbers are expected')
    return
elseif n~= math.floor(n)  or n~=math.abs(n) then
  error('only positive integers are expected')
  return
end
    if (n == 0) then
        return 1
    else
        return n * _factorial(n-1)
    end
end

或隐藏_factorial:

function factorialwithinputcheck(n)
    local function _factorial(n)
        if (n == 0) then
            return 1
        else
            return n * _factorial(n-1)
        end
    end
  if type(n) ~= 'number' then
    error('only numbers are expected')
    return
elseif n~= math.floor(n)  or n~=math.abs(n) then
  error('only positive integers are expected')
  return
end
    if (n == 0) then
        return 1
    else
        return n * _factorial(n-1)
    end
end

但同样，我不完全确定这种方式是否必须多次“创建”_factorial 函数（这也会对性能产生影响）。但也许这可以通过一些基准测试来解决。

~~编辑：哦，如果你想要一些输入净化：到目前为止，你不检查负数。~~

Edit2：并且由于您要求对阶乘函数进行一般优化。是的，当然可以将递归过程转换为迭代过程（避免多次创建新的堆栈帧）。

使用某种 累加器 (acc) 将 n*acc 传递给下一个调用，您也可以使函数尾部递归，（根据到 this pil chapter（我希望在更频繁的 lua 版本中没有变化）lua 将为您处理）。例如：

local function factorial_rec(n)
    local function _factorial(n)
        if (n == 0) then
            return 1
        else
            return n * _factorial(n-1)
        end
    end
  if type(n) ~= 'number' then
    error('only numbers are expected')
    return
elseif n~= math.floor(n)  or n~=math.abs(n) then
  error('only positive integers are expected')
  return
end
    if (n == 0) then
        return 1
    else
        return n * _factorial(n-1)
    end
end

（但老实说，如果我从 0 到 40 遍历 factorial，我看不出有多少性能提升（0.000293s vs 0.000354s，以 21! 开头的数字已经超出 lua 中的数字范围（对于我的安装），仅使用非常基本的基准进行检查））

递归 Lua 函数中循环和条件的优化

Optimization of Loops and conditionals in Recursive Lua Function

optimization

lua

loops

function

lua-table