Более эффективная стратегия для которых() или матч()

Question

У меня есть вектор положительных и отрицательных чисел

vec<-c(seq(-100,-1), rep(0,20), seq(1,100)) 

вектор больше, чем в примере, и принимает случайного набора значений. Я должен повторно найти количество отрицательных чисел в векторе ... Я считаю, что это довольно неэффективно.

Поскольку мне нужно только найти число отрицательных чисел, и вектор отсортирован, мне нужно знать только индекс первого 0 или положительного числа (в фактических случайных векторах может отсутствовать 0s).

В настоящее время я использую этот код, чтобы найти длину

length(which(vec<0)) 

, но это заставляет R, чтобы пройти через весь вектор, но так как он сортируется, нет никакой необходимости.

я мог бы использовать

match(0, vec) 

но мой вектор не всегда 0s

Так что мой вопрос, есть ли какой-то матч() функция, которая применяет условие вместо того, чтобы найти конкретное значение ? Или есть более эффективный способ запускать мой код()?

Спасибо

Answer 1

Решения, предлагаемые до сих пор, предполагают создание logical(length(vec)) и полное или частичное сканирование на этом. Как вы заметили, вектор сортируется. Мы можем использовать это, выполнив двоичный поиск. Я начал думать, что буду супер-умным и реализовать это на C еще большую скорость, но имел проблемы с отладкой индексации алгоритма (что является сложной частью!).Так что я написал в R:

f3 <- function(x) { 
    imin <- 1L 
    imax <- length(x) 
    while (imax >= imin) { 
     imid <- as.integer(imin + (imax - imin)/2) 
     if (x[imid] >= 0) 
      imax <- imid - 1L 
     else 
      imin <- imid + 1L 
    } 
    imax 
} 

Для сравнения с другими предложениями

f0 <- function(v) length(which(v < 0)) 
f1 <- function(v) sum(v < 0) 
f2 <- function(v) which.min(v < 0) - 1L 

и для удовольствия

library(compiler) 
f3.c <- cmpfun(f3) 

приведшего к

> vec <- c(seq(-100,-1,length.out=1e6), rep(0,20), seq(1,100,length.out=1e6)) 
> identical(f0(vec), f1(vec)) 
[1] TRUE 
> identical(f0(vec), f2(vec)) 
[1] TRUE 
> identical(f0(vec), f3(vec)) 
[1] TRUE 
> identical(f0(vec), f3.c(vec)) 
[1] TRUE 
> microbenchmark(f0(vec), f1(vec), f2(vec), f3(vec), f3.c(vec)) 
Unit: microseconds 
     expr  min  lq  median   uq  max neval 
    f0(vec) 15274.275 15347.870 15406.1430 15605.8470 19890.903 100 
    f1(vec) 15513.807 15575.229 15651.2970 17064.8830 18326.293 100 
    f2(vec) 21473.814 21558.989 21679.3210 22733.1710 27435.889 100 
    f3(vec) 51.715 56.050 75.4495 78.5295 100.730 100 
f3.c(vec) 11.612 17.147 28.5570 31.3160 49.781 100 

Вероятно, есть некоторые сложные случаи, которые у меня есть Онг! Переход на C, я сделал

library(inline) 
f4 <- cfunction(c(x = "numeric"), " 
    int imin = 0, imax = Rf_length(x) - 1, imid; 
    while (imax >= imin) { 
     imid = imin + (imax - imin)/2; 
     if (REAL(x)[imid] >= 0) 
      imax = imid - 1; 
     else 
      imin = imid + 1; 
    } 
    return ScalarInteger(imax + 1); 
") 

с

> identical(f3(vec), f4(vec)) 
[1] TRUE 
> microbenchmark(f3(vec), f3.c(vec), f4(vec)) 
Unit: nanoseconds 
     expr min  lq median  uq max neval 
    f3(vec) 52096 53192.0 54918.5 55539.0 69491 100 
f3.c(vec) 10924 12233.5 12869.0 13410.0 20038 100 
    f4(vec) 553 796.0 893.5 1004.5 2908 100 

findInterval придумал, когда подобный вопрос был задан на R-help списке. Он медленный, но безопасный, проверяя, что vec фактически отсортирован и имеет дело с значениями NA. Если кто-то хочет, чтобы жить на краю (возможно, не хуже, что реализация f3 или f4), затем

f5.i <- function(v) 
    .Internal(findInterval(v, 0 - .Machine$double.neg.eps, FALSE, FALSE)) 

почти так же быстро, как реализация C, но, вероятно, более надежные и векторизация (т.е. искать вектор значений во втором аргументе, для удобных вычислений, подобных диапазону).

Answer 2

Использования sum() и логическое сравнение:

sum(vec < 0) 
[1] 100 

Это будет довольно быстро, и когда вы подвести логический, TRUE 1 и FALSE является 0, так что общим будет число отрицательных значений.

Ой, я чувствую необходимость сравнения бенчмаркинга ... :-) Вектор длина 2e5

library(microbenchmark) 
vec<-c(seq(-100,-1,length.out=1e5), rep(0,20), seq(1,100,length.out=1e5)) 
microbenchmark((which.min(vec < 0) - 1L) , (sum(vec < 0))) 

Unit: milliseconds 
         expr  min  lq median  uq  max neval 
(which.min(vec < 0) - 1L) 1.883847 2.130746 2.554725 3.141787 75.943911 100 
      (sum(vec < 0)) 1.398100 1.500639 1.508688 1.745088 2.662164 100 

Answer 3

Вы можете использовать which.min

which.min(vec < 0) - 1L 

Это вернет первое значение FALSE , т. е. первое 0.