加快计算字符串中最频繁数字的比例，在 R 中

Question

我需要帮助来加速函数来计算重复数字的比例（忽略任何非数字）。该功能有助于在运行任何校验位验证（如果可用的话）之前识别用户的虚假条目。想想假的 phone 号码、假的学号、假的支票帐号、假的信用卡号、假的任何标识符等等。

该函数是的泛化。

这是它的作用。对于指定数量的最常出现的数字，它计算最高数字占字符串中所有数字的比例，忽略所有非数字。如果字符串中没有数字，则为 returns 1.0。所有计算都是在字符串向量上完成的。

library(microbenchmark)
V = c('(12) 1221-12121,one-twoooooooooo', 'twos:22-222222222', '34-11111111, ext.123', 
        '01012', '123-456-789 valid', 'no digits', '', NaN, NA)

Fake_Similarity = function(V, TopNDigits) {
    vapply(V, function(v) {
        freq = sort(tabulate(as.integer(charToRaw(v)))[48:57], decreasing = T);
        ratio = sum(freq[1:TopNDigits], na.rm = T) / sum(freq, na.rm = T)
        if (is.nan(ratio)) ratio = 1
        ratio
    },
    double(1))
}

t(rbind(Top1Digit = Fake_Similarity(v, 1), Top2Digits = Fake_Similarity(v, 2), Top3Digits = Fake_Similarity(v, 3)))

microbenchmark(Fake_Similarity(v, 2))

与输出。标签不重要，但顺序比例必须符合相应字符串的原始顺序。

                                 Top1Digit Top2Digits Top3Digits
(12) 1221-12121,one-twoooooooooo 0.5454545  1.0000000  1.0000000
twos:22-222222222                1.0000000  1.0000000  1.0000000
34-11111111, ext.123             0.6923077  0.8461538  0.9230769
01012                            0.4000000  0.8000000  1.0000000
123-456-789 valid                0.1111111  0.2222222  0.3333333
no digits                        1.0000000  1.0000000  1.0000000
                                 1.0000000  1.0000000  1.0000000
NaN                              1.0000000  1.0000000  1.0000000
<NA>                             1.0000000  1.0000000  1.0000000
Unit: milliseconds
                  expr      min       lq     mean   median       uq      max neval
 Fake_Similarity(v, 2) 1.225418 1.283113 1.305139 1.292755 1.304262 1.769703   100

例如twos:22-222222222有11个数字，全部相同。因此，对于 Top1Digit 我们有 11/11=1，对于 Top2Digits 我们又有 (11+0)/11=1，依此类推。换句话说，无论以何种标准衡量，这都是一个假数字。比方说，一个人的 phone 号码不太可能有相同的数字，包括区号。

Answer 1

您可以使用这个 Rcpp 函数：

#include <Rcpp.h>
using namespace Rcpp;

// [[Rcpp::export]]
double prop_top_digit(const RawVector& x, int top_n_digits) {

  // counts occurence of each character
  IntegerVector counts(256);
  RawVector::const_iterator it;
  for(it = x.begin(); it != x.end(); ++it) counts[*it]--;

  // partially sort first top_n_digits (negative -> decreasing)
  IntegerVector::iterator it2 = counts.begin() + 48, it3;
  std::partial_sort(it2, it2 + top_n_digits, it2 + 10);

  // sum the first digits
  int top = 0;
  for(it3 = it2; it3 != (it2 + top_n_digits); ++it3) top += *it3;

  // add the rest -> sum all
  int div = top;
  for(; it3 != (it2 + 10); ++it3) div += *it3;

  // return the proportion
  return div == 0 ? 1 : top / (double)div;
}

验证：

Fake_Similarity2 <- function(V, TopNDigits) {
  vapply(V, function(v) prop_top_digit(charToRaw(v), TopNDigits), 1)
    }
t(rbind(Top1Digit = Fake_Similarity2(v, 1), 
        Top2Digits = Fake_Similarity2(v, 2), 
        Top3Digits = Fake_Similarity2(v, 3)))
                                 Top1Digit Top2Digits Top3Digits
(12) 1221-12121,one-twoooooooooo 0.5454545  1.0000000  1.0000000
twos:22-222222222                1.0000000  1.0000000  1.0000000
34-11111111, ext.123             0.6923077  0.8461538  0.9230769
01012                            0.4000000  0.8000000  1.0000000
123-456-789 valid                0.1111111  0.2222222  0.3333333
no digits                        1.0000000  1.0000000  1.0000000
                                 1.0000000  1.0000000  1.0000000
NaN                              1.0000000  1.0000000  1.0000000
<NA>                             1.0000000  1.0000000  1.0000000

基准：

microbenchmark(Fake_Similarity(v, 2), Fake_Similarity2(v, 2))
Unit: microseconds
                   expr     min       lq      mean   median      uq     max neval cld
  Fake_Similarity(v, 2) 298.972 306.0905 328.69384 312.5465 328.108 600.924   100   b
 Fake_Similarity2(v, 2)  25.163  27.1495  30.18863  29.1350  30.460  52.975   100  a

Answer 2

这个可能不会与 RCPP 解决方案竞争，但我认为它可以提高效率。此实现的要点是 而不是运行每个 N 的算法，而是一次性运行所有 N 的算法。这意味着我们只需要对每个字符串执行一次 charToRaw，而不是对每个字符串 N 执行一次，以及类似的排序、制表等。然后我们可以使用优化函数 cumsum 和 colSums一次计算所有频率。

library(matrixStats)
Fake_Similarity3 = function(V, N) {
    freq = vapply(V, function(v) {
        s = sort(tabulate(as.integer(charToRaw(v)))[48:57], decreasing = T)
        length(s) = 10
        return(s)
    }, FUN.VALUE = integer(10), USE.NAMES = FALSE)
    cumfreq = colCumsums(freq)
    ratio = t(cumfreq) / (colSums(freq, na.rm = T))
    ratio[!is.finite(ratio) | ratio == 0] = 1
  return(ratio[, N, drop = FALSE])
}

有了这个函数，我们不用调用参数 (V, 1)、(V, 2) 和 (V, 3)，而是调用 (V, 1:3)

 #           [,1]      [,2]      [,3]
 # [1,] 0.5454545 1.0000000 1.0000000
 # [2,] 1.0000000 1.0000000 1.0000000
 # [3,] 0.6923077 0.8461538 0.9230769
 # [4,] 0.4000000 0.8000000 1.0000000
 # [5,] 0.1111111 0.2222222 0.3333333
 # [6,] 1.0000000 1.0000000 1.0000000
 # [7,] 1.0000000 1.0000000 1.0000000
 # [8,] 1.0000000 1.0000000 1.0000000
 # [9,] 1.0000000 1.0000000 1.0000000


microbenchmark::microbenchmark(
    FS1 = t(rbind(Top1Digit = Fake_Similarity(V, 1), Top2Digits = Fake_Similarity(V, 2), Top3Digits = Fake_Similarity(V, 3))),
    FS3 = Fake_Similarity3(V, 1:3)
)

# Unit: microseconds
#  expr     min      lq     mean   median        uq      max neval cld
#   FS1 896.336 958.490 1103.260 1011.800 1145.0125 2494.136   100   b
#   FS3 311.798 336.853  399.983  358.979  408.0855  886.013   100  a

所以，对于前 1、2 和 3 位数字，它比原来的速度快大约 3 倍。使用的高位数字越多，相对于原始数字就越好。

加快计算字符串中最频繁数字的比例，在 R 中

Speed up the calculation of proportion of most frequent digits in a string, in R

string

performance

r

max

digits