bash脚本数组来存储fibonacci序列

Question

无法将Fibonacci值保存到关联数组中进行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

如果使用$ 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"数组似乎正在重置，或者分配的值没有持久化。由于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初始化数组
  ${memo[n]}+x扩展到x，当且仅当fib(n)已被存储