Ошибка: использование стека C 7970184 слишком близко к пределу

Я хотел бы вычислить функцию RSI, которая задается следующим образом:

RSI = 100 * RS / ( 1 + RS ), where        RS = n_up / n_down

                             and   n_up( t ) = ( 1 - b ) *   n_up( t - 1 )
                                             +       b   *      U( t     ),

                             and n_down( t ) = ( 1 - b ) * n_down( t - 1 )
                                             +       b   *      D( t     ).  

                             where    U( t ) = 1  for P( t ) >  P( t - 1 ) and
                                               0  otherwise;

                             and      D( t ) = 1  for P( t ) <  P( t - 1 ) and
                                               0  otherwise.

Итак, вот мой код:

p <- data[,6]


rsi <- function(P,t,n)
{
  U <- function(P,t)
  {
    if (diff(P)[t] > 0) 
    {
      return(1)
    } else {
      return(0)
    }
  }

  D <- function(P,t)
  {
    if (diff(P)[t] < 0) 
    {
      return(1)
    } else {
      return(0)
    }
  }

  recursive.n_up <- function(P,t,b)
  {
    return((1-b)*recursive.n_up(P,t-1,b) + b*U(P,t))
  }

  recursive.n_down <- function(P,t,b)
  {
    return((1-b)*recursive.n_down(P,t-1,b) + b*D(P,t))  
  }

  b <- 2/(n+1)
  rs <- function(P,t,b)
  {
    return(recursive.n_up(P,t,b)/recursive.n_down(P,t,b))
  }
  return(100*rs(P,t,b)/(1+rs(P,t,b)))
}

n <- 14
RSI <- rep(0,length(p)-1)
for (i in 1:length(RSI))
{
  RSI[i] <- rsi(p,i,n)
}

print(RSI)

Я получаю сообщение об ошибке:

Использование стека C 7970184 слишком близко к пределу

Итак, я хочу знать, очень ли плох мой дизайн алгоритма или этого следует ожидать при использовании рекурсивных функций? Спасибо, что помогли мне решить эту проблему.


r recursion quantitative-finance
person QFi    schedule 25.11.2017    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Да, ваша формулировка рекурсии плоха,
как технически, так и с точки зрения производительности:

Хотя известна рекурсия, которая может помочь разумно сформулировать некоторые проблемы, основная логика заключается в том, что у нее должна быть некоторая «нижняя» черта, где рекурсия останавливается от любого более глубокого погружения — будучи легко решаемой точкой — из которого до сих пор вложенные рекурсии начинают возвращаться обратно и (находясь в пути обратно к первому вызывающему) процесс возврата рекурсии собирает правильный ответ как побочный эффект этого выхода обратно с самого глубокого уровня из этого известная, легко определяемая точка известного возвращаемого значения.

Проще говоря, это отсутствует в вашей алгоритмизации.

Ваш код будет пытаться погружаться все глубже и глубже (назад во времени) даже на самом первом историческом баре данных TimeSeries.

Если вы справитесь с этим случаем должным образом, код перестанет свою сукцидальную привычку нырять бесконечно глубоко и начнет собирать результат.

Далее идет производительность:

Рекурсия хороша для универсального исчисления.

Рекурсия — плохая идея для повторяющихся вычислений, если уже рассчитанные «шаги» снова пересчитываются, если политика повторного использования плохих значений заставляет снова и снова возвращаться назад снова и снова к тому же самому «терминалу». point», только из-за оригинальной (предварительно неоптимизированной) формулировки рекурсии.

Покажем это на факториале.

Используя его тривиальную, самую простую форму рекурсии в иллюстративных целях, в то время как все принципы применимы к любой более сложной обработке на основе рекурсии - этот просто подходит только для одного SLOC:
factorial( N ) = ( N == 1 ) ? 1 : N * factorial( N - 1 )

Если бы это было для вычисления только одного factorial( 15 ), нельзя было бы возразить ни одним словом против того, чтобы пройти всю цепочку:

fact15 = ( 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 )

где отсутствие любого шага приведет к тому, что процесс не сможет правильно вычислить факториал.

Проблема выглядела бы в другом свете, если бы следующей задачей было вычислить только следующую -- factorial( 16 )

реализация, не учитывающая производительность, пойдет по той же полосе туда и обратно:

fact16 = ( 16 * 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 )

тогда как умная, ориентированная на производительность реализация никогда не повторит хвостовую часть цирка, а просто умножит головную часть:

fact16 = ( 16 * fact15 )

никогда не повторяя часть, которая уже была вычислена один раз.

Вы видите влияние?

И представьте масштабы этой очевидной разницы, когда глубины рекурсии выросли до каких-то замечательных сотен, тысяч, десятков тысяч, сотен тысяч, миллионов шагов рекурсии... повторяя каждый из них в следующий раз снова и снова и снова. Нет никогда.

Это основная логика всей высокопроизводительной обработки данных TimeSeries с малой задержкой, RSI является очевидным случаем, с которым вы столкнулись самостоятельно.

person user3666197    schedule 25.11.2017

arrow_upward
2
arrow_downward

Я полностью согласен с предыдущим ответом, предоставленным user3666197; у вас нет условия остановки в вашей рекурсивной функции. Это будет продолжаться и продолжаться....

Кроме того, вы делаете что-то очень неэффективное в функции. Вы рассчитываете

return( 100 *       rs( P, t, b )
            / ( 1 + rs( P, t, b )
              )
        )

Таким образом, rs(...) вычисляется дважды с одними и теми же параметрами. Почему бы и нет:

Z <- rs( P, t, b )
return( 100 * Z / ( 1 + Z )

Вам нужно будет интегрировать правильное условие остановки.

person Bhas    schedule 25.11.2017
comment
Основная неэффективность заключается не в двойном выполнении рекурсии за один временной шаг, а в повторении всех прошлых шагов рекурсии на каждом следующем шаге. Это основной убийца производительности в наивной обработке данных TimeSeries... - person user3666197; 25.11.2017

arrow_upward
1
arrow_downward

Для меня я очистил R, используя следующее, и все заработало:

#Clear plots
if(!is.null(dev.list())) dev.off()

# Clear console
cat("\014") 

# Clean workspace
rm(list=ls())
person Sruthi Poddutur    schedule 27.11.2018