¿Por qué las pandas se fusionan en python más rápido que data.table se fusiona en R en 2012?

160

Recientemente me encontré con la biblioteca de pandas para Python, que según este punto de referencia realiza fusiones en memoria muy rápidas. Es incluso más rápido que el paquete data.table en R (mi lenguaje de elección para el análisis).

¿Por qué es pandasmucho más rápido que data.table? ¿Se debe a una ventaja de velocidad inherente que tiene Python sobre R, o hay alguna compensación que no conozco? ¿Hay alguna manera de realizar uniones internas y externas data.tablesin recurrir a merge(X, Y, all=FALSE)y merge(X, Y, all=TRUE)?

Comparación

Aquí está el código R y el código Python utilizado para comparar los diversos paquetes.

Zach
fuente
10
@JoshuaUlrich: IIRC data.tablesimplemente hereda de data.frame, pero se basa en el código C bajo el capó.
digEmAll
44
@Joshua ¿Qué quieres decir con "data.frames son lentos incluso si los manipulas en C"? ¿Es eso relativo a algo más? ¿Y lento a qué?
Matt Dowle el
12
@JoshuaUlrich Me acabo de dar cuenta de que este comentario nunca se ha acostado. Para aclararlo: set()se agregó data.tablepoco después de esta discusión. Muy similar :=pero evita la pequeña sobrecarga de [.data.tablecuando se coloca en bucle y, en consecuencia, es tan rápido como matrix. Por lo tanto, data.frame se puede manipular tan rápido como la matriz. El punto de referencia está aquí .
Matt Dowle
55
¿Podemos obtener una versión actualizada de este punto de referencia? Está bastante claro que este banco era en realidad un caso extremo y que esto ya está solucionado. Dado que todos los puntos de referencia que he visto muestran que data.table es más rápido, ¿me gustaría ver cuál es el número de fusión?
statquant
3
@statquant No ejecuté el punto de referencia original, pero realmente me encantaría ver a Wes actualizar el punto de referencia.
Zach

Respuestas:

120

Parece que Wes pudo haber descubierto un problema conocido data.tablecuando la cantidad de cadenas únicas ( niveles ) es grande: 10,000.

¿ Rprof()Revela la mayor parte del tiempo dedicado a la llamada sortedmatch(levels(i[[lc]]), levels(x[[rc]])? Esto no es realmente la unión en sí (el algoritmo), sino un paso preliminar.

Se han realizado esfuerzos recientes para permitir columnas de caracteres en las claves, lo que debería resolver ese problema al integrarse más estrechamente con la propia tabla global de hash de cadenas de R. Ya se informan algunos resultados de referencia, test.data.table()pero ese código aún no está conectado para reemplazar los niveles de coincidencia de niveles.

¿Los pandas se fusionan más rápido que data.tablelas columnas enteras normales? Esa debería ser una forma de aislar el algoritmo en sí mismo frente a los factores.

Además, data.tabletiene series temporales fusionadas en mente. Dos aspectos a eso: i) claves ordenadas de múltiples columnas como (id, fecha y hora) ii) unión prevaleciente rápida ( roll=TRUE) también conocida como última observación llevada adelante.

Necesitaré algo de tiempo para confirmar, ya que es la primera vez que veo la comparación con la data.tablepresentada.


ACTUALIZACIÓN de data.table v1.8.0 lanzado en julio de 2012

  • La función interna sortedmatch () se eliminó y se reemplazó con chmatch () al hacer coincidir los niveles i con los niveles x para columnas de tipo 'factor'. Este paso preliminar estaba causando una desaceleración significativa (conocida) cuando el número de niveles de una columna de factor era grande (por ejemplo,> 10,000). Exacerbado en las pruebas de unir cuatro de esas columnas, como lo demuestra Wes McKinney (autor del paquete Python Pandas). Hacer coincidir 1 millón de cadenas de las cuales 600,000 son únicas ahora se reduce de 16s a 0.5s, por ejemplo.

También en ese lanzamiento fue:

  • las columnas de caracteres ahora están permitidas en las claves y se prefieren factorizar. data.table () y setkey () ya no obligan al personaje a factorizar. Los factores aún son compatibles. Implementa FR # 1493, FR # 1224 y (parcialmente) FR # 951.

  • Nuevas funciones chmatch () y% chin%, versiones más rápidas de match () y% in% para vectores de caracteres. Se utiliza el caché de cadenas interno de R (no se crea una tabla hash). Son aproximadamente 4 veces más rápidos que match () en el ejemplo en? Chmatch.

A partir de septiembre de 2013 data.table es v1.8.10 en CRAN y estamos trabajando en v1.9.0. NOTICIAS se actualiza en vivo.


Pero como escribí originalmente, arriba:

data.tabletiene series temporales fusionadas en mente. Dos aspectos a eso: i) claves ordenadas de múltiples columnas como (id, fecha y hora) ii) unión prevaleciente rápida ( roll=TRUE) también conocida como última observación llevada adelante.

Por lo tanto, la unión equitativa de dos columnas de caracteres de Pandas probablemente sea aún más rápida que data.table. Ya que suena como hash las dos columnas combinadas. data.table no teclea la clave porque tiene en mente las combinaciones ordenadas predominantes. Una "clave" en data.table es literalmente solo el orden de clasificación (similar a un índice agrupado en SQL; es decir, así es como se ordenan los datos en RAM). En la lista hay que agregar claves secundarias, por ejemplo.

En resumen, la deslumbrante diferencia de velocidad resaltada por esta prueba particular de columna de dos caracteres con más de 10,000 cadenas únicas no debería ser tan mala ahora, ya que el problema conocido se ha solucionado.

Matt Dowle
fuente
66
Si proporciona un caso de prueba para un conjunto de datos razonablemente grande y realista, me complacerá ejecutar los puntos de referencia. Eres más que bienvenido, también. De hecho, todavía no he optimizado el código para el caso de la clave de unión de enteros (¡ponlo en mi lista de tareas pendientes!), Pero puede esperar un rendimiento significativamente mejor que el caso de la cadena dado el estudio de tabla hash en la presentación vinculada.
Wes McKinney
22
No uso ninguna de estas bibliotecas, pero me complace ver una respuesta constructiva del lado R en la forma de Matthew Dowle.
SlowLearner
3
Aquí hay algunos resultados de Rprof pastie.org/3258362 . Parece que el 20-40% del tiempo se gasta en una clasificación ordenada según el tipo de unión. Tendré que buscar columnas enteras en otra ocasión: hice un problema de GitHub de pandas para recordarme que optimice ese caso ( github.com/wesm/pandas/issues/682 )
Wes McKinney el
14
@AndyHayden Las mejoras se realizaron hace algún tiempo. Editaré en los artículos de NOTICIAS. Wes eligió una prueba específica (equi unir dos columnas de caracteres) que jugó en ese problema conocido. Si hubiera elegido columnas enteras, habría sido diferente. Y si me hubiera avisado antes de presentar el punto de referencia en la conferencia, entonces podría haberle contado más sobre el problema conocido.
Matt Dowle
191

La razón por la que pandas es más rápido es porque se me ocurrió un algoritmo mejor, que se implementa con mucho cuidado utilizando una implementación rápida de tabla hash: klib y en C / Cython para evitar la sobrecarga del intérprete de Python para las partes no vectorizables. El algoritmo se describe con cierto detalle en mi presentación: una mirada al diseño y desarrollo de pandas .

La comparación con data.tablees realmente un poco interesante porque el objetivo de las R data.tablees que contiene índices precalculados para varias columnas para acelerar operaciones como la selección de datos y las fusiones. En este caso (la base de datos se une), el DataFrame de pandas no contiene información precalculada que se esté utilizando para la fusión, por así decirlo, es una fusión "en frío". Si hubiera almacenado las versiones factorizadas de las teclas de combinación, la combinación sería significativamente más rápida, ya que la factorización es el mayor cuello de botella para este algoritmo.

También debo agregar que el diseño interno del DataFrame de pandas es mucho más adecuado para este tipo de operaciones que el data.frame de R (que es solo una lista de arreglos internos).

Wes McKinney
fuente
76
Por supuesto, ahora que lo ha descubierto todo en Python, debería ser fácil traducirlo a R;)
hadley
37
Pero, ¿por qué alguien querría hacerlo? :)
ely
9
Umm ... ¿tal vez porque querrían que las operaciones de datos fueran más rápidas en R? Solo adivinando :))
lebatsnok
28
Hola Wes, parece que tus resultados data.tablefueron impulsados ​​principalmente por un error que desde entonces se ha solucionado. ¿Hay alguna posibilidad de que pueda volver a ejecutar su punto de referencia y escribir una publicación de blog actualizada?
Zach
66
Zach asegúrate de revisar esto: github.com/Rdatatable/data.table/wiki/Benchmarks-:-Grouping
Merik
37

Este tema tiene dos años pero parece un lugar probable para que la gente aterrice cuando buscan comparaciones de pandas y datos.

Dado que ambos han evolucionado con el tiempo, quiero publicar una comparación relativamente nueva (desde 2014) aquí para los usuarios interesados: https://github.com/Rdatatable/data.table/wiki/Benchmarks-:-Grouping

Sería interesante saber si Wes y / o Matt (que, por cierto, son creadores de Pandas y data.table respectivamente y ambos han comentado anteriormente) tienen alguna noticia que agregar aquí también.

- ACTUALIZACIÓN -

Un comentario publicado a continuación por jangorecki contiene un enlace que creo que es muy útil: https://github.com/szilard/benchm-databases

https://github.com/szilard/benchm-databases/blob/master/plot.png

Este gráfico muestra los tiempos promedio de agregación y operaciones de unión para diferentes tecnologías ( menor = más rápido ; comparación actualizada por última vez en septiembre de 2016). Fue realmente educativo para mí.

Volviendo a la pregunta, R DT keyy R DTse refieren a los sabores con clave / sin codificar de R data.table y pasar a ser más rápido en este punto de referencia distinto de las pandas de Python ( Py pandas).

Merik
fuente
1
¡Estaba a punto de publicar esto! Gracias por añadir.
Zach
77
@Zach vea esto: github.com/szilard/benchm-databases y eso también es bueno: speakerdeck.com/szilard/…
jangorecki
1
@Zach, cuatro años más tarde, finalmente aparecieron nuevos resultados de referencia, vea mi respuesta a continuación.
Jangorecki
7

Hay excelentes respuestas, especialmente hechas por los autores de ambas herramientas sobre las que se formula la pregunta. La respuesta de Matt explica el caso reportado en la pregunta, que fue causado por un error y no por un algoritmo de fusión. El error se solucionó al día siguiente, hace más de 7 años.

En mi respuesta, proporcionaré algunos tiempos actualizados de operación de fusión para data.table y pandas. Tenga en cuenta que plyr y base R merge no están incluidos.

Los tiempos que presento provienen del proyecto db-benchmark , un punto de referencia reproducible que se ejecuta continuamente. Actualiza las herramientas a versiones recientes y vuelve a ejecutar scripts de referencia. Ejecuta muchas otras soluciones de software. Si está interesado en Spark, Dask y algunos otros, asegúrese de consultar el enlace.


A partir de ahora ... (aún por implementar: un tamaño de datos más y 5 preguntas más)

Probamos 2 tamaños de datos diferentes de la tabla LHS.
Para cada uno de esos tamaños de datos, ejecutamos 5 preguntas de fusión diferentes.

q1: unión interna LHS RHS- pequeña en número entero
q2: unión interna LHS medio RHS en entero
q3: unión externa LHS medio RHS en entero
q4: unión interna LHS medio RHS en factor (categórico)
q5: unión interna LHS RHS- grande en número entero

La mesa RHS es de 3 tamaños diferentes.

  • pequeño se traduce al tamaño de LHS / 1e6
  • medio se traduce al tamaño de LHS / 1e3
  • grande se traduce al tamaño de LHS

En todos los casos, hay alrededor del 90% de las filas coincidentes entre LHS y RHS, y no hay duplicados en la columna de unión de RHS (sin producto cartesiano).


A partir de ahora (se ejecuta el 2 de noviembre de 2019)

pandas 0.25.3 lanzado el 1 de noviembre de 2019
data.table 0.12.7 (92abb70) lanzado el 2 de noviembre de 2019

Los tiempos siguientes son en segundos, para dos tamaños de datos diferentes de LHS. La columna pd2dtse agrega a la relación de almacenamiento de campo de cuántas veces los pandas son más lentos que data.table.

  • 0.5 GB de datos LHS
+-----------+--------------+----------+--------+
| question  |  data.table  |  pandas  |  pd2dt |
+-----------+--------------+----------+--------+
| q1        |        0.51  |    3.60  |      7 |
| q2        |        0.50  |    7.37  |     14 |
| q3        |        0.90  |    4.82  |      5 |
| q4        |        0.47  |    5.86  |     12 |
| q5        |        2.55  |   54.10  |     21 |
+-----------+--------------+----------+--------+
  • 5 GB de datos LHS
+-----------+--------------+----------+--------+
| question  |  data.table  |  pandas  |  pd2dt |
+-----------+--------------+----------+--------+
| q1        |        6.32  |    89.0  |     14 |
| q2        |        5.72  |   108.0  |     18 |
| q3        |       11.00  |    56.9  |      5 |
| q4        |        5.57  |    90.1  |     16 |
| q5        |       30.70  |   731.0  |     23 |
+-----------+--------------+----------+--------+
jangorecki
fuente
¡Gracias por la actualización del futuro! ¿Podría agregar una columna para la implementación R vs python de data.table?
Zach
1
Creo que es bueno ir al sitio web y verificarlo, incluso para mirar R dt vs pandas. Y pyDT no era parte de la pregunta original realmente.
Jangorecki