Pourquoi les fusions pandas en python étaient-elles plus rapides que les fusions data.table dans R en 2012?

Je suis récemment tombé sur la bibliothèque pandas pour python, qui, selon ce benchmark, effectue des fusions en mémoire très rapides. C'est encore plus rapide que le package data.table en R (ma langue de choix pour l'analyse).

Pourquoi est-ce pandastellement plus rapide que data.table? Est-ce à cause d'un avantage inhérent à la vitesse de python par rapport à R, ou y a-t-il un compromis dont je ne suis pas au courant? Existe-t-il un moyen d'effectuer des jointures internes et externes data.tablesans recourir à merge(X, Y, all=FALSE)et merge(X, Y, all=TRUE)?

Voici le code R et le code Python utilisés pour comparer les différents packages.

Il semble que Wes ait découvert un problème connu data.tablelorsque le nombre de chaînes uniques ( niveaux ) est élevé: 10 000.

Révèle-t-il la Rprof()plupart du temps passé dans l'appel sortedmatch(levels(i[[lc]]), levels(x[[rc]])? Ce n'est pas vraiment la jointure elle-même (l'algorithme), mais une étape préliminaire.

Des efforts récents ont été déployés pour autoriser les colonnes de caractères dans les clés, ce qui devrait résoudre ce problème en s'intégrant plus étroitement à la propre table de hachage de chaînes globale de R. Certains résultats de référence sont déjà rapportés par test.data.table()mais ce code n'est pas encore connecté pour remplacer les niveaux par des niveaux correspondants.

Les pandas fusionnent-ils plus rapidement que data.tablepour les colonnes entières régulières? Cela devrait être un moyen d'isoler l'algorithme lui-même des problèmes de facteurs.

En outre, data.tablea séries temporelles fusion à l' esprit. Deux aspects à cela: i) clés ordonnées multi-colonnes telles que (id, datetime) ii) jointure prédominante rapide ( roll=TRUE) aka dernière observation reportée.

J'aurai besoin d'un peu de temps pour confirmer car c'est la première fois que j'ai vu la comparaison avec data.tablecelle présentée.

MISE À JOUR de data.table v1.8.0 publiée en juillet 2012

• La fonction interne sortedmatch () a été supprimée et remplacée par chmatch () lors de la mise en correspondance de i niveaux avec x niveaux pour les colonnes de type 'factor'. Cette étape préliminaire provoquait un ralentissement significatif (connu) lorsque le nombre de niveaux d'une colonne de facteurs était important (par exemple> 10 000). Exacerbé dans les tests de jonction de quatre de ces colonnes, comme l'a démontré Wes McKinney (auteur du package Python Pandas). La correspondance de 1 million de chaînes, dont 600 000 sont uniques, passe désormais de 16 à 0,5, par exemple.

également dans cette version était:

• les colonnes de caractères sont désormais autorisées dans les clés et sont préférables à factoriser. data.table () et setkey () ne contraignent plus le caractère à factoriser. Les facteurs sont toujours pris en charge. Met en œuvre FR # 1493, FR # 1224 et (partiellement) FR # 951.

• Nouvelles fonctions chmatch () et% chin%, versions plus rapides de match () et% in% pour les vecteurs de caractères. Le cache de chaînes interne de R est utilisé (aucune table de hachage n'est construite). Ils sont environ 4 fois plus rapides que match () sur l'exemple dans? Chmatch.

Depuis septembre 2013, data.table est v1.8.10 sur CRAN et nous travaillons sur v1.9.0. NEWS est mis à jour en direct.

Mais comme je l'ai écrit à l'origine, ci-dessus:

data.tablea en tête la fusion des séries chronologiques . Deux aspects à cela: i) clés ordonnées multi-colonnes telles que (id, datetime) ii) jointure prédominante rapide ( roll=TRUE) aka dernière observation reportée.

Ainsi, la jointure Pandas equi de deux colonnes de caractères est probablement encore plus rapide que data.table. Puisqu'il semble hacher les deux colonnes combinées. data.table ne hache pas la clé car elle a en tête les jointures ordonnées dominantes. Une "clé" dans data.table est littéralement juste l'ordre de tri (similaire à un index clusterisé en SQL; c'est-à-dire ainsi que les données sont ordonnées dans la RAM). Sur la liste est d'ajouter des clés secondaires, par exemple.

En résumé, la différence de vitesse flagrante mise en évidence par ce test particulier de colonnes à deux caractères avec plus de 10 000 chaînes uniques ne devrait pas être aussi grave maintenant, puisque le problème connu a été résolu.

La raison pour laquelle pandas est plus rapide est que j'ai proposé un meilleur algorithme, qui est implémenté très soigneusement en utilisant une implémentation rapide de table de hachage - klib et en C / Cython pour éviter la surcharge de l'interpréteur Python pour les parties non vectorisables. L'algorithme est décrit en détail dans ma présentation: Un regard sur la conception et le développement des pandas .

La comparaison avec data.tableest en fait un peu intéressante car tout l'intérêt des R data.tableest qu'il contient des index pré-calculés pour diverses colonnes afin d'accélérer les opérations telles que la sélection et les fusions de données. Dans ce cas (jointure de base de données), le DataFrame de pandas ne contient aucune information pré-calculée qui est utilisée pour la fusion, pour ainsi dire c'est une fusion "à froid". Si j'avais stocké les versions factorisées des clés de jointure, la jointure serait beaucoup plus rapide - car la factorisation est le plus gros goulot d'étranglement pour cet algorithme.

Je dois également ajouter que la conception interne du DataFrame de pandas est beaucoup plus adaptée à ce type d'opérations que data.frame de R (qui est juste une liste de tableaux en interne).

Ce sujet a deux ans mais semble être un endroit probable où les gens peuvent atterrir lorsqu'ils recherchent des comparaisons de Pandas et de données.

Étant donné que ces deux éléments ont évolué au fil du temps, je souhaite publier ici une comparaison relativement plus récente (à partir de 2014) pour les utilisateurs intéressés: https://github.com/Rdatatable/data.table/wiki/Benchmarks-:-Grouping

Il serait intéressant de savoir si Wes et / ou Matt (qui, soit dit en passant, sont respectivement les créateurs de Pandas et de data.table et ont tous deux commenté ci-dessus) ont également des nouvelles à ajouter ici.

-- METTRE À JOUR --

Un commentaire posté ci-dessous par jangorecki contient un lien que je trouve très utile: https://github.com/szilard/benchm-databases

Ce graphique représente les temps moyens d'agrégation et de jointure des opérations pour différentes technologies ( inférieur = plus rapide ; comparaison mise à jour pour la dernière fois en septembre 2016). C'était vraiment éducatif pour moi.

Revenons à la question R DT keyet R DTréférez - vous aux saveurs à clé / non clé de la table data.table de R et se trouvent être plus rapides dans ce benchmark que Pandas de Python ( Py pandas).

Il existe d'excellentes réponses, notamment faites par les auteurs des deux outils sur lesquels la question se pose. La réponse de Matt explique le cas signalé dans la question, qu'il a été causé par un bogue et non par un algorithme de fusion. Le bug a été corrigé le lendemain, il y a plus de 7 ans déjà.

Dans ma réponse, je fournirai des horaires à jour de l'opération de fusion pour data.table et pandas. Notez que la fusion plyr et base R n'est pas incluse.

Les timings que je présente proviennent du projet db-benchmark , un benchmark reproductible en continu. Il met à niveau les outils vers les versions récentes et réexécute les scripts de référence. Il exécute de nombreuses autres solutions logicielles. Si vous êtes intéressé par Spark, Dask et quelques autres, assurez-vous de vérifier le lien.

A partir de maintenant ... (encore à implémenter: encore une taille de données et 5 questions supplémentaires)

Nous testons 2 tailles de données différentes de la table LHS.
Pour chacune de ces tailles de données, nous exécutons 5 questions de fusion différentes.

q1: Jointure interne LHS RHS- petit sur l'entier
q2: Jointure interne LHS RHS-medium sur l'entier
q3: Jointure externe LHS RHS-medium sur l'entier
q4: Jointure interne LHS RHS-medium sur le facteur (catégorique)
q5: Jointure interne LHS RHS- gros sur entier

La table RHS est de 3 tailles différentes

• petit se traduit par une taille de LHS / 1e6
• moyen se traduit par une taille de LHS / 1e3
• grand se traduit par la taille de LHS

Dans tous les cas, il y a environ 90% de lignes correspondantes entre LHS et RHS, et aucun doublon dans la colonne de jonction RHS (pas de produit cartésien).

À partir de maintenant (exécuté le 2 novembre 2019)

pandas 0.25.3 publié le 1er novembre 2019
data.table 0.12.7 (92abb70) publié le 2 novembre 2019

Les durées ci-dessous sont en secondes, pour deux tailles de données différentes de LHS. La colonne pd2dtest le rapport de stockage de champ ajouté du nombre de fois que les pandas sont plus lents que data.table.

• 0,5 Go de données 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 Go de données 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 |
+-----------+--------------+----------+--------+