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

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)?

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

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.

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).

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

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).

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 |
+-----------+--------------+----------+--------+