bash 用于记忆斐波那契数列的脚本数组

Question

无法将 Fibonacci 值保存到关联数组以进行 momoization。此脚本将斐波那契指数作为参数，并 returns 关联值序列值。在每次脚本执行时，都会生成一个从 1 到参数值的新序列。记忆化应该减少整体运行时间。

fab.sh

if [ -f log.txt ]; then
  rm log.txt
fi

# initialize SAVED array
SAVED=()

# populate saved with  of 0's
for i in $(eval echo {0..$((-1))}); do
  SAVED[i]=0
done

fib () {
  local currentIndex=

  if [ "$currentIndex" -eq 0 ]
  then
    echo 0
  elif [ "$currentIndex" -eq 1 ] ; then
    echo 1
  elif [[ ${SAVED[$currentIndex]} -ne 0 ]]; then
    echo 'MEMOIZED' >> log.txt
    echo ${SAVED[$currentIndex]}
  else
    SAVED[$currentIndex]=$((`fib $[$currentIndex - 1]`+`fib $[$currentIndex - 2]`))
    echo ${SAVED[@]} >> log.txt
    echo ${SAVED[$currentIndex]}
  fi
}

if [[  -eq 0 ]]
then
  echo "Sequence limit must be at least 1"
elif [[  -gt 0 ]]
then
  fib $(( - 1)) 
fi

如果 fab.sh 是运行使用 $ source fab.sh 5:

$ 3

它正在打印正确的值，但记忆功能不起作用。

输出的log.txt文件是：

似乎 'SAVED' 数组正在重置或分配的值未保留。由于 SAVED 数组是一个全局变量，我认为这会起作用。它可能与 bash 如何处理递归函数有关。

任何见解将不胜感激。

Answer 1

而不是

SAVED[$currentIndex]=$((`fib $[$currentIndex - 1]`+`fib $[$currentIndex - 2]`))

你可能想写

SAVED[currentIndex]=$((`fib $((currentIndex - 1))` + `fib $((currentIndex - 2))`))

但是，这并不能解决实际问题。正如我们从您的日志中看到的那样，记忆数组始终最多只有一个条目。怎么可能填满最后一个条目，但计算最后一个条目所需的条目为 0？答案是 »subshells«!

当您使用子外壳 $(fib ...) 调用函数时，函数对变量所做的更改仅在子外壳内。要解决此问题，您必须使用文件进行记忆或找到一种无需子 shell 即可调用函数的方法。

如果我被迫使用您目前的方法，我会这样写那张纸条。请注意，有更好的方法来计算斐波那契数，也有更好的语言来编写这些计算程序。

#! /bin/bash
memo=(0 1)
fib() {
        >&2 printf %s "fib() memo=(${memo[*]}) => "
        local n=""
        if [ "${memo[n]+x}" ]; then
                >&2 echo lookup
                return
        fi
        >&2 echo compute
        fib "$((n-1))"
        fib "$((n-2))"
        ((memo[n]=memo[n-1]+memo[n-2]))
}
fib ""
echo "${memo[]}"

以>&2开头的行仅用于打印调试信息；你可以删除它们。要抑制调试输出，运行脚本为 script.sh 12 2> /dev/null.

改进：

要解决 subshell 问题，不要回显函数结果并使用 var=$(fib ...) 存储它，而是保持沉默并直接将结果存储在指定的全局变量中。这里我们不需要新变量，因为我们已经有了记忆数组。我们首先调用 fib x 以确保数组条目 x 存在，然后我们使用 memo[x] 访问该条目。
使用 >&2 echo.

stderr

通过将 fib(0)=0 存储在记忆数组中，我们不必使用索引偏移量。
将简单的案例 0 和 1 直接嵌入到记忆数组中。
不要用 0 初始化数组。
${memo[n]}+x 扩展为 x 当且仅当 fib(n) 已经被记忆。

bash 用于记忆斐波那契数列的脚本数组

bash script array to memoize fibonacci sequence

linux

bash

memoization

dynamic-programming

fibonacci

fab.sh