Предотвращение переполнения стека с помощью функции Аккермана в R - PullRequest
Новая
       48

Предотвращение переполнения стека с помощью функции Аккермана в R

2 голосов
/ 05 апреля 2019

Недавно я увидел интересное Компьютерное видеофайл о функции Аккермана и попытался воссоздать его в R, вот что я придумал: 

Ackermann <- function(m,n){

  if (m == 0){

    return(n+1)

  } else if (m > 0 & n == 0){

    return(Ackermann(m-1,1))

  } else if (m > 0 & n > 0){

    return(Ackermann(m-1,Ackermann(m,n-1)))

  }

}

в видео, которое они реализовалисвою собственную версию кода (я думаю, на C), и объяснил, что требуется огромное количество рекурсивных вычислений для конкретных пар значений, таких как 4,1, и им понадобилось 3 минуты, чтобы вычислить это значение.Если я пытаюсь воссоздать это в R с помощью моего алгоритма, я получаю переполнение стека: 

Error: C stack usage  7971652 is too close to the limit

Есть ли способ получить результат для Аккермана (4,1) в R?

1 Ответ

1 голос
/ 06 апреля 2019

Я думаю, что это возможно, но, вероятно, довольно сложно. Если вы напишите это так (см. Ниже), это не выдаст ошибку, но это займет довольно много времени: 

sub_Ackermann1 <- function(df){
  i <- nrow(df)
  m <- df$m[i]
  n <- df$n[i]
  if (m == 0){
    r <- n+1
    df$r[i] <- r
    df_i <- df} 
  else if (m > 0 & n == 0){
    r <- NA
    m <- m-1
    n <- 1
    df_i <- df
    newrow <- data.frame(m=m,n=n,r=r)
    df_i <- rbind(df_i,newrow)} 
  else if (m > 0 & n > 0){
    r1 <- NA
    m1 <- m-1
    n1 <- NA
    df_i <- df
    newrow1 <- data.frame(m=m1,n=n1,r=r1)
    df_i <- rbind(df_i,newrow1)

    r2 <- NA
    m2 <- m
    n2 <- n-1
    newrow2 <- data.frame(m=m2,n=n2,r=r2)
    df_i <- rbind(df_i,newrow2)}

  return(df_i)
}

sub_Ackermann2 <- function(df){
  r <- df$r[nrow(df)]
  if (is.na(df$n[nrow(df)-1])){ 
    df$n[nrow(df)-1] <- r }
  else if (is.na(df$r[nrow(df)-1])){ df$r[nrow(df)-1] <- r}
  df_i <- df[-nrow(df),] 
  return(df_i)
}
Ackermann <- function(m,n){
  df <- data.frame(m=m,n=n,r=NA)
  if (m == 0){df$r <- n+1} 
  while (is.na(df$r[1])){
    if (is.na(df$r[nrow(df)])){ df <- sub_Ackermann1(df)}
    else if (is.na(df$r[1])){ df <- sub_Ackermann2(df)}
  }
  return(df$r[1])

}

Работает как минимум при меньших значениях и не падает при больших значениях. Может быть, кто-то может показать, что это не может работать или наоборот , есть идеи, как это оптимизировать ...

...