¿Por qué ejecutar "único" es más rápido en un marco de datos que una matriz en R?

Question

He comenzado a creer que los marcos de datos no tienen ventajas sobre las matrices, excepto por la comodidad de notación. Sin embargo, noté esta rareza al correr unique En matrices y marcos de datos: parece funcionar más rápido en un marco de datos.

a   = matrix(sample(2,10^6,replace = TRUE), ncol = 10)
b   = as.data.frame(a)

system.time({
    u1 = unique(a)
})
 user  system elapsed
1.840   0.000   1.846


system.time({
    u2 = unique(b)
})
 user  system elapsed
0.380   0.000   0.379

Los resultados de la sincronización divergen aún más sustancialmente a medida que aumenta el número de filas. Entonces, hay dos partes en esta pregunta.

1. ¿Por qué es esto más lento para una matriz? Parece más rápido convertirse a un marco de datos, ejecutar unique, y luego volver a convertir.

2. ¿Hay alguna razón para no solo envolver? unique en myUnique, ¿Cuál es las conversiones en la parte #1?

---

Nota 1. Dado que una matriz es atómica, parece que unique Debe ser más rápido para una matriz, en lugar de más lento. Ser capaz de iterar sobre los bloques de memoria contiguos de tamaño fijo, generalmente deberían ser más rápidos que ejecutar en bloques separados de listas vinculadas (supongo que así es como se implementan los marcos de datos ...).

Nota 2. como lo demuestra el rendimiento de data.table, correr unique En un marco de datos o una matriz es una idea relativamente mala: vea la respuesta de Matthew Dowle y los comentarios para los horarios relativos. He migrado muchos objetos a tablas de datos, y este rendimiento es otra razón para hacerlo. Entonces, aunque los usuarios deberían estar bien servidos para adoptar tablas de datos, por razones pedagógicas / de la comunidad, dejaré la pregunta abierta por ahora con respecto al por qué ¿Esto tarda más en los objetos de matriz? La dirección de las respuestas a continuación dónde ¿pasa el tiempo y de que otra forma ¿Podemos obtener un mejor rendimiento (es decir, tablas de datos)? La respuesta a por qué está cerca: el código se puede encontrar a través de unique.data.frame y unique.matrix. :) Una explicación en inglés de lo que está haciendo y por qué faltan todo lo que falta.

Answer 1

1. En esta implementación, unique.matrix es lo mismo que unique.array

   > identical(unique.array, unique.matrix)

   [1] TRUE

2. unique.array tiene que manejar matrices multidimensionales que requieren procesamiento adicional para 'colapsar' las dimensiones adicionales (esas llamadas adicionales a paste()) que no son necesarios en el caso bidimensional. La sección clave del código es:

   collapse <- (ndim > 1L) && (prod(dx[-MARGIN]) > 1L)

   temp <- if (collapse) apply(x, MARGIN, function(x) paste(x, collapse = "\r"))

3. unique.data.frame está optimizado para el caso 2D, unique.matrix no es. Podría ser, como sugiere, simplemente no está en la implementación actual.

Tenga en cuenta que en todos los casos (únicos. {Array, Matrix, Data.Table}) donde hay más de una dimensión es la representación de cadena la que se compara con la singularidad. Para números de puntos flotantes, esto significa 15 dígitos decimales, así que

NROW(unique(a <- matrix(rep(c(1, 1+4e-15), 2), nrow = 2)))

es 1 tiempo

NROW(unique(a <- matrix(rep(c(1, 1+5e-15), 2), nrow = 2)))

y

NROW(unique(a <- matrix(rep(c(1, 1+4e-15), 1), nrow = 2)))

son ambos 2. Eres Por supuesto unique ¿Es lo que quieres?

Answer 2

1. No estoy seguro, pero supongo que porque matrix es un vector contiguo, r lo copia en vectores de columna primero (como un data.frame) porque paste Necesita una lista de vectores. Tenga en cuenta que ambos son lentos porque ambos usan paste.

2. Quizás porque unique.data.table ya es muchas veces más rápido. Actualice a V1.6.7 descargándolo desde el repositorio R-Forge porque eso tiene la solución a unique Te criaste en esta pregunta. data.table no se usa paste que hacer unique.

a = matrix(sample(2,10^6,replace = TRUE), ncol = 10)
b = as.data.frame(a)
system.time(u1<-unique(a))
   user  system elapsed 
   2.98    0.00    2.99 
system.time(u2<-unique(b))
   user  system elapsed 
   0.99    0.00    0.99 
c = as.data.table(b)
system.time(u3<-unique(c))
   user  system elapsed 
   0.03    0.02    0.05  # 60 times faster than u1, 20 times faster than u2
identical(as.data.table(u2),u3)
[1] TRUE

Answer 3

Al intentar responder a mi propia pregunta, especialmente la Parte 1, podemos ver dónde pasa el tiempo al observar los resultados de Rprof. Corrí esto de nuevo, con 5 m elementos.

Aquí están los resultados para la primera operación única (para la matriz):

> summaryRprof("u1.txt")
$by.self
                     self.time self.pct total.time total.pct
"paste"                   5.70    52.58       5.96     54.98
"apply"                   2.70    24.91      10.68     98.52
"FUN"                     0.86     7.93       6.82     62.92
"lapply"                  0.82     7.56       1.00      9.23
"list"                    0.30     2.77       0.30      2.77
"!"                       0.14     1.29       0.14      1.29
"c"                       0.10     0.92       0.10      0.92
"unlist"                  0.08     0.74       1.08      9.96
"aperm.default"           0.06     0.55       0.06      0.55
"is.null"                 0.06     0.55       0.06      0.55
"duplicated.default"      0.02     0.18       0.02      0.18

$by.total
                     total.time total.pct self.time self.pct
"unique"                  10.84    100.00      0.00     0.00
"unique.matrix"           10.84    100.00      0.00     0.00
"apply"                   10.68     98.52      2.70    24.91
"FUN"                      6.82     62.92      0.86     7.93
"paste"                    5.96     54.98      5.70    52.58
"unlist"                   1.08      9.96      0.08     0.74
"lapply"                   1.00      9.23      0.82     7.56
"list"                     0.30      2.77      0.30     2.77
"!"                        0.14      1.29      0.14     1.29
"do.call"                  0.14      1.29      0.00     0.00
"c"                        0.10      0.92      0.10     0.92
"aperm.default"            0.06      0.55      0.06     0.55
"is.null"                  0.06      0.55      0.06     0.55
"aperm"                    0.06      0.55      0.00     0.00
"duplicated.default"       0.02      0.18      0.02     0.18

$sample.interval
[1] 0.02

$sampling.time
[1] 10.84

Y para el marco de datos:

> summaryRprof("u2.txt")
$by.self
                     self.time self.pct total.time total.pct
"paste"                   1.72    94.51       1.72     94.51
"[.data.frame"            0.06     3.30       1.82    100.00
"duplicated.default"      0.04     2.20       0.04      2.20

$by.total
                        total.time total.pct self.time self.pct
"[.data.frame"                1.82    100.00      0.06     3.30
"["                           1.82    100.00      0.00     0.00
"unique"                      1.82    100.00      0.00     0.00
"unique.data.frame"           1.82    100.00      0.00     0.00
"duplicated"                  1.76     96.70      0.00     0.00
"duplicated.data.frame"       1.76     96.70      0.00     0.00
"paste"                       1.72     94.51      1.72    94.51
"do.call"                     1.72     94.51      0.00     0.00
"duplicated.default"          0.04      2.20      0.04     2.20

$sample.interval
[1] 0.02

$sampling.time
[1] 1.82

Lo que notamos es que la versión de matriz pasa mucho tiempo apply, paste, y lapply. Por el contrario, la versión de marco de datos se ejecuta simple duplicated.data.frame y la mayor parte del tiempo se pasa paste, presumiblemente agregando resultados.

Aunque esto explica dónde el tiempo va, no explica por qué Estos tienen implementaciones diferentes, ni los efectos de simplemente cambiar de un tipo de objeto a otro.