在比较答案中两个函数的效率时检查列表是否包含 R 中的另一个列表 https://stackoverflow.com/a/39350733/4408538，我偶然发现了一个有趣的结果。排序大大提高了效率duplicated当向量很大时。这让我感到惊讶，因为我从来没有注意到我自己的工作中使用duplicated。事实上，对于我每天使用的尺寸来说，没有什么区别。观察：

set.seed(1007)
s1 <- sample(10^2, 10^3, replace = TRUE)
s1_sort <- sort(s1)
library(microbenchmark)
microbenchmark(dp=duplicated(s1), dp_sort=duplicated(s1_sort), times=1000)
Unit: microseconds
   expr    min      lq     mean  median      uq      max neval cld
     dp 16.459 16.9425 22.06371 17.2965 22.5050 1541.137  1000   a
dp_sort 17.007 17.5005 25.54953 17.8200 23.3655 1549.198  1000   a

正如您所看到的，向量排序时的时间没有明显的差异。然而，对于非常大的向量，结果有很大不同。观察：

s2 <- sample(10^6, 10^7, replace = TRUE)
s2_sort <- sort(s2)
microbenchmark(dp=duplicated(s2), dp_sort=duplicated(s2_sort), times=100)
Unit: milliseconds
   expr      min       lq     mean   median       uq       max neval cld
     dp 816.6883 847.9231 869.6829 861.8210 882.3978 1019.6339   100   b
dp_sort 287.6779 305.4779 322.8830 315.1198 324.9249  449.1734   100  a 

几乎快了 3 倍！！！这让我陷入了兔子洞，它从这里开始：r-源.../重复.R https://github.com/SurajGupta/r-source/blob/master/src/library/base/R/duplicated.R。从这里我们看到，duplicated 调用了.Internal(duplicated(x,...))。然后使用该函数pryr::show_c_source(.Internal(duplicated(x)))和解决方法 https://github.com/hadley/pryr/issues/48由 @joran 建议（show_c_source目前出现问题..参见'show_c_source()' 坏了吗？ https://stackoverflow.com/q/38353760/4408538），我们看到duplicated打电话给。最后，heart https://github.com/wch/r-source/blob/6e7a2ed989027f3800d2e2d64e60e6d700034c6b/src/main/unique.c#L667 of duplicated显示（从第 667 行开始，到第 988 行结束）。看起来整个向量被循环，然后发生一些散列：

724     /* count unique entries */
725     k = 0;
726     for (i = 0; i < n; i++)
727         if (LOGICAL(dup)[i] == 0)
728             k++;

776     /* Build a hash table, ignoring information on duplication */
777     static void DoHashing(SEXP table, HashData *d)

我不完全理解所有代码，但似乎排序并不重要。无论哪种情况（排序与非排序），我们都会循环遍历整个向量，并最终调用各种哈希函数，这不应该取决于向量是否排序。我最初的想法是正在进行某种分支预测（请参阅这个问题 https://stackoverflow.com/q/11227809/4408538），但是从更新到这个答案 https://stackoverflow.com/a/11227902/4408538，看来这些事情应该已经不重要了。

这是怎么回事？？

EDIT

随着向量大小和重复项数量的增加，差距似乎也在增加。

set.seed(496)
s3 <- sample(10^6, 10^8, replace = TRUE)
s3_sort <- sort(s3)
microbenchmark(dp=duplicated(s3), dp_sort=duplicated(s3_sort), times = 10)
Unit: seconds
   expr       min        lq      mean    median        uq       max neval cld
     dp 12.149932 12.175665 12.848843 12.495599 12.719861 15.589190    10   b
dp_sort  2.395636  2.401837  2.706674  2.551375  2.677556  4.373653    10  a 

正如@alexis_laz指出的，如果没有重复项，排序的影响就会大大减少。

s4 <- sample(10^8)
s4_sort <- sort(s4)
microbenchmark(dp=duplicated(s4), dp_sort=duplicated(s4_sort), times = 10)
Unit: seconds
   expr      min       lq     mean   median       uq       max neval cld
     dp 8.013995 8.130565 8.593626 8.197501 8.438703 10.639452    10   b
dp_sort 6.135788 6.158140 6.751101 6.256739 7.241381  8.913507    10  a 

主要因素是 CPU 缓存未命中率，并且随着大小的增加，页面错误的代价也会更高。通过参考简单的哈希表来检查重复。如果被查询的哈希表部分已经在高速内存缓存中，那么这些查找会快得多。对于小向量，相应的哈希表将完全适合高速内存缓存，因此访问顺序并不重要，这就是您在第一个基准测试中看到的。

对于较大的向量，在任何给定时间只有哈希表的某些块适合缓存。如果重复项是连续的，则查找所需的哈希表部分将已经在缓存中以供后续查找。这就是为什么性能会随着较大向量的重复次数而提高。对于非常大的向量，哈希表甚至可能无法完全适合可用的物理内存并被分页到磁盘，从而使差异更加明显。

为了测试这一点，让我们使用原始帖子的s2向量及其排序版本，但也测试是否使重复项彼此相邻，但否则未排序。

# samples as in original post
s2 <- sample(10^6, 10^7, replace = TRUE)
s2_sort <- sort(s2)

# in the same order as s2, but with duplicates brought together
u2 <- unique(s2)
t2 <- rle(s2_sort)
s2_chunked <- rep(u2,times=t2$length[match(u2,t2$values)])

我们还考虑仅按哈希值排序。我将近似 R 中的哈希编码，但我们在这里处理的是双倍大小的值，而不是能够使用无符号长整型，因此我们将无法使用按位运算。

# in the order of hash value
K <- ceiling(log2(length(s2)*2))
M <- 2^K
h <- ((3141592653 * s2) %% 2^32)/2^(32-K)
ho <- order(h)
s2_hashordered <- s2[ho]

我们期望看到的是性能相似s2_sort and s2_chunked甚至更好s2_hashordered。在每种情况下，我们都尝试最大限度地减少缓存未命中。

microbenchmark(
 duplicated(s2), 
 duplicated(s2_sort), 
 duplicated(s2_chunked),
 duplicated(s2_hashordered),
 times=10)

Unit: milliseconds
                       expr      min       lq     mean   median       uq      max neval cld
             duplicated(s2) 664.5652 677.9340 690.0001 692.3104 703.8312 711.1538    10   c
        duplicated(s2_sort) 245.6511 251.3861 268.7433 276.2330 279.2518 284.6589    10  b 
     duplicated(s2_chunked) 240.0688 243.0151 255.3857 248.1327 276.3141 283.4298    10  b 
 duplicated(s2_hashordered) 166.8814 169.9423 185.9345 185.1822 202.7478 209.0383    10 a