linux - 用于内存斐波那契数列的 bash 脚本数组

Question

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

fab.sh

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

# initialize SAVED array
SAVED=()

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

fib () {
  local currentIndex=$1

  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 [[ $1 -eq 0 ]]
then
  echo "Sequence limit must be at least 1"
elif [[ $1 -gt 0 ]]
then
  fib $(($1 - 1)) 
fi

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

$ 3

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

输出的 log.txt 文件是:

0 0 1 0 0
0 0 0 2 0
0 0 1 0 0
0 0 0 0 3

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

如有任何见解，我们将不胜感激。

Answer 1

代替

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

你可能想写

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

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

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

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

#! /bin/bash
memo=(0 1)
fib() {
        >&2 printf %s "fib($1) memo=(${memo[*]}) => "
        local n="$1"
        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 "$1"
echo "${memo[$1]}"

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

改进:

• 要解决 subshel​​l 问题，不要回显函数结果并使用 var=$(fib ...) 存储它，而是保持沉默并直接将结果存储在指定的全局多变的。这里我们不需要新变量，因为我们已经有了内存数组。我们首先调用 fib x 以确保数组条目 x 存在，然后我们使用 memo[x] 访问该条目。
• 不是打印到日志，而是使用 >&2 echo 将调试信息打印到 stderr。
• 通过将 fib(0)=0 存储在内存数组中，我们不必使用索引偏移量。
• 将简单情况 0 和 1 直接嵌入到内存数组中。
• 不要用0初始化数组。
  ${memo[n]}+x 扩展为 x 当且仅当 fib(n) 已被内存。