Сравнивая эффективность двух функций в ответе Проверить, содержит ли список другой список в R, я наткнулся на интересный результат. Сортировка значительно увеличивает эффективность 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-source.../duplicated.R. Отсюда мы видим, что дубликат вызывает вызов .Internal(duplicated(x,...)). Затем с помощью функции pryr::show_c_source(.Internal(duplicated(x))) и обходной путь, предложенный @joran (show_c_source, в настоящее время дает проблемы.. см. Is 'show_c_source()' borken?), мы видим, что duplicated делает вызов do_duplicated. Наконец, показано сердце 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)

Я не полностью понимаю весь код, но, похоже, сортировка не имеет значения. Мы перебираем весь вектор в любом случае (отсортированный или не отсортированный) и в конечном итоге вызываем набор хеш-функций, который не должен зависеть от того, отсортирован ли вектор или нет. Моя первоначальная мысль заключалась в том, что происходило какое-то предсказание ветвей (см. этот вопрос), но от обновления до этот ответ, похоже, что эти вещи не должны иметь значения.

Что происходит?

ИЗМЕНИТЬ

Зазор, по-видимому, возрастает по мере увеличения как размера вектора, так и количества дубликатов.

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

Ответ 1

Основным фактором является снижение промахов в кэше CPU, а также увеличение масштабов, более дорогостоящие ошибки страницы. Дублирование проверяется ссылкой на простую хеш-таблицу. Если запрашиваемая часть хеш-таблицы уже находится в высокоскоростном кэше памяти, эти поисковые запросы намного быстрее. Для небольших векторов соответствующая хеш-таблица будет полностью вписываться в кеш высокой скорости, поэтому порядок доступа невелик, что и было в первом эталоне.

Для более крупных векторов только некоторые блоки хэш-таблицы будут вписываться в кеш в любой момент времени. Если дубликаты последовательны, то часть хеш-таблицы, необходимая для поиска, уже будет в кеше для последующих поисков. Вот почему производительность увеличивается на количество дубликатов для больших векторов. Для чрезвычайно больших векторов хеш-таблица может даже не полностью вписаться в доступную физическую память и выгружаться на диск, что делает ее еще более заметной.

Чтобы проверить это, позвольте использовать исходный post s2 vector и его отсортированную версию, но также проверить, просто ли дубликаты рядом друг с другом, но в противном случае unsorted.

# 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, но здесь мы имеем дело с значениями двойного размера, а не с возможностью использования unsigned longs, поэтому мы не сможем использовать побитовые операции.

# 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 и 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