массив скриптов bash для запоминания последовательности Фибоначчи - PullRequest
Новая
       41

массив скриптов bash для запоминания последовательности Фибоначчи

0 голосов
/ 09 ноября 2018

Невозможно сохранить значения Фибоначчи в ассоциативный массив для умножения. Этот сценарий принимает индекс Фибоначчи в качестве аргумента и возвращает соответствующее значение последовательности значений. При каждом выполнении скрипта генерируется новая последовательность от 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 обрабатывает рекурсивные функции.

Любые идеи будут с благодарностью.

1 Ответ

0 голосов
/ 09 ноября 2018

вместо 

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

Вы, вероятно, хотели написать 

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

Однако это не решило бы реальной проблемы. Как мы видим из вашего журнала, массив памятки всегда содержит не более одной записи. Как это возможно, что последняя запись заполнена, но записи, необходимые для вычисления этой последней записи, равны 0? Ответ »подоболочки« !

Когда вы вызываете свою функцию с использованием подоболочки $(fib ...), изменения, которые функция вносит в переменные, находятся только внутри подоболочки. Чтобы обойти эту проблему, вы должны либо использовать файл для запоминания, либо найти способ вызвать вашу функцию без вложенной оболочки.

Вот как я написал бы этот сценарий, если бы меня заставили использовать ваш текущий подход. Обратите внимание, что есть лучшие способы вычисления чисел Фибоначчи и лучшие языки для программирования этих вычислений. 

#! /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.

Улучшения: * * тысяча двадцать-один

  • Чтобы обойти проблему subshell, не отображайте результат функции и сохраняйте его, используя var=$(fib ...), но храните молчание и сохраняйте результат непосредственно в назначенной глобальной переменной. Здесь нам не нужна новая переменная, потому что у нас уже есть массив памятки. Сначала мы вызываем fib x, чтобы убедиться, что запись массива x есть, а затем получаем доступ к этой записи с помощью memo[x].
  • Вместо печати в журнал выведите отладочную информацию в stderr, используя >&2 echo.
  • Сохраняя fib(0)=0 в массиве памятки, нам не нужно использовать смещение индекса.
  • Вставить тривиальные случаи 0 и 1 непосредственно в массив памятки.
  • Не инициализировать массив с 0.
    ${memo[n]}+x расширяется до x тогда и только тогда, когда fib(n) уже запомнено.
...