查找元素索引的快速方法

Question

我有一個單一的段[0,1]和幾個點，它表示爲一個向量v。此外，我有一個0到1之間的數字k，我想知道該數字落入的區間的指數是什麼。 我想知道是否存在一種智能方式，而不是在元素上循環。

k <- 0.67 
v <- c(0.12 , 0.25 , 0.48 , 0.78 , 1) 

Answer 1

的一種方式是執行以下操作：

的間隔爲n - 1向量v（n）的長度。因此，考慮到這一點，你可以使用Position返回的function(x) 0.67 < x第一次出現的位置：

#sort helps in case v is not sorted 
Position(function(x) 0.67 < sort(x), v) - 1 
[1] 3 

上述發生的位置是4，間隔是第三。

Answer 2

像這樣的東西可能：c(max(which(v<k)),min(which(v>k)))

Answer 3

我一直在努力很類似，不同之處在於將輪向量中的最接近的值，而不是返回指數。我一直在用Rcpp編寫一個C++腳本。下面我以上述三個解決方案爲基準，以及我編寫的cpp腳本，它返回值而不是索引，但很容易修改。 findInterval似乎是迄今爲止最快的，如果您不計算cpp代碼：

library(Rcpp) 
cppFunction('NumericVector nearest_neighbor(NumericVector x, NumericVector v) { 
    int n, m, i, j, k, adj; 
      n = v.size(); 
      m = x.size(); 

      NumericVector y(m); 
      for (int a=0;a<m;a++) { 
      if (x[a] < v[0]) { 
      return v[0]; 
      } else if (x[a] >= v[n-1]) { 
      return v[n-1]; 
      } 
      i = 0; 
      j = 0; 
      k = n-1; 
      while(!(v[j] <= x[a] && x[a] < v[j+1])) { 
      if (x[a] < v[j]) { 
      k = j; 
      } else { 
      i = j+1; 
      } 
      j = div((k-i), 2).quot + i; 
      } 
      if (pow(x[a] - v[j+1],2) < pow(x[a] - v[j],2)) { 
      adj = 1; 
      } else { 
      adj = 0; 
      } 
      y[a] = v[j + adj]; 
      } 
      return y; 
      }') 


library(microbenchmark) 
v <- 1:10000 
k <- 6.5 
microbenchmark(c(max(which(v<k)),min(which(v>k)))) 
#> Unit: microseconds 
#>          expr  min  lq  mean 
#> c(max(which(v < k)), min(which(v > k))) 200.907 202.6625 290.4425 
#> median  uq  max neval 
#> 203.8475 234.6495 1789.479 100 
microbenchmark(Position(function(x) k < sort(x), v) - 1) 
#> Unit: microseconds 
#>          expr  min  lq  mean 
#> Position(function(x) k < sort(x), v) - 1 262.773 282.9995 296.9819 
#> median  uq  max neval 
#> 298.919 305.849 428.715 100 
microbenchmark(findInterval(k, v)) 
#> Unit: microseconds 
#>    expr min  lq  mean median uq  max neval 
#> findInterval(k, v) 33.199 33.7105 50.62627 34.264 37.04 1483.216 100 
microbenchmark(nearest_neighbor(k, v)) 
#> Unit: microseconds 
#>     expr min  lq  mean median  uq  max 
#> nearest_neighbor(k, v) 12.567 13.166 29.45889 13.4945 13.787 1574.045 
#> neval 
#> 100