Подсчитать количество палиндромов в строке

Question

Я написал следующий код для подсчета количества палиндромных строк в данной строке:

countPalindromes <- function(str){
  len <- nchar(str)
  count <- 0

  for(i in 1:len){
    for(j in i:len){
        subs <- substr(str, i, j)
        rev <- paste(rev(substring(subs, 1:nchar(subs), 1:nchar(subs))), collapse = "")
        if(subs == rev){
          count <- count + 1
        }
      }
  }
  count
}

Это на самом деле работает нормально, но код необходимо оптимизировать таким образом, чтобы он выполнялся с большей скоростью.

Пожалуйста, предложите несколько способов оптимизировать этот фрагмент кода.

Answer 1

Вот решение, которое использует замечательный пакет stringi - как и предлагал Андре - вместе с небольшим векторизацией.

cp <- function(s) {
  lenstr <- stri_length(s)  # Get the length
  res <- sapply(1:lenstr, function(i) {
    # Get all substrings
    sub_string <- stringi::stri_sub(s, i, i:lenstr)
    # Count matches
    sum((sub_string == stringi::stri_reverse(sub_string)))
  })
  sum(res)
}

Это должно дать тот же результат, что и ваша функция

> cp("enafdemderredmedfane")
[1] 30
> countPalindromes("enafdemderredmedfane")
[1] 30

У коротких строк не так много ускорения, но для более длинных строк вы действительно можете увидеть преимущество:

> microbenchmark::microbenchmark(countPalindromes("howdoyoudo"), cp("howdoyoudo"))
Unit: microseconds
                           expr     min       lq     mean   median      uq     max neval cld
 countPalindromes("howdoyoudo") 480.979 489.6180 508.9044 494.9005 511.201 662.605   100   b
               cp("howdoyoudo") 156.117 163.1555 175.4785 169.5640 179.993 324.145   100  a 

По сравнению с

> microbenchmark::microbenchmark(countPalindromes("enafdemderredmedfane"), cp("enafdemderredmedfane"))
Unit: microseconds
                                     expr      min        lq      mean   median       uq      max neval cld
 countPalindromes("enafdemderredmedfane") 2031.565 2115.0305 2475.5974 2222.354 2384.151 6696.484   100   b
               cp("enafdemderredmedfane")  324.991  357.6055  430.8334  387.242  478.183 1298.390   100  a 

Answer 2

Работая с вектором, процесс идет быстрее, я думаю об устранении двойника для, но не могу найти эффективный способ.

countPalindromes_new <- function(str){
  len <- nchar(str)
  strsp <- strsplit(str, "")[[1]]
  count <- 0

  for(i in 1:len){
    for(j in i:len){
      if(all(strsp[i:j] == strsp[j:i])){
        count <- count + 1
      }
    }
  }
  count
}

> microbenchmark::microbenchmark(countPalindromes("howdoyoudo"), cp("howdoyoudo"), countPalindromes_new("howdoyoudo"))
Unit: microseconds
                               expr     min       lq       mean  median       uq      max neval
     countPalindromes("howdoyoudo") 869.121 933.1215 1069.68001 963.201 1022.081 6712.751   100
                   cp("howdoyoudo") 192.000 202.8805  243.11972 219.308  258.987  477.441   100
 countPalindromes_new("howdoyoudo")  49.068  53.3340   62.32815  57.387   63.574  116.481   100
> microbenchmark::microbenchmark(countPalindromes("enafdemderredmedfane"), cp("enafdemderredmedfane"), countPalindromes_new("enafdemderredmedfane"))
Unit: microseconds
                                         expr      min        lq      mean   median        uq       max neval
     countPalindromes("enafdemderredmedfane") 3578.029 3800.9620 4170.0888 3987.416 4173.6550 10205.445   100
                   cp("enafdemderredmedfane")  391.254  438.4010  609.8782  481.708  534.6135  6116.270   100
 countPalindromes_new("enafdemderredmedfane")  200.534  214.1875  235.3501  223.148  245.5475   448.854   100

ОБНОВЛЕНИЕ (НОВАЯ ВЕРСИЯ БЕЗ СРАВНЕНИЯ LEN 1):

countPalindromes_new2 <- function(str){
  len <- nchar(str)
  strsp <- strsplit(str, "")[[1]]
  count <- len

  for(i in 1:(len-1)){
    for(j in (i + 1):len){
      if(all(strsp[i:j] == strsp[j:i])){
        count <- count + 1
      }
    }
  }
  count
}

Answer 3

Просто: обычно я против использования новых библиотек везде. Но stringi - это THE библиотека для работы со строками в R.

string_vec <- c("anna","nothing","abccba")
string_rev <- stringi::stri_reverse(string_vec)
sum(string_vec == string_rev)
#evals 2