relacionales - para que sirven los operadores logicos

¿Por qué algunos de los operadores lógicos son tan lentos?

Question

Al intentar optimizar mi código, encontré que algunas operaciones logical eran más lentas de lo que esperaba en comparación con operaciones similares en integer o numeric .

¡Así que fui a reescribir operadores booleanos básicos ! , & , | , xor como sigue:

my.not <- function(x) as.logical(1L - as.integer(x))
my.and <- function(e1, e2) as.logical(as.integer(e1) * as.integer(e2))
my.or  <- function(e1, e2) as.logical(as.integer(e1) + as.integer(e2))
my.xor <- function(e1, e2) as.logical(as.integer(e1) + as.integer(e2) == 1L)

Prueba de que todo funciona como se espera:

a <- sample(c(TRUE, FALSE), 1e6, TRUE)
b <- sample(c(TRUE, FALSE), 1e6, TRUE)

identical(!a, my.not(a))             # TRUE
identical(a & b, my.and(a, b))       # TRUE
identical(a | b, my.or(a, b))        # TRUE
identical(xor(a, b), my.xor(a, b))   # TRUE

Ahora benchmarking:

library(microbenchmark)
microbenchmark(!a, my.not(a),
               a & b, my.and(a, b),
               a | b, my.or(a, b),
               xor(a, b), my.xor(a, b))

# Unit: milliseconds
#          expr       min        lq    median         uq       max neval
#            !a  1.237437  1.459042  1.463259   1.492671  17.28209   100
#     my.not(a)  6.018455  6.263176  6.414515  15.291194  70.16313   100
#         a & b 32.318530 32.667525 32.769014  32.973878  50.55528   100
#  my.and(a, b)  8.010022  8.592776  8.750786  18.145590  78.38736   100
#         a | b 32.030545 32.383769 32.506937  32.820720 102.43609   100
#   my.or(a, b) 12.089538 12.434793 12.663695  22.046841  32.19095   100
#     xor(a, b) 94.892791 95.480200 96.072202 106.104000 164.19937   100
#  my.xor(a, b) 13.337110 13.708025 14.048350  24.485478  29.75883   100

Mirando los resultados, el ! El operador es el único que parece hacer un trabajo decente en comparación con el mío. Los otros tres son un poco más lentos. Un poco embarazoso para las funciones Primitive . Incluso espero que los operadores booleanos bien implementados sean mucho más rápidos que las operaciones con enteros (cómo implementé mis propias funciones).

Pregunta: ¿Por qué? ¿Mala implementación? ¿O quizás las funciones primitivas están haciendo algunas cosas buenas (por ejemplo, verificación de errores, casos especiales) que mis funciones no están haciendo?

Answer 1

Además, no olvide que en R, los lógicos se almacenan como números enteros en la memoria. Así que tiene sentido no tener una gran mejora en la velocidad.

> a=rep(TRUE,1000)
> b=rep(1L,1000)
> c=rep(1,1000)
> class(a)
[1] "logical"
> class(b)
[1] "integer"
> class(c)
[1] "numeric"
> object.size(a)
4040 bytes
> object.size(b)
4040 bytes
> object.size(c)
8040 bytes

Answer 2

Aunque me gustan mucho sus métodos y me encanta el aumento de velocidad, lamentablemente pierden su habilidad cuando e1 e2 tienen una estructura más compleja que un vector.

> dim(a) <- c(1e2, 1e4)
> dim(b) <- c(1e2, 1e4)
> 
> identical(!a, my.not(a))            
[1] FALSE
> identical(a & b, my.and(a, b))       
[1] FALSE
> identical(a | b, my.or(a, b))        
[1] FALSE
> identical(xor(a, b), my.xor(a, b))   
[1] FALSE

ESTRUCTURA / DIMENSIONALIDAD

Las funciones lógicas conservan la estructura y los atributos, lo cual es costoso, pero tiene valor.

T <- TRUE; F <- FALSE
A <- matrix(c(T, F, T, F), ncol=2)
B <- matrix(c(T, F, F, T), ncol=2)

> A & B
      [,1]  [,2]
[1,]  TRUE FALSE
[2,] FALSE FALSE

> my.and(A, B)
[1]  TRUE FALSE FALSE FALSE

Manejo de NA

Además, como se señaló en los comentarios, las NA también deben tenerse en cuenta, es decir, más gastos generales.

a <- c(T, F, NA, T)
b <- c(F, NA, T, T)
>     identical(!a, my.not(a))    
[1] TRUE
>     identical(a & b, my.and(a, b))       
[1] FALSE
>     identical(a | b, my.or(a, b))        
[1] FALSE
>     identical(xor(a, b), my.xor(a, b))   
[1] TRUE

ATRIBUTOS

a <- c(T, F, NA, T)
b <- c(F, NA, T, T)

names(a) <- names(b) <- LETTERS[23:26]

> a & b
    W     X     Y     Z 
FALSE FALSE    NA  TRUE 

> my.and(a, b)
[1] FALSE    NA    NA  TRUE

No velocidad

Por supuesto, con todo lo que se dice, ¡sus funciones ofrecen un gran aumento! Si sabes que no tienes que preocuparte por las NA y los me gusta, y no te importa la estructura, ¡entonces por qué no usarlas!

Answer 3

Mirando un poco la implementación de C, las operaciones lógicas y matemáticas implementan sus bucles de manera diferente. Las operaciones lógicas hacen algo como (en logic.c: 327)

library(inline)

or1 <- cfunction(c(x="logical", y="logical"), "
    int nx = LENGTH(x), ny = LENGTH(y), n = nx > ny ? nx : ny;
    SEXP ans = PROTECT(allocVector(LGLSXP, n));
    int x1, y1;
    for (int i = 0; i < n; i++) {
        x1 = LOGICAL(x)[i % nx];
        y1 = LOGICAL(y)[i % ny];
        if ((x1 != NA_LOGICAL && x1) || (y1 != NA_LOGICAL && y1))
            LOGICAL(ans)[i] = 1;
        else if (x1 == 0 && y1 == 0)
            LOGICAL(ans)[i] = 0;
        else
            LOGICAL(ans)[i] = NA_LOGICAL;
    }
    UNPROTECT(1);
    return ans;
")

Donde hay dos operadores de módulo % cada iteración. En contraste, las operaciones aritméticas (en Itermacros.h: 54) hacen algo como

or2 <- cfunction(c(x="logical", y="logical"), "
    int nx = LENGTH(x), ny = LENGTH(y), n = nx > ny ? nx : ny;
    SEXP ans = PROTECT(allocVector(LGLSXP, n));
    int x1, y1, ix=0, iy=0;
    for (int i = 0; i < n; i++) {
        x1 = LOGICAL(x)[ix];
        y1 = LOGICAL(x)[iy];
        if (x1 == 0 || y1 == 0)
            LOGICAL(ans)[i] = 0;
        else if (x1 == NA_LOGICAL || y1 == NA_LOGICAL)
            LOGICAL(ans)[i] = NA_LOGICAL;
        else
            LOGICAL(ans)[i] = 1;

        if (++ix == nx) ix = 0;
        if (++iy == ny) iy = 0;
    }
    UNPROTECT(1);
    return ans;
")

Realizando dos pruebas de identidad. Aquí hay una versión que se salta la prueba para NA

or3 <- cfunction(c(x="logical", y="logical"), "
    int nx = LENGTH(x), ny = LENGTH(y), n = nx > ny ? nx : ny;
    SEXP ans = PROTECT(allocVector(LGLSXP, n));
    int x1, y1, ix=0, iy=0;
    for (int i = 0; i < n; ++i) {
        x1 = LOGICAL(x)[ix];
        y1 = LOGICAL(y)[iy];
        LOGICAL(ans)[i] = (x1 || y1);
        if (++ix == nx) ix = 0;
        if (++iy == ny) iy = 0;
    }
    UNPROTECT(1);
    return ans;
")

Y luego una versión que evita la macro LOGICAL.

or4 <- cfunction(c(x="logical", y="logical"), "
    int nx = LENGTH(x), ny = LENGTH(y), n = nx > ny ? nx : ny;
    SEXP ans = PROTECT(allocVector(LGLSXP, n));
    int *xp = LOGICAL(x), *yp = LOGICAL(y), *ansp = LOGICAL(ans);
    for (int i = 0, ix = 0, iy = 0; i < n; ++i)
    {
        *ansp++ = xp[ix] || yp[iy];
        ix = (++ix == nx) ? 0 : ix;
        iy = (++iy == ny) ? 0 : iy;
    }
    UNPROTECT(1);
    return ans;
")

Aquí hay algunos tiempos

microbenchmark(my.or(a, b), a|b, or1(a, b), or2(a, b), or3(a, b), or4(a, b))
Unit: milliseconds
        expr       min        lq    median       uq      max neval
 my.or(a, b)  8.002435  8.100143 10.082254 11.56076 12.05393   100
       a | b 23.194829 23.404483 23.860382 24.30020 24.96712   100
   or1(a, b) 17.323696 17.659705 18.069139 18.42815 19.57483   100
   or2(a, b) 13.040063 13.197042 13.692152 14.09390 14.59378   100
   or3(a, b)  9.982705 10.037387 10.578464 10.96945 11.48969   100
   or4(a, b)  5.544096  5.592754  6.106694  6.30091  6.94995   100

La diferencia entre a|b y or1 refleja cosas no implementadas aquí, como atributos y dimensiones y manejo especial de objetos. De or1 a or2 refleja el costo de las diferentes formas de reciclaje; Me sorprendió que hubiera diferencias aquí. De or2 a or3 es el costo de NA-safety. Es un poco difícil saber si la aceleración adicional en or4 se vería en una implementación base R: en el código C del usuario C LOGICAL() es una macro, pero en la base R es una llamada de función integrada.

El código fue compilado con banderas -O2 y

> system("clang++ --version")
Ubuntu clang version 3.0-6ubuntu3 (tags/RELEASE_30/final) (based on LLVM 3.0)
Target: x86_64-pc-linux-gnu
Thread model: posix

Los tiempos de my.or no fueron particularmente consistentes entre las sesiones de R independientes, a veces tomando un poco más de tiempo; No estoy seguro de por qué. Los tiempos anteriores fueron con la versión R 2.15.3 Patched (2013-03-13 r62579); El actual R-devel parecía un 10% más rápido.