Warum wurden Pandas 2012 in Python schneller zusammengeführt als data.table in R?

160

Ich bin kürzlich auf die Pandas- Bibliothek für Python gestoßen, die laut diesem Benchmark sehr schnelle In-Memory-Zusammenführungen durchführt. Es ist sogar schneller als das data.table- Paket in R (meine bevorzugte Sprache für die Analyse).

Warum ist pandasso viel schneller als data.table? Liegt es an einem inhärenten Geschwindigkeitsvorteil, den Python gegenüber R hat, oder gibt es einen Kompromiss, den ich nicht kenne? Gibt es eine Möglichkeit, innere und äußere Verbindungen herzustellen, data.tableohne auf merge(X, Y, all=FALSE)und zurückzugreifen merge(X, Y, all=TRUE)?

Vergleich

Hier ist der R-Code und der Python-Code, die zum Benchmarking der verschiedenen Pakete verwendet werden.

Zach
quelle
10
@JoshuaUlrich: IIRC data.tableerbt nur von data.frame, aber es basiert auf C-Code unter der Haube.
digEmAll
4
@Joshua Was meinst du mit "data.frames sind langsam, auch wenn du sie in C manipulierst"? Ist das relativ zu etwas anderem? Und langsam bei was?
Matt Dowle
12
@JoshuaUlrich Ich habe gerade bemerkt, dass dieser Kommentarpfad nie ins Bett gebracht wurde. Also, um es zu klären: set()wurde data.tablekurz nach dieser Diskussion hinzugefügt . Sehr ähnlich, :=vermeidet aber den geringen Overhead [.data.tablebeim Schleifen und ist folglich so schnell wie matrix. Daher data.frame kann genauso schnell wie Matrix manipuliert werden. Benchmark ist da .
Matt Dowle
5
Können wir eine aktualisierte Version dieses Benchmarks erhalten, ist es ziemlich klar, dass diese Bank tatsächlich ein Randfall war und dass dies inzwischen behoben ist. Angesichts der Tatsache, dass alle Benchmarks, die ich gesehen habe, zeigen, dass data.table schneller ist, würde ich gerne sehen, wie die Zusammenführungsnummer lautet.
statquant
3
@statquant Ich habe den ursprünglichen Benchmark nicht ausgeführt, aber ich würde wirklich gerne sehen, wie Wes den Benchmark aktualisiert.
Zach

Antworten:

120

Es sieht so aus, als hätte Wes ein bekanntes Problem entdeckt, data.tableals die Anzahl der eindeutigen Zeichenfolgen ( Ebenen ) groß war: 10.000.

Zeigt Rprof()die meiste Zeit des Anrufs an sortedmatch(levels(i[[lc]]), levels(x[[rc]])? Dies ist nicht wirklich der Join selbst (der Algorithmus), sondern ein vorläufiger Schritt.

In jüngster Zeit wurden Zeichenspalten in Schlüsseln zugelassen, wodurch dieses Problem durch eine engere Integration in Rs eigene globale Zeichenfolgen-Hash-Tabelle behoben werden sollte. Einige Benchmark-Ergebnisse wurden bereits von gemeldet, test.data.table()aber dieser Code ist noch nicht angeschlossen, um die Level-to-Level-Übereinstimmungen zu ersetzen.

Sind Pandas schneller zusammengeführt als data.tablebei normalen Ganzzahlspalten? Dies sollte eine Möglichkeit sein, den Algorithmus selbst gegenüber Faktorproblemen zu isolieren.

Auch data.tablehat Zeitreihen im Auge zu behalten. Zwei Aspekte dazu: i) mehrspaltig geordnete Schlüssel wie (id, datetime) ii) schnell vorherrschende join ( roll=TRUE), auch bekannt als letzte übertragene Beobachtung.

Ich werde einige Zeit brauchen, um zu bestätigen, da es das erste Mal ist, dass ich den Vergleich mit data.tabledem präsentierten gesehen habe.


UPDATE von data.table v1.8.0 veröffentlicht im Juli 2012

  • Interne Funktion sortedmatch () entfernt und durch chmatch () ersetzt, wenn i-Ebenen mit x-Ebenen für Spalten vom Typ 'Faktor' abgeglichen werden. Dieser vorläufige Schritt verursachte eine (bekannte) signifikante Verlangsamung, wenn die Anzahl der Ebenen einer Faktorsäule groß war (z. B.> 10.000). Verschärft durch Tests zum Verbinden von vier solchen Spalten, wie Wes McKinney (Autor des Python-Pakets Pandas) demonstrierte. Das Abgleichen von 1 Million Zeichenfolgen, von denen 600.000 einzigartig sind, wird jetzt beispielsweise von 16 auf 0,5 Sekunden reduziert.

auch in dieser Veröffentlichung war:

  • Zeichenspalten sind jetzt in Schlüsseln zulässig und werden bevorzugt berücksichtigt. data.table () und setkey () zwingen Zeichen nicht mehr zum Faktor. Faktoren werden weiterhin unterstützt. Implementiert FR # 1493, FR # 1224 und (teilweise) FR # 951.

  • Neue Funktionen chmatch () und% chin%, schnellere Versionen von match () und% in% für Zeichenvektoren. Der interne String-Cache von R wird verwendet (es wird keine Hash-Tabelle erstellt). Sie sind ungefähr viermal schneller als match () im Beispiel in? Chmatch.

Ab September 2013 ist data.table v1.8.10 für CRAN und wir arbeiten an v1.9.0. NEWS wird live aktualisiert.


Aber wie ich ursprünglich oben geschrieben habe:

data.tablehat Zeitreihenverschmelzung im Sinn. Zwei Aspekte dazu: i) mehrspaltig geordnete Schlüssel wie (id, datetime) ii) schnell vorherrschende join ( roll=TRUE), auch bekannt als letzte übertragene Beobachtung.

Der Pandas-Equi-Join aus zwei Zeichenspalten ist also wahrscheinlich immer noch schneller als data.table. Da es so klingt, als würde es die kombinierten zwei Spalten hashen. data.table hasht den Schlüssel nicht, da die vorherrschenden geordneten Joins berücksichtigt wurden. Ein "Schlüssel" in data.table ist buchstäblich nur die Sortierreihenfolge (ähnlich einem Clustered-Index in SQL; dh so werden die Daten im RAM sortiert). Auf der Liste stehen beispielsweise Sekundärschlüssel.

Zusammenfassend sollte der eklatante Geschwindigkeitsunterschied, der durch diesen speziellen Test mit zwei Zeichenspalten mit über 10.000 eindeutigen Zeichenfolgen hervorgehoben wird, jetzt nicht so schlimm sein, da das bekannte Problem behoben wurde.

Matt Dowle
quelle
6
Wenn Sie einen Testfall für einen relativ großen, realistischen Datensatz liefern, führe ich gerne die Benchmarks durch. Sie sind auch mehr als willkommen. Ich habe den Code für den Integer-Join-Key-Fall noch nicht optimiert (setzen Sie ihn auf meine ToDo-Liste!), Aber Sie können angesichts der Hash-Tabellenstudie in der verknüpften Präsentation eine deutlich bessere Leistung als den String-Fall erwarten.
Wes McKinney
22
Ich benutze keine dieser Bibliotheken, freue mich aber über eine konstruktive Antwort von der R-Seite in Form von Matthew Dowle.
SlowLearner
3
Hier sind einige Rprof-Ergebnisse pastie.org/3258362 . Es sieht so aus, als würden 20-40% der Zeit in sortierten Übereinstimmungen verbracht, abhängig vom Join-Typ. Ich muss ein anderes Mal in ganzzahlige Spalten schauen - ich habe ein Pandas-GitHub-Problem gemacht, um mich daran zu erinnern, diesen Fall zu optimieren ( github.com/wesm/pandas/issues/682 )
Wes McKinney
14
@AndyHayden Verbesserungen wurden vor einiger Zeit vorgenommen. Ich werde in den NEWS-Elementen bearbeiten. Wes wählte einen bestimmten Test aus (gleichbedeutend mit dem Verbinden von zwei Zeichenspalten), der sich mit diesem bekannten Problem befasste. Wenn er ganzzahlige Spalten ausgewählt hätte, wäre es anders gewesen. Und wenn er mich vor der Präsentation des Benchmarks auf der Konferenz informiert hätte, hätte ich ihm mehr über das bekannte Problem erzählen können.
Matt Dowle
191

Der Grund, warum Pandas schneller sind, liegt darin, dass ich einen besseren Algorithmus entwickelt habe, der sehr sorgfältig mithilfe einer schnellen Hash-Tabellenimplementierung implementiert wird - klib und in C / Cython , um den Python-Interpreter-Overhead für die nicht vektorisierbaren Teile zu vermeiden. Der Algorithmus wird in meiner Präsentation ausführlich beschrieben: Ein Blick in das Design und die Entwicklung von Pandas .

Der Vergleich mit data.tableist tatsächlich ein bisschen interessant, da der springende Punkt bei Rs darin data.tablebesteht, dass er vorberechnete Indizes für verschiedene Spalten enthält, um Operationen wie Datenauswahl und Zusammenführung zu beschleunigen. In diesem Fall (Datenbankverknüpfungen) enthält der DataFrame von pandas keine vorberechneten Informationen , die für die Zusammenführung verwendet werden. Es handelt sich also sozusagen um eine "kalte" Zusammenführung. Wenn ich die faktorisierten Versionen der Verknüpfungsschlüssel gespeichert hätte, wäre die Verknüpfung erheblich schneller - da die Faktorisierung der größte Engpass für diesen Algorithmus ist.

Ich sollte auch hinzufügen, dass das interne Design des DataFrame von pandas für diese Art von Operationen viel zugänglicher ist als das data.frame von R (das nur eine interne Liste von Arrays ist).

Wes McKinney
quelle
76
Natürlich sollte es jetzt, da Sie alles in Python herausgefunden haben, einfach sein, es in R zu übersetzen;)
Hadley
37
Aber warum sollte jemand jemals wollen? :)
ely
9
Ähm ... vielleicht, weil sie möchten, dass Datenoperationen in R schneller sind? Nur raten :))
lebatsnok
28
Hallo Wes, es scheint, dass Ihre Ergebnisse data.tableprimär von einem Fehler getrieben wurden, der inzwischen behoben wurde. Gibt es eine Chance, dass Sie Ihren Benchmark erneut ausführen und einen aktualisierten Blog-Beitrag schreiben?
Zach
6
Zach stellen Sie sicher, dass Sie dies überprüfen: github.com/Rdatatable/data.table/wiki/Benchmarks-:-Grouping
Merik
37

Dieses Thema ist zwei Jahre alt, scheint aber ein wahrscheinlicher Ort für Menschen zu sein, wenn sie nach Vergleichen von Pandas und data.table suchen

Da sich beide im Laufe der Zeit weiterentwickelt haben, möchte ich hier einen relativ neueren Vergleich (ab 2014) für die interessierten Benutzer veröffentlichen: https://github.com/Rdatatable/data.table/wiki/Benchmarks-:-Grouping

Es wäre interessant zu wissen, ob Wes und / oder Matt (die übrigens Schöpfer von Pandas bzw. data.table sind und beide oben kommentiert haben) auch hier Neuigkeiten hinzuzufügen haben.

- UPDATE -

Ein Kommentar von jangorecki enthält einen Link, den ich für sehr nützlich halte: https://github.com/szilard/benchm-databases

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

Diese Grafik zeigt die durchschnittlichen Zeiten für Aggregations- und Verknüpfungsvorgänge für verschiedene Technologien ( niedriger = schneller ; Vergleich zuletzt aktualisiert im September 2016). Es war wirklich lehrreich für mich.

Gehen Sie zurück zu der Frage R DT keyund R DTbeziehen Sie sich auf die Keyed / Unkeyed-Varianten von Rs data.table, die in diesem Benchmark schneller sind als Pythons Pandas ( Py pandas).

Merik
quelle
1
Ich wollte das gerade posten! Danke fürs Hinzufügen.
Zach
7
@ Zach sehen dies: github.com/szilard/benchm-databases und das ist auch schön: Speakerdeck.com/szilard/…
Jangorecki
1
@Zach vier Jahre später kamen endlich neue Benchmark-Ergebnisse, siehe meine Antwort unten.
Jangorecki
7

Es gibt großartige Antworten, insbesondere von Autoren beider Tools, nach denen gefragt wird. Matts Antwort erklärt den in der Frage gemeldeten Fall, dass er durch einen Fehler und nicht durch einen Zusammenführungsalgorithmus verursacht wurde. Der Fehler wurde am nächsten Tag behoben, bereits vor mehr als 7 Jahren.

In meiner Antwort werde ich einige aktuelle Zeitpunkte für den Zusammenführungsvorgang für data.table und pandas bereitstellen. Beachten Sie, dass Plyr und Base R nicht zusammengeführt werden.

Die von mir vorgestellten Timings stammen aus dem db-Benchmark- Projekt, einem kontinuierlich durchgeführten reproduzierbaren Benchmark. Es aktualisiert Tools auf aktuelle Versionen und führt Benchmark-Skripte erneut aus. Es werden viele andere Softwarelösungen ausgeführt. Wenn Sie an Spark, Dask und einigen anderen interessiert sind, überprüfen Sie unbedingt den Link.


Ab sofort ... (noch zu implementieren: noch eine Datengröße und 5 weitere Fragen)

Wir testen 2 verschiedene Datengrößen der LHS-Tabelle.
Für jede dieser Datengrößen führen wir 5 verschiedene Zusammenführungsfragen aus.

q1: LHS-Innenverknüpfung RHS- klein auf Ganzzahl
q2: LHS-Innenverknüpfung RHS-Medium auf Ganzzahl
q3: LHS- Außenverknüpfung RHS-Medium auf Ganzzahl
q4: LHS-Innenverknüpfung RHS-Medium auf Faktor (kategorisch)
q5: LHS-Innenverknüpfung RHS- groß auf Ganzzahl

Der RHS-Tisch hat 3 verschiedene Größen

  • klein bedeutet LHS / 1e6
  • Medium bedeutet LHS / 1e3
  • groß bedeutet Größe von LHS

In allen Fällen gibt es ungefähr 90% der übereinstimmenden Zeilen zwischen LHS und RHS und keine Duplikate in der RHS-Verbindungsspalte (kein kartesisches Produkt).


Ab sofort (läuft am 2. November 2019)

pandas 0.25.3 veröffentlicht am 1. November 2019
data.table 0.12.7 (92abb70) veröffentlicht am 2. November 2019

Die folgenden Zeitangaben erfolgen in Sekunden für zwei verschiedene Datengrößen von LHS. In der Spalte pd2dtwird das Feldspeicherverhältnis hinzugefügt, wie oft Pandas langsamer als data.table sind.

  • 0,5 GB LHS-Daten
+-----------+--------------+----------+--------+
| 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 LHS-Daten
+-----------+--------------+----------+--------+
| 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
quelle
Vielen Dank für das Update aus der Zukunft! Könnten Sie eine Spalte für die R vs Python-Implementierung von data.table hinzufügen?
Zach
1
Ich denke, es ist gut, einfach auf die Website zu gehen und sie zu überprüfen, selbst wenn man sich R dt vs pandas ansieht. Und pyDT war nicht wirklich Teil der ursprünglichen Frage.
Jangorecki