Почему подмножество на "логическом" типе медленнее, чем подмножество на "числовом" типе?

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