GTIN-13算法的高效实现

Question

我正在寻找一种有效的方法来实现 GTIN-13 check digit algorithm. I have looked at some relevant SO posts such as this and this，但在这两种情况下，效率似乎都不是关注的主题。

简而言之，该算法采用一个数字字符串（例如 123765）并将每隔一个数字（从右到左）乘以 1 或 3 来计算和（因此 5 * 1 + 6 * 3 + 7 * 1 + 3 * 3 + 2 * 1 + 1 * 3 = 44），然后减去这个和从等于或大于此总和的最接近的 10 的倍数（在本例中为 50 - 44 = 6）导出最终校验位（此处为 6）。输入的长度预计为 12 位，但如果较短，则可以简单地从左侧用零填充（因此 123765 实际预期为 000000123765），但结果仍然相同。

一个天真的实现如下：

gtin13 <- function(n) {
  s <- as.character(n)
  check.sum <- 0
  for (i in 1:nchar(s)) {
    digit <- substr(s, nchar(s) - i + 1, nchar(s) - i + 1)
    check.sum <- check.sum + as.numeric(digit) * ifelse(i %% 2, 1, 3)
  }
  10 - check.sum %% 10
}

但是，由于 for 循环以及转换为字符串和返回数字，这是低效的。例如：

df <- data.frame(
  num <- sample(1:1000000, 100000, T)
)
system.time(cd <- vapply(df$num, gtin13, 0))

在普通桌面上大约需要 6 秒。

用什么计算这个check.sum更有效？

Answer 1

我们可以做得更好。如果我们对整数而不是字符进行操作，我们会看到效率的巨大提升：

gtim13Challenger <- function(n) {
    n <- as.integer(n)
    len <- as.integer(ceiling(log10(n)))
    digs <- n %/% as.integer(10^(0L:(len - 1L))) %% 10L
    if (len > 1L)
        digs[seq.int(2L,len,2L)] <- digs[seq.int(2L,len,2L)] * 3L
    10L - sum(digs) %% 10L
}

system.time(cd <- vapply(df$num, gtim13, 0))
user  system elapsed 
6.15    0.00    6.16 

system.time(cd2 <- vapply(df$num, gtim13Challenger, 0L))
user  system elapsed 
0.76    0.00    0.76 

all.equal(cd, cd2)
[1] TRUE

Answer 2

此版本不需要 vapply，因此速度更快，因为我们不会遍历 R 中可能的数字数。例如

gtim13_vec <- function(x) {
  d <- x %% 10
  for(i in 1:12) { # Input can be up to 12 digits
    d <- d +(x%/% 10^i %% 10) * c(1,3)[1+i%%2]
  }
  d
  10-(d%%10)
}

我在这个实验中使用了 set.seed(7)。我看到了

system.time(r1 <- vapply(df$num, gtim13, 0))
#    user  system elapsed 
#    3.21    0.00    3.36 
system.time(r2 <- gtim13_vec(df$num))
#    user  system elapsed 
#    0.03    0.00    0.03 
all(r1==r2)
# [1] TRUE

所以速度有了很大的提升。

Answer 3

使用 Rcpp：

#include <Rcpp.h>
using namespace Rcpp;

int gtim13_cpp(int x) {

  int r, sum = 0, coeff = 1;
  while (x != 0) {
    r = x % 10;
    sum += coeff * r;
    coeff = 4 - coeff;  // 3 <--> 1
    x /= 10;
  }

  return 10 - (sum % 10);
}

// [[Rcpp::export]]
IntegerVector gtim13_all_cpp(IntegerVector x) {

  int n = x.size();
  IntegerVector res(n);
  for (int i = 0; i < n; i++) {
    res[i] = gtim13_cpp(x[i]);
  }

  return res;
}


/*** R
gtim13_all_cpp(123765)

gtin13 <- function(n) {
  s <- as.character(n)
  check.sum <- 0
  for (i in 1:nchar(s)) {
    digit <- substr(s, nchar(s) - i + 1, nchar(s) - i + 1)
    check.sum <- check.sum + as.numeric(digit) * ifelse(i %% 2, 1, 3)
  }
  10 - check.sum %% 10
}
df <- data.frame(
  num <- sample(1:1000000, 100000, T)
)
system.time(cd <- vapply(df$num, gtin13, 0))
system.time(cd3 <- gtim13_all_cpp(df$num))
all.equal(cd3, cd)
*/

结果：

> system.time(cd <- vapply(df$num, gtin13, 0))
   user  system elapsed 
  4.105   0.001   4.105 

> system.time(cd3 <- gtim13_all_cpp(df$num))
   user  system elapsed 
  0.004   0.000   0.003 

> all.equal(cd3, cd)
[1] TRUE

GTIN-13算法的高效实现

Efficient implementation of the GTIN-13 algorithm

performance

checksum

r

check-digit