计算字符串中的回文数量

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

更新(NEW VERSION WIHTOUT LEN 1 COMPARASION):

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
}