Почему подмножество на "логическом" типе медленнее, чем подмножество на "числовом" типе?
Предположим, что у нас есть vector (или data.frame):
set.seed(1)
x <- sample(10, 1e6, TRUE)
И каждый хочет получить все значения x, где x > 4, скажем:
a1 <- x[x > 4] # (or)
a2 <- x[which(x > 4)]
identical(a1, a2) # TRUE
Я думаю, что большинство людей предпочитают x[x > 4]. Но удивительно (по крайней мере для меня), подмножество с использованием which выполняется быстрее!
require(microbenchmark)
microbenchmark(x[x > 4], x[which(x > 4)], times = 100)
Unit: milliseconds
expr min lq median uq max neval
x[x > 4] 56.59467 57.70877 58.54111 59.94623 104.51472 100
x[which(x > 4)] 26.62217 27.64490 28.31413 29.97908 99.68973 100
Это примерно в 2,1 раза быстрее на моем.
Одна из возможностей разницы, я думал, может быть связана с тем, что which не рассматривает NA, но > возвращает их также. Но тогда логическая операция сама по себе должна быть причиной этой разницы, что не так (очевидно). То есть:
microbenchmark(x > 4, which(x > 4), times = 100)
Unit: milliseconds
expr min lq median uq max neval
x > 4 8.182576 10.06163 12.68847 14.64203 60.83536 100
which(x > 4) 18.579746 19.94923 21.43004 23.75860 64.20152 100
Использование which примерно в 1.7 раза медленнее перед подмножеством. Но which, похоже, сильно подтягивается во время подмножества.
Кажется невозможным использовать мое обычное оружие выбора debugonce (благодаря @GavinSimpson) в качестве which вызывает .Internal(which(x)), тогда как == вызывает .Primitive("==").
Поэтому мой вопрос: почему [ на numeric тип, полученный из which быстрее, чем логический вектор, полученный из >? Любые идеи?
Ответы
Ответ 1
Думаю, я должен отойти от комментариев и добавить ответ. Это моя навязчивая мысль о том, что другие ответили и обсудили. (Я уверен, что реальный ответ существует в источнике C для subset_dflt.)
Как только у меня есть вектор x и логический вектор x > 0, я могу подмножить x на x > 0 двумя способами. Я могу использовать which, или я могу использовать вектор x > 0 непосредственно в качестве индексации. Однако мы должны отметить, что они не идентичны, так как x[x > 0] сохранит NA, а x[which(x > 0)] не будет.
Однако в любом методе мне нужно будет изучить каждый элемент вектора x > 0. В явном вызове which мне придется исследовать только логическое состояние элемента, а в операции прямого подчинения мне нужно будет изучить как пропущенность, так и логическое состояние каждого элемента.
@flodel дает интересное наблюдение. Поскольку [, is.na, which и | - все примитивы или внутренние процедуры, не допускайте чрезмерных накладных расходов и выполняйте этот эксперимент:
microbenchmark(which(x > 0), x[which(x > 0)], x > 0 | is.na(x), x[x > 0],
unit="us", times=1000)
Unit: microseconds
expr min lq median uq max neval
which(x > 0) 1219.274 1238.693 1261.439 1900.871 23085.57 1000
x[which(x > 0)] 1554.857 1592.543 1974.370 2339.238 23816.99 1000
x > 0 | is.na(x) 3439.191 3459.296 3770.260 4194.474 25234.70 1000
x[x > 0] 3838.455 3876.816 4267.261 4621.544 25734.53 1000
Учитывая медианные значения, мы можем видеть, что, предполагая, что x > 0 | is.na(x) является грубой моделью того, что я говорю, происходит в логической подстановке, тогда фактическое время, затрачиваемое на "подмножество" , составляет ~ 500 us. И время, затраченное на "подмножество" , с которым составляет ~ 700 у.е. Оба эти числа сопоставимы и указывают, что это не "подмножество" , которое дорого стоит тем или иным способом. Вместо этого выполняется то, что делается для вычисления требуемого подмножества, которое дешевле в методе which.
Ответ 2
Это похоже на то, что подмножество по логическому вектору медленнее, чем подмножество по числовому индексу.
> ii <- x > 4
> ij <- which(x > 4)
>
> head(ii)
[1] FALSE FALSE TRUE TRUE FALSE TRUE
> head(ij)
[1] 3 4 6 7 8 9
>
> microbenchmark(x[ii], x[ij], times = 100)
Unit: milliseconds
expr min lq median uq max neval
x[ii] 25.574977 26.15414 28.299858 31.080903 82.04686 100
x[ij] 3.037134 3.31821 3.670096 7.516761 12.39738 100
Обновлено:
Вероятно, одна из причин заключается в том, что меньшая длина индексного числа может уменьшить (внутренний) цикл для подмножества и приведет к более медленной оценке. Вы можете найти ik < ij < il
Но было бы другое различие, потому что между ii и il существует огромная разница.
> ii <- x > 4
>
> ij <- which(x > 4)
> ik <- which(x > 9)
> il <- which(x > -1)
>
> microbenchmark(x[ii], x[ij], x[ik], x[il], times = 100)
Unit: microseconds
expr min lq median uq max neval
x[ii] 25645.621 25986.2720 28466.412 30693.158 79582.484 100
x[ij] 3111.974 3281.8280 3477.627 6142.216 55076.121 100
x[ik] 585.723 628.2125 650.184 682.888 7551.084 100
x[il] 5266.032 5773.9015 9073.614 10583.312 15113.791 100
Ответ 3
Здесь я беру на себя это. Подмножество на числовое значение позволяет вытаскивать именно те элементы, которые требуются. Подмножество по логике требует проверки каждого элемента вектора индекса, чтобы увидеть, если он TRUE, а затем построение внутреннего списка необходимых элементов целевого вектора. Есть два шага, поэтому потребуется больше времени.
Наибольшая разница состоит в том, что количество извлеченных элементов невелико относительно размера исходного вектора. Например:
> z <- rnorm(1e8)
> system.time(z[which(z < -5)])
user system elapsed
0.58 0.03 0.60
> system.time(z[z < -5])
user system elapsed
2.56 0.14 2.70
> system.time(z[which(z < 5)])
user system elapsed
1.39 0.30 1.68
> system.time(z[z < 5])
user system elapsed
2.82 0.44 3.26
Здесь, если вы вытаскиваете только небольшую часть элементов (в моем тесте было 23 элемента z < -5), использование which занимает очень небольшую долю по сравнению с логической индексацией. Однако, если вы извлекаете большую часть элементов, время ближе.
