2013-04-25 21 views
6

Ho un vettore di numeri positivi e negativipiù efficiente strategia per cui() o match()

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

il vettore è maggiore della esempio, e assume un insieme casuale di valori. Devo trovare ripetutamente il numero di numeri negativi nel vettore ... Sto trovando che questo è abbastanza inefficiente.

Poiché ho solo bisogno di trovare il numero di numeri negativi e il vettore è ordinato, ho solo bisogno di conoscere l'indice del primo 0 o numero positivo (non ci possono essere 0 nei vettori casuali reali).

Attualmente sto usando questo codice per trovare la lunghezza

length(which(vec<0)) 

ma questo costringe R per passare attraverso l'intero vettore, ma dal momento che è ordinato, non è necessario.

ho potuto utilizzare

match(0, vec) 

ma il mio vettore non ha sempre 0s

Quindi la mia domanda è: esiste una sorta di match() funzione che applica una condizione invece di trovare un valore specifico ? O c'è un modo più efficiente per eseguire il mio quale() codice?

Grazie

risposta

15

Le soluzioni offerte finora implicano la creazione di uno logical(length(vec)) e la scansione completa o parziale su questo. Come si nota, il vettore è ordinato. Possiamo sfruttarlo effettuando una ricerca binaria. Ho iniziato a pensare che sarei stato super-intelligente e l'avrei implementato in C per una velocità ancora maggiore, ma ho avuto problemi con il debugging dell'indicizzazione dell'algoritmo (che è la parte difficile!).Così ho scritto in 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 
} 

Per il confronto con gli altri suggerimenti

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

e per il divertimento

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

Leading to

> 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 

Probabilmente ci sono alcuni casi complicati che ho avuto wr ong! Trasferirsi in C, ho fatto

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); 
") 

con

> 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 è venuto quando una domanda simile è stato chiesto sulla lista R-help. È lento ma sicuro, controllando che lo vec sia effettivamente ordinato e si occupi dei valori di NA. Se si vuole vivere al limite (forse non peggio che l'attuazione F3 o F4) allora

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

è quasi veloce come l'implementazione C, ma probabilmente più robusto e vectorized (vale a dire, cercare un vettore di valori nel secondo argomento, per semplici calcoli di tipo intervallo).

+5

+1 wow. Imparerò molto da questo. Grazie mille per aver postato una risposta così ponderata e approfondita –

+0

Ho ricevuto un errore durante l'acquisizione della funzione f4 https://gist.github.com/anonymous/5785498 – Juancentro

+0

@Juancentro la versione C del codice richiede che tu abbia un compilatore C installato. Per Windows, [seguire queste istruzioni] (http://cran.r-project.org/bin/windows/Rtools/). –

3

Usa sum() e confronto logico:

sum(vec < 0) 
[1] 100 

Questo sarà piuttosto veloce, e quando si somma una logica, TRUE è 1 e FALSE è 0 in modo che il totale sarà il numero di valori negativi.

Uh oh, sento la necessità di un confronto di benchmarking ... :-) lunghezza Vector è 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 
+0

s/subetting/confronto/;-) –

+0

@JoshuaUlrich s ??? –

+0

Simon, fa parte della sintassi del comando 'sed' e/o unix shell. Il piombo "s" è l'abbreviazione di "sostituto". –

2

si potrebbe usare which.min

which.min(vec < 0) - 1L 

Ciò restituirà il primo valore FALSE , ovvero il primo 0.