Почему дублированные данные R работают лучше на отсортированных данных?
Сравнивая эффективность двух функций в ответе Проверить, содержит ли список другой список в 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
