performance - vectores - suma de elementos de un vector matlab

Función rápida para agregar elementos vectoriales por sus nombres

Question

Escribí esta función R que, dada cualquier cantidad de vectores ( ... ) los combina al sumar los valores de los elementos respectivos en función de sus nombres.

add_vectors <- function(...) {
  a <- list(...)
  nms <- sort(unique(unlist(lapply(a, names))))
  out <- numeric(length(nms))
  names(out) <- nms
  for (v in a) out[names(v)] <- out[names(v)] + v

  out
}

Ejemplo:

v1 <- c(a=2,b=3,e=4)
v2 <- c(b=1,c=6,d=0,a=4)
add_vectors(v1, v2)
#
a b c d e 
6 4 6 0 4

Intento escribir una función equivalente que sea mucho más rápida .

Lamentablemente, en este momento no tengo idea de cómo lograr esto en R así que pensé en Rcpp . Pero, para convertir en Rcpp esta función, echo de menos algunos conceptos:

1. Cómo administrar el ... parámetro. Con un parámetro de tipo de List en Rcpp ?
2. Cómo iterar los vectores en el parámetro ...
3. Cómo acceder (y luego sumar) los elementos de los vectores por su nombre (esto es muy trivial en R , pero no puedo entender cómo hacerlo en Rcpp ).

Así que estoy buscando a alguien que pueda ayudarme a mejorar el rendimiento de esta función (en R o Rcpp , o en ambas).

Cualquier ayuda es apreciada, gracias.

Answer 1

Acabo de escribir una versión binaria (2 entradas) de esta función en Rcpp .

No sé cómo usar el ... parámetro (y cómo iterar en él) en Rcpp así que he encapsulado esta función en una simple función R

SOLUCIÓN

library(Rcpp)
cppFunction(
  code = ''
  NumericVector add_vectors_cpp(NumericVector v1, NumericVector v2) {
    // merging names, sorting them and removing duplicates
    std::vector<std::string> nms1 = v1.names();
    std::vector<std::string> nms2 = v2.names();
    std::vector<std::string> nms;
    nms.resize(nms1.size() + nms2.size());
    std::merge(nms1.begin(), nms1.end(), nms2.begin(), nms2.end(), nms.begin());
    std::sort(nms.begin(), nms.end());
    nms.erase(std::unique(nms.begin(), nms.end()), nms.end());
    // summing vector elements by their names and storing them in an associative data structure
    int num_names = nms.size();
    std::tr1::unordered_map<std::string, double> map(num_names);
    for (std::vector<int>::size_type i1 = 0; i1 != nms1.size(); i1++) {
        map[nms1[i1]] += v1[i1];
    }
    for (std::vector<int>::size_type i2 = 0; i2 != nms2.size(); i2++) {
        map[nms2[i2]] += v2[i2];
    }
    // extracting map values (to use as result vector) and keys (to use as result vector names)
    NumericVector vals(map.size());
    for (unsigned r = 0; r < num_names; ++r) {
        vals[r] = map[nms[r]];
    }
    vals.names() = nms;
    return vals;
  }'',
  includes = ''
  #include <vector>
  #include <tr1/unordered_map>
  #include <algorithm>''
)

Luego, la encapsulación en una función R :

add_vectors_2 <- function(...) {
  Reduce(function(x, y) add_vectors_cpp(x, y), list(...))
}

Tenga en cuenta que esta solución utiliza las bibliotecas STL . No sé si esta es una solución de C ++ bien escrita o si se puede escribir una solución más eficiente (probablemente), pero con seguridad es un buen punto de partida (y de trabajo).

EJEMPLOS DE USO

v1 <- c(b = 1, d = 2, c = 3, a = 4, e = 6, f = 5)
v2 <- c(d = 2, c = 3, a = 4, e = 6, f = 5)
add_vectors(v1, v2, v1, v2)
#  a  b  c  d  e  f 
# 16  2 12  8 24 20
add_vectors_2(v1, v2, v1, v2)
#  a  b  c  d  e  f 
# 16  2 12  8 24 20 

NOTA: esta función también funciona para vector cuyos nombres no son únicos.

v1 <- c(b = 1, d = 2, c = 3, a = 4, e = 6, f = 5)
v2 <- c(d = 2, c = 3, a = 4, e = 6, f = 5, f = 10, a = 12)
add_vectors(v1, v2)
#  a  b  c  d  e  f 
# 16  1  6  4 12 15 
add_vectors_2(v1, v2)
#  a  b  c  d  e  f 
# 20  1  6  4 12 20

Como se muestra en el último ejemplo, esta solución funciona incluso cuando los vectores de entrada tienen nombres no únicos, sumando los elementos del mismo vector con el mismo nombre .

BENCHMARKS

Mi solución es aproximadamente 3 veces más rápida que la solución R en el caso más simple (dos vectores). Es una buena implementación, pero probablemente haya margen para pequeñas mejoras adicionales con una mejor solución de C++ .

Unit: microseconds
                 expr    min     lq median      uq     max neval
  add_vectors(v1, v2) 65.460 68.569 70.913 73.5205 614.274   100
add_vectors_2(v1, v2) 20.743 23.389 25.142 26.9920 337.544   100

Al aplicar esta función a más vectores, las actuaciones se degradan un poco (solo 2 veces más rápido).

Unit: microseconds
                                 expr     min       lq  median       uq     max neval
  add_vectors(v1, v2, v1, v2, v1, v1) 105.994 195.7565 205.174 212.5745 993.756   100
add_vectors_2(v1, v2, v1, v2, v1, v1)  66.168 125.2110 135.060 139.7725 666.975   100

Entonces, el último objetivo ahora es eliminar la función de envoltura R administrando el parámetro ... (o similar, por ejemplo, List ) directamente con Rcpp .

Creo que esto es posible porque el azúcar Rcpp tiene características similares a él (por ejemplo, el uso de la función sapply ), pero agradecería algunos comentarios.

Answer 2

El paquete data.table es excelente para realizar agregación y otras operaciones. No soy realmente un experto, pero

library(data.table)
add_vectors5 <- function(...)
{
    vals <- do.call(c, list(...))
    dt <- data.table(nm=names(vals), v=vals, key="nm")
    dt <- dt[,sum(v), by=nm]
    setNames(dt[[2]], dt[[1]])
}

parece ser aproximadamente 2 veces más rápido que otras implementaciones de R puro. Una implementación más críptica es

add_vectors6 <- function(..., method="radix")
{
    vals <- do.call(c, list(...))
    ## order by name, but use integers for faster order algo
    idx <- match(names(vals), unique(names(vals)))
    o <- sort.list(idx, method=method, na.last=NA)

    ## cummulative sum of ordered values
    csum <- cumsum(vals[o])

    ## subset where ordering factor changes, and then diff
    idxo <- idx[o]
    diff(c(0, csum[idxo != c(idxo[-1], TRUE)]))
}

que es propenso al desbordamiento numérico; use method = "radix" si hay menos de 100,000 nombres, como está implícito en ?sort.list , de lo contrario method = "quick".

Answer 3

La compilación de código de bytes con el paquete de compilación le proporciona algunas mejoras. Este paquete se envía con R.

library(compiler)
library(microbenchmark)

add_vectors_cmp <- cmpfun(add_vectors)

set.seed(1)
v <- rpois(length(letters), 10)
names(v) <- letters
vs <- replicate(150, v, simplify=FALSE)

not_compiled <- function(l) do.call(add_vectors, l)
compiled <- function(l) do.call(add_vectors_cmp, l)

plot(microbenchmark(not_compiled(vs), compiled(vs)))

Answer 4

No creo que obtengas mucha aceleración. Tomé un enfoque alternativo en el código R, combinando todas las entradas en un solo vector, luego resplicándome por nombre y agregando vapply . Más o menos todas las funciones allí llamadas código C interno, y la velocidad es comparable a su función para vectores grandes (probado en vectores de longitud 1e5 y 1e6). Es un poco más lento para los ejemplos de juguetes de 3 o 4 elementos.

add_vectors2 <- function(...) {
  y <- do.call(c, unname(list(...)))
  vapply(split(y, names(y)), sum, numeric(1))
}

#Longer sample vectors
m <- 1e3
n <- 1e6
v1 <- sample(m, n, replace = TRUE)
names(v1) <- sample(n)
v2 <- sample(m, n, replace = TRUE)
names(v2) <- sample(seq_len(n) + n / 2)  

#Timings
k <- 20
system.time(for(i in 1:k) add_vectors(v1, v2))   #5 or 6 seconds
system.time(for(i in 1:k) add_vectors2(v1, v2))  #same

EDITAR: los nombres de vectores se han fijado para que sean únicos, lo que refleja el comentario de Roland. Mi solución ahora es un poco más lenta que la de OP.

Answer 5

Yo usaría algo como esto:

#include <Rcpp.h>
using namespace Rcpp; 

// [[Rcpp::export]]
NumericVector add_all(List vectors){
    RCPP_UNORDERED_MAP<std::string,double> out ; 
    int n = vectors.size() ;
    for( int i=0; i<n; i++){
        NumericVector x = vectors[i] ;
        CharacterVector names = x.attr("names") ;
        int m = x.size() ;

        for( int j=0; j<m; j++){
            String name = names[j] ;
            out[ name ] += x[j] ;   
        }
    }
    return wrap(out) ;
}

con la siguiente envoltura:

add_vectors_cpp <- function(...){
    add_all( list(...) )
}

RCPP_UNORDERED_MAP es solo un typedef a unordered_map , ya sea en std:: o en std::tr1:: dependiendo de tu compilador, etc ...

El truco aquí es crear una lista regular de ... usando la list(...) clásica list(...) .

Si realmente quisiera pasar directamente ... en C ++ y tratarlo internamente, tendría que usar la interfaz .External . Esto se usa muy poco, por lo que los atributos Rcpp no ​​son compatibles con la interfaz .External .

Con .External , se vería así (no probado):

SEXP add_vectors(SEXP args){
    RCPP_UNORDERED_MAP<std::string,double> out ; 
    args = CDR(args) ;
    while( args != R_NilValue ){
        NumericVector x = CAR(args) ;

        CharacterVector names = x.attr("names") ;
        int m = x.size() ;

        for( int j=0; j<m; j++){
            String name = names[j] ;
            out[ name ] += x[j] ;   
        }        
        args = CDR(args) ;
    }   
    return wrap(out) ;
}