R：獲取元素的索引以排序向量

我有一個排序的載體，讓我們說R：獲取元素的索引以排序向量

v <- c(1, 1, 2, 3, 5, 8, 13, 21, 34)

現在我想找到比例如a <- 15更大的第一個元素的索引i。

我可以做些類似i <- which(v > a)[1]的東西。

但我想利用v排序的事實，我不認爲which關心。

我可以寫我自己，在半遞歸地劃分區間，並在這些局部區間搜索...

是否有任何內置的解決方案？像往常一樣，主要問題是速度，我自己的功能肯定會變慢。

謝謝。

來源

2015-05-04 Mika Prouk

你的溶液需要不到90微秒我的機器上爲1E4個元素的向量。你確定這個速度不夠快嗎？ – Roland

嗯。你是對的。 '（runif（10e6,0,100）> 99.99）[1]'幾乎沒有時間。在我的情況下，我有一個很大的日期時間向量。在我的機器上，它需要0.015s和一百萬個日期時間。奇怪的是，如果排序或不排序則沒有區別。 '這確實很不錯。 –

如果你想改進，你可以用Rcpp實現你的建議算法。 – Roland

對於速度貪食

a <- 10 
v <- sort(runif(1e7,0,1000)); 
Rcpp::cppFunction('int min_index(NumericVector v, double a) { 
        NumericVector::iterator low=std::lower_bound (v.begin(), v.end(), a); 
        return (low - v.begin()); 
        }') 
microbenchmark::microbenchmark(which(v > a)[1], min_index(v, a), unit="relative") 

#Unit: relative 
#   expr  min  lq  mean median  uq  max neval 
#which(v > a)[1] 61299.15 67211.58 14346.42 8797.526 8683.39 11163.27 100 
#min_index(v, a)  1.00  1.00  1.00 1.000 1.00  1.00 100

來源

2015-05-04 12:17:48 Khashaa

只是想知道以下可能是有用的。

Filter(function(x) x > 15, v)[1] 
#[1] 21 
Find(function(x) x > 15, v, right = FALSE, nomatch = NULL) 
#[1] 21 
Position(function(x) x > 15, v, right = FALSE, nomatch = NA_integer_) 
#[1] 8

來源

2015-05-04 09:38:36

這比OP的解決方案慢。 – Roland

which不完全是緩慢的，所以怎麼樣min(which())：

v <- c(1,1,2,3,5,8,13,21,34) 
system.time(
    print(min(which(v > 5))) 
) 
# [1] 6 
# user system elapsed 
    0  0  0

來源

2015-05-04 09:40:27 Phil

這比OP的解決方案慢。 – Roland

感謝您的基準測試，瞭解它非常有用。我並不是建議我的解決方案更快或更慢，只是「which（）」不是很慢，所以對於OP來說絕對不夠快（因爲你問過）？ – Phil

有uniroot。它使用二分法，在更長的矢量上更快。

v <- c(1,1,2,3,5,8,13,21,34) 
a <- 15 

root <- uniroot(f = function(x) v[x] - a, interval = c(1, length(v))) 
my_index <- floor(root$root)

來源

2015-05-04 09:50:52 bergant

不錯的主意，但在以'set.seed（42）爲基準進行基準測試時也不會有任何改進。 v < - sort（sample（1：100，1e4，TRUE））'。 – Roland

@Roland同意。但更長的載體速度更快。（> 20000） – bergant

R：獲取元素的索引以排序向量

回答

相關問題