我在R中使用的paste0()是否可以被更正，这样这个函数的运行速度和最初的Python示例一样快？

Question

我正在尝试使用一些最近发现的模仿用诺维格(氏)拼写检查器编写的部分edit2的R代码；特别是，我试图找出在R中实现edit2函数的正确方法：

def splits(word):
    return [(word[:i], word[i:]) 
            for i in range(len(word)+1)]

def edits1(word):
    pairs      = splits(word)
    deletes    = [a+b[1:]           for (a, b) in pairs if b]
    transposes = [a+b[1]+b[0]+b[2:] for (a, b) in pairs if len(b) > 1]
    replaces   = [a+c+b[1:]         for (a, b) in pairs for c in alphabet if b]
    inserts    = [a+c+b             for (a, b) in pairs for c in alphabet]
    return set(deletes + transposes + replaces + inserts)

def edits2(word):
    return set(e2 for e1 in edits1(word) for e2 in edits1(e1))

但是，在我的基准测试中，使用paste0 (或者从str_c生成字符串，或者从stri_join生成stri_join)在R中生成数千个小字符串，导致代码比Norvig显示的Python实现慢大约10倍(或~100倍，或~50倍)。(是的，与使用paste0相比，基于字符串和基于字符串的函数的速度更慢。)我的问题是(3号是我想要解决的主要问题)：

1. 我做得对吗(代码“对”)？
2. 如果是这样的话，这是已知的R(极慢的字符串连接)问题吗？
3. 我能做些什么使这个significantly更快(至少是一个或多个数量级)而不需要用Rcpp11重写整个函数或类似的东西？

下面是我为edit2函数编写的R代码：

# 1. generate a list of all binary splits of a word
binary.splits <- function(w) {
  n <- nchar(w)
  lapply(0:n, function(x)
         c(stri_sub(w, 0, x), stri_sub(w, x + 1, n)))
}

# 2. generate a list of all bigrams for a word
bigram.unsafe <- function(word)
  sapply(2:nchar(word), function(i) substr(word, i-1, i))
bigram <- function(word)
  if (nchar(word) > 1) bigram.unsafe(word) else word

# 3. four edit types: deletion, transposition, replacement, and insertion
alphabet = letters
deletions <- function(splits) if (length(splits) > 1) {
   sapply(1:(length(splits)-1), function(i)
          paste0(splits[[i]][1], splits[[i+1]][2]), simplify=FALSE) 
} else {
    splits[[1]][2]
}   
transpositions <- function(splits) if (length(splits) > 2) {
  swaps <- rev(bigram.unsafe(stri_reverse(splits[[1]][2])))
  sapply(1:length(swaps), function(i)
         paste0(splits[[i]][1], swaps[i], splits[[i+2]][2]), simplify=FALSE)
} else {
  stri_reverse(splits[[1]][2])
} 
replacements <- function(splits) if (length(splits) > 1) {
  sapply(1:(length(splits)-1), function(i)
         lapply(alphabet, function(symbol)
                paste0(splits[[i]][1], symbol, splits[[i+1]][2])))
} else {
  alphabet
} 
insertions <- function(splits)
  sapply(splits, function(pair)
         lapply(alphabet, function(symbol)
                paste0(pair[1], symbol, pair[2]))) 

# 4. create a vector of all words at edit distance 1 given the input word
edit.1 <- function(word) {
  splits <- binary.splits(word)
  unique(unlist(c(deletions(splits),
                  transpositions(splits),
                  replacements(splits),
                  insertions(splits))))
}

# 5. create a simple function to generate all words of edit distance 1 and 2
edit.2 <- function(word) { 
  e1 <- edit.1(word)
  unique(c(unlist(lapply(e1, edit.1)), e1))
} 

如果您开始分析这段代码，您将看到replacements和insertions嵌套了"lapplies“，并且似乎比deletions或transpositions长10倍，因为它们生成的拼写变体要多得多。

library(rbenchmark)
benchmark(edit.2('abcd'), replications=20)

这在我的核心i5 MacBook Air上大约需要8秒，而相应的edit2基准测试(运行相应的edit2函数20次)大约需要0.6秒，也就是说大约快10-15倍！

我尝试过使用expand.grid来摆脱内部的lapply，但是这使得代码更慢，而不是更快。我知道使用lapply代替sapply会使我的代码更快一些，但是我不认为使用“错误”函数(我想要一个向量返回)来实现一个小的速度提升的意义。但是，在纯R edit.2中生成函数的结果可能要快得多。

Answer 1

R's paste0与python‘.’.join的性能

最初的标题询问R中的paste0是否比python中的字符串连接慢10倍。如果是的话，那么就没有希望编写一个在R中严重依赖字符串连接的算法，该算法与相应的python算法一样快。

我有过

> R.version.string
[1] "R version 3.1.0 Patched (2014-05-31 r65803)"

和

>>> sys.version '3.4.0 (default, Apr 11 2014, 13:05:11) \n[GCC 4.8.2]'

这是第一个比较

> library(microbenchmark)
> microbenchmark(paste0("a", "b"), times=1e6)
Unit: nanoseconds
             expr min   lq median   uq      max neval
 paste0("a", "b") 951 1071   1162 1293 21794972 1e+06

(因此，对于所有的复制，大约1s )与

>>> import timeit
>>> timeit.timeit("''.join(x)", "x=('a', 'b')", number=int(1e6))
0.119668865998392

我想这就是最初海报观察到的10倍的性能差异。然而，R在向量上工作得更好，而且算法无论如何都涉及到单词的向量，所以我们可能会对比较感兴趣。

> x = y = sample(LETTERS, 1e7, TRUE); system.time(z <- paste0(x, y))
   user  system elapsed 
  1.479   0.009   1.488 

和

>>> setup = '''
import random
import string
y = x = [random.choice(string.ascii_uppercase) for _ in range(10000000)]
'''
>>> timeit.Timer("map(''.join, zip(x, y))", setup=setup).repeat(1)
[0.362522566007101]

这表明，如果我们的R算法以python的1/4速度运行，我们将走在正确的轨道上；OP发现了10倍的差异，因此看起来还有改进的余地。

R迭代与矢量化

OP使用迭代(lapply和朋友)，而不是矢量化。我们可以将向量版本与各种迭代方法进行比较，如下所示

f0 = paste0

f1 = function(x, y) 
   vapply(seq_along(x), function(i, x, y) paste0(x[i], y[i]), character(1), x, y)

f2 = function(x, y) Map(paste0, x, y)

f3 = function(x, y) {
    z = character(length(x))
    for (i in seq_along(x)) 
        z[i] = paste0(x[i], y[i])
    z 
}

f3c = compiler::cmpfun(f3)    # explicitly compile

f4 = function(x, y) {
    z = character()
    for (i in seq_along(x)) 
        z[i] = paste0(x[i], y[i])
    z 
}

缩放数据，将“矢量化”解决方案定义为f0，并对这些方法进行比较

> x = y = sample(LETTERS, 100000, TRUE)
> library(microbenchmark)
> microbenchmark(f0(x, y), f1(x, y), f2(x, y), f3(x, y), f3c(x, y), times=5)
Unit: milliseconds
      expr       min        lq    median        uq       max neval
  f0(x, y)  14.69877  14.70235  14.75409  14.98777  15.14739     5
  f1(x, y) 241.34212 250.19018 268.21613 279.01582 292.21065     5
  f2(x, y) 198.74594 199.07489 214.79558 229.50684 271.77853     5
  f3(x, y) 250.64388 251.88353 256.09757 280.04688 296.29095     5
 f3c(x, y) 174.15546 175.46522 200.09589 201.18543 214.18290     5

由于f4速度太慢，无法包含

> system.time(f4(x, y))
   user  system elapsed 
 24.325   0.000  24.330 

因此，从这里可以看到Tierney博士的建议，即将这些lapply调用向量化可能有好处。

进一步矢量化更新的原始帖子

@民解力量通过部分展开循环采用了原始代码。例如，还有更多相同的机会，

replacements <- function(splits) if (length(splits$left) > 1) {
  lapply(1:(length(splits$left)-1), function(i)
         paste0(splits$left[i], alphabet, splits$right[i+1]))
} else {
  splits$right[1]
}

可以修改为执行单个粘贴调用，依赖于参数回收(可回收的短向量直到其长度匹配较长的向量)。

replacements1 <- function(splits) if (length(splits$left) > 1) {
    len <- length(splits$left)
    paste0(splits$left[-len], rep(alphabet, each = len - 1), splits$right[-1])
} else {
  splits$right[1]
}

这些值是按不同的顺序排列的，但这对算法并不重要。删除下标(前缀为-)可能会提高内存效率。相似

deletions1 <- function(splits) if (length(splits$left) > 1) {
  paste0(splits$left[-length(splits$left)], splits$right[-1])
} else {
  splits$right[1]
}

insertions1 <- function(splits)
    paste0(splits$left, rep(alphabet, each=length(splits$left)), splits$right)

我们就有了

edit.1.1 <- function(word) {
  splits <- binary.splits(word)
  unique(c(deletions1(splits),
           transpositions(splits),
           replacements1(splits),
           insertions1(splits)))
}

有一些加速

> identical(sort(edit.1("word")), sort(edit.1.1("word")))
[1] TRUE
> microbenchmark(edit.1("word"), edit.1.1("word"))
Unit: microseconds
             expr     min       lq   median       uq     max neval
   edit.1("word") 354.125 358.7635 362.5260 372.9185 521.337   100
 edit.1.1("word") 296.575 298.9830 300.8305 307.3725 369.419   100

OP指出他们的原始版本比python慢10倍，并且他们最初的修改导致了5倍的加速。我们获得了更多的1.2倍的速度，因此，也许是在预期的性能，该算法使用R的paste0。下一步是询问替代算法或实现是否具有更高的性能，特别是substr可能是有希望的。

Answer 2

按照@LukeTierney在问题中关于向量化paste0调用和返回两个向量binary.splits的注释中的技巧，我编辑了函数以正确地向量化。我也在他的答案中添加了@MartinMorgan描述的附加修改:使用单个后缀删除条目，而不是使用选择范围(例如，"[-1]"而不是"[2:n]"等等；但是注意:对于transpositions中使用的多个后缀，这实际上要慢一些)，特别是使用rep进一步向量化replacements和insertions中的paste0调用。

这就得到了最好的答案(到目前为止？)在R中实现edit.2 (谢谢，卢克和马丁！)换句话说，在Luke提供的主要提示和Martin随后的一些改进之后，R实现的速度大约是Python的一半(但请参阅Martin在下面的答复中的最后评论)。(如上面所示，函数edit.1、edit.2和bigram.unsafe保持不变。)

binary.splits <- function(w) {
  n <- nchar(w)
  list(left=stri_sub(w, rep(0, n + 1), 0:n),
       right=stri_sub(w, 1:(n + 1), rep(n, n + 1)))
}

deletions <- function(splits) {
  n <- length(splits$left)
  if (n > 1) paste0(splits$left[-n], splits$right[-1])
  else splits$right[1]
}
transpositions <- function(splits) if (length(splits$left) > 2) {
  swaps <- rev(bigram.unsafe(stri_reverse(splits$right[1])))
  paste0(splits$left[1:length(swaps)], swaps,
         splits$right[3:length(splits$right)])
} else {
  stri_reverse(splits$right[1])
}
replacements <- function(splits) {
  n <- length(splits$left)
  if (n > 1) paste0(splits$left[-n],
                    rep(alphabet, each=n-1),
                    splits$right[-1])
  else alphabet
}
insertions <- function(splits)
  paste0(splits$left,
         rep(alphabet, each=length(splits$left)),
         splits$right)

总之，为了结束这个练习，Luke和Martin的建议使R实现运行速度大约是Python代码最初显示的一半，使我的原始代码提高了大约6倍。然而，我更担心的是两个不同的问题：(1) R代码似乎要冗长得多(LOC，但可能会被修饰一点)；(2)即使稍微偏离“正确的向量化”，R代码的性能也会很糟糕，而Python中对“正确的Python”的轻微偏离通常不会产生这样的极端影响。尽管如此，我将继续我的“编码高效R”的努力-感谢大家的参与！