时间戳

首页 > 解决方案 > GTIN-13算法的高效实现

r - GTIN-13算法的高效实现

问题描述

我正在寻找一种有效的方法来实现GTIN-13 校验位算法。我已经查看了一些相关的 SO 帖子，例如this和this，但在这两种情况下，效率似乎都不是关注的主题。

简而言之，该算法采用一个数字字符串（例如 123765）并将每隔一个数字（从右到左）乘以 1 或 3 来计算总和 (so 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 更有效的是什么？

标签： rperformancechecksumcheck-digit

解决方案

这个版本不需要 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

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

推荐阅读