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

Question

Je suis récemment tombé sur le pandas bibliothèque pour python, qui selon cette référence effectue des fusions en mémoire très rapides.C'est encore plus rapide que le données.table package en R (mon langage de choix pour l’analyse).

Pourquoi est-ce pandas tellement plus rapide que data.table?Est-ce à cause d'un avantage de vitesse inhérent à 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.table sans recourir à merge(X, Y, all=FALSE) et merge(X, Y, all=TRUE)?

Ici se trouve le Code R et le Code Python utilisé pour comparer les différents packages.

Answer 1

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

Fait Rprof() révéler la plupart du temps passé dans l'appel sortedmatch(levels(i[[lc]]), levels(x[[rc]])?Il ne s'agit pas vraiment de la jointure elle-même (l'algorithme), mais d'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.table pour les colonnes entières régulières ?Cela devrait être un moyen d'isoler l'algorithme lui-même des problèmes de facteurs.

Aussi, data.table a fusion de séries chronologiques à l'esprit.Deux aspects à cela :i) plusieurs colonnes commandé clés telles que (id, datetime) ii) jointure rapide (roll=TRUE) alias.dernière observation reportée.

Il me faudra un peu de temps pour confirmer car c'est la première fois que je vois une comparaison avec data.table tel que présenté.

---

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 des niveaux i aux niveaux x pour les colonnes de type 'facteur'.Ceci l’étape préliminaire provoquait un ralentissement significatif (connu) lorsque le nombre de des niveaux d’une colonne de facteurs était grande (p. ex.>10 000).Exacerbé dans les tests d’assemblage de quatre colonnes de ce type, comme l’a démontré Wes McKinney (auteur du paquet Python Pandas).Correspondant à 1 million de chaînes, dont dont 600 000 sont uniques est désormais réduit de 16 s à 0,5 s, par exemple.

également dans cette version était :

• Les colonnes de caractères sont maintenant autorisées dans les clés et sont préférées à facteur.data.table() et setkey() ne forcent plus le caractère à facteur.Les facteurs sont toujours pris en charge.Implémente 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îne interne de R est used (aucune table de hachage n’est construite).Ils sont environ 4 fois plus rapides than match() sur l’exemple dans ?chmatch.

Depuis septembre 2013, data.table est la version 1.8.10 sur CRAN et nous travaillons sur la version 1.9.0. NOUVELLES est mis à jour en direct.

---

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

data.table a fusion de séries chronologiques à l'esprit.Deux aspects à cela :i) Multi colonne commandé clés telles que (id,datetime) ii) fast prevailing joindre (roll=TRUE) alias.dernière observation reportée.

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

En résumé, la différence de vitesse flagrante mise en évidence par ce test particulier sur deux colonnes de 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.

Answer 2

La raison pour laquelle les pandas sont plus rapides est que j'ai trouvé un meilleur algorithme, qui est implémenté très soigneusement en utilisant une implémentation rapide d'une 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 aperçu de la conception et du développement des pandas.

La comparaison avec data.table est en fait un peu intéressant parce que tout l'intérêt des R data.table c'est qu'il contient index pré-calculés pour diverses colonnes afin d'accélérer les opérations telles que la sélection de données et les fusions.Dans ce cas (jointures de base de données), le DataFrame de pandas contient aucune information pré-calculée qui est utilisé 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 nettement 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 le data.frame de R (qui n'est qu'une liste de tableaux en interne).

Answer 3

Ce sujet date de deux ans mais semble être un endroit probable où les gens peuvent atterrir lorsqu'ils recherchent des comparaisons entre Pandas et data.table.

Étant donné que ces deux éléments ont évolué au fil du temps, je souhaite publier ici une comparaison relativement plus récente (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 data.table et ont tous deux commenté ci-dessus) ont également des nouvelles à ajouter ici.

-- MISE À JOUR --

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

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

Pour en revenir à la question, R DT key et R DT faites référence aux versions avec/sans clé de data.table de R et se révèlent être plus rapides dans ce benchmark que les Pandas de Python (Py pandas).

Answer 4

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

Dans ma réponse, je fournirai des horaires à jour pour les opérations de fusion pour data.table et pandas.Notez que la fusion plyr et base R ne sont pas incluses.

Les horaires que je présente proviennent de référence de base de données projet, un benchmark reproductible exécuté 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, mais dans cette réponse, je ne fournirai que les horaires data.table.Si vous êtes intéressé par Spark, Dask et quelques autres, assurez-vous de le vérifier en ligne.

---

A partir de maintenant...(reste à mettre en œuvre :une taille de données supplémentaire et 5 questions supplémentaires)

Nous testons 2 tailles de données différentes du tableau 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 un entier
Q2 :Jointure interne LHS RHS-moyen sur un entier
q3 :LHS extérieur rejoindre RHS-medium sur un entier
Q4 :LHS interne rejoint RHS-medium sur facteur (catégorique)
Q5 :Jointure interne LHS RHS-grand sur un 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 (le 2 novembre 2019)

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

Les timings ci-dessous sont en secondes, pour deux tailles de données différentes de LHS.Colonne pd2dt est ajouté un rapport de stockage de champ indiquant combien de fois 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 |
+-----------+--------------+----------+--------+