linux - bash脚本数组来内存斐波那契数列

Question

无法将斐波那契值保存到关联数组以进行 momoization。该脚本采用斐波那契指数作为参数并返回关联的值序列值。每次执行脚本时，都会生成一个从 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

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

$ 3

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

输出的log.txt文件是:

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

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

任何见解将不胜感激。

Answer 1

而不是

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

你可能想写

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

但是，这并不能解决实际问题。正如我们从日志中看到的，内存数组在任何时候都最多有一个条目。怎么可能最后一个条目已被填满，但计算最后一个条目所需的条目却是 0？答案是»子shell<!

当您使用子 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。

改进:

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