R: Получение индексы элементов в отсортированном векторе

У меня есть отсортированный вектор, скажемR: Получение индексы элементов в отсортированном векторе

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

Теперь я хочу, чтобы найти индекс i первого элемента, который больше, чем, например a <- 15.

Я мог бы сделать что-то вроде i <- which(v > a)[1].

Но я хочу использовать тот факт, что v отсортирован, что я не думаю which заботится о.

Я мог бы написать его сам и разделить интервал рекурсивно пополам и поиск в этих частичных интервалах ...

Есть ли встроенные решения? Как обычно, основной проблемой является скорость, и моя собственная функция будет медленнее.

спасибо.

источник

2015-05-04 Mika Prouk

Ваше решение занимает менее 90 микросекунд на моей машине для вектора 1E4 элементов. Вы уверены, что это недостаточно быстро? – Roland

Хм. Ты прав. 'который (runif (10e6,0,100)> 99,99) [1]' тоже практически не занимает времени. В моем случае у меня есть большой вектор данных. На моей машине требуется 0,015 с миллионным временем. Любопытно, что это не имеет значения, если они отсортированы или нет. 'который' действительно очень хорош. –

Если вы хотите улучшить, вы можете реализовать предлагаемый алгоритм с помощью 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: Получение индексы элементов в отсортированном векторе

ответ

Смежные вопросы