「論理型」型のサブセット化が「数値型」型のサブセット化より遅いのはなぜですか？

Question

次のように我々は（そのことについてまたはdata.frame）vectorをしましたとします

set.seed(1) 
x <- sample(10, 1e6, TRUE) 

を、もう1つは 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は、サブセット化の際に/その間に大幅に追い付いているようです。

which通話.Internal(which(x))==に対し、通話.Primitive("==")として選択debugonce（thanks to @GavinSimpson）の私のいつもの武器を使用することはできないようです。

[がnumericの場合は、>の論理ベクトルよりもwhichの方が速いのはなぜですか？何か案は？

Answer 1

これは、論理ベクトルによるサブセット化が数値インデックスによるサブセット化よりも遅いためです。更新

> 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 

Answer 2

これは私の取り組みです。数値をサブセット化すると、必要な要素を正確に引き出すことができます。論理にサブセットを設定するには、インデックスベクトルの各要素を調べて、それがTRUEであるかどうかを確認し、ターゲットベクトルの必要な要素の内部リストを構築する必要があります。 2つのステップがありますので、時間がかかります。

抽出される要素の数が元のベクトルのサイズに比べて小さいことが最も大きな違いです。たとえば：あなたは要素のごく一部を引き出している場合

> 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 

ここで、whichは論理インデックスに比べて非常に小さい割合を取る使用して、（私のテストにおけるz < -5の23個の要素がありました） 。しかし、要素の大部分を抽出している場合は、時間が近くなります。

Answer 3

私はコメントから外して答えを加えるべきだと思います。これは、他の人が答えて議論してきたものを築き上げる私の感覚です。私はベクトルxと論理ベクトルx > 0を持っていたら（私は本当の答えはsubset_dfltのCソースに存在することを確認しています。）

、私は2つの方法でx > 0にxをサブセットすることができます。 whichを使用することができます。または、ベクトルx > 0をインデックスとして直接使用することができます。しかし、x[x > 0]はNAを保持し、x[which(x > 0)]は保持しないので、2つは同一ではないことに注意する必要があります。

しかしどちらの方法でも、ベクトル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です。そして時間は「サブセット」で取られ、〜700 usです。どちらの数値も匹敵し、ある方法や別の方法ではコストがかかる「部分集合」ではないことを示しています。代わりに、それはwhichメソッドで安価なサブセットを計算するために行われていることです。