Dlaczego łączenie pand w Pythonie było szybsze niż data.table w R w 2012 roku?

160

Niedawno natknąłem się na bibliotekę pand dla Pythona, która według tego testu porównawczego wykonuje bardzo szybkie połączenia w pamięci. Jest nawet szybszy niż pakiet data.table w R (mój język do analizy).

Dlaczego jest pandaso wiele szybszy niż data.table? Czy to z powodu nieodłącznej przewagi szybkości, jaką Python ma nad R, czy też jest jakiś kompromis, którego nie jestem świadomy? Czy istnieje sposób na wykonanie połączeń wewnętrznych i zewnętrznych data.tablebez uciekania się do merge(X, Y, all=FALSE)i merge(X, Y, all=TRUE)?

Porównanie

Oto kod R i kod Pythona używane do testów porównawczych różnych pakietów.

Zach
źródło
10
@JoshuaUlrich: IIRC data.tablepo prostu dziedziczy po data.frame, ale opiera się na kodzie C pod maską.
digEmAll
4
@Joshua Co masz na myśli, mówiąc „data.frames są wolne, nawet jeśli manipulujesz nimi w C”? Czy to odnosi się do czegoś innego? I w czym wolno?
Matt Dowle,
12
@JoshuaUlrich Właśnie zauważyłem, że ten ślad komentarza nigdy nie został położony do łóżka. Aby to wyjaśnić: set()dodano do data.tablewkrótce po tej dyskusji. Bardzo podobny do, :=ale unika niewielkiego narzutu, [.data.tablegdy jest zapętlony, a zatem jest tak szybki, jak matrix. Dlatego data.frame można nim manipulować równie szybko jak matrycą. Benchmark jest tutaj .
Matt Dowle
5
Czy możemy uzyskać zaktualizowaną wersję tego testu porównawczego, jest całkiem jasne, że ten test porównawczy był w rzeczywistości przypadkiem skrajnym i że jest to już naprawione. Biorąc pod uwagę, że wszystkie testy porównawcze, które widziałem, pokazują, że data.table jest szybsza, chciałbym zobaczyć, jaki jest numer scalania?
statquant
3
@statquant Nie uruchomiłem oryginalnego testu porównawczego, ale naprawdę chciałbym zobaczyć, jak Wes aktualizuje test.
Zach

Odpowiedzi:

120

Wygląda na to, że Wes mógł odkryć znany problem, data.tablegdy liczba unikalnych ciągów ( poziomów ) jest duża: 10 000.

Czy Rprof()ujawnia większość czasu spędzonego na rozmowie sortedmatch(levels(i[[lc]]), levels(x[[rc]])? To nie jest tak naprawdę samo łączenie (algorytm), ale wstępny krok.

Ostatnio podjęto wysiłki, aby zezwolić na kolumny znaków w kluczach, co powinno rozwiązać ten problem poprzez ściślejszą integrację z własną globalną tabelą skrótów ciągów R. Niektóre wyniki testów porównawczych są już zgłaszane przez, test.data.table()ale ten kod nie jest jeszcze podłączony, aby zastąpić poziomy pasującymi poziomami.

Czy pandy łączą się szybciej niż w data.tableprzypadku zwykłych kolumn całkowitych? Powinien to być sposób na oddzielenie samego algorytmu od problemów czynnikowych.

Również data.tablema szeregów czasowych seryjnej w umyśle. Dwa aspekty tego: i) klucze uporządkowane w wielu kolumnach , takie jak (id, datetime) ii) szybkie łączenie dominujące ( roll=TRUE), czyli ostatnia obserwacja przeniesiona do przodu.

Potrzebuję trochę czasu, aby potwierdzić, ponieważ jest to pierwsze, jakie widziałem w porównaniu do data.tableprezentowanego.


AKTUALIZACJA z data.table v1.8.0 wydana w lipcu 2012 r

  • Funkcja wewnętrzna sortmatch () została usunięta i zastąpiona przez chmatch () podczas dopasowywania i poziomów do x poziomów dla kolumn typu „współczynnik”. Ten wstępny krok powodował (znane) znaczące spowolnienie, gdy liczba poziomów kolumny czynnika była duża (np.> 10 000). Zaostrzył się w testach łączenia czterech takich kolumn, co wykazał Wes McKinney (autor pakietu Python Pandas). Dopasowanie 1 miliona ciągów, z których 600 000 jest unikalnych, zostało na przykład skrócone z 16 do 0,5 sekundy.

także w tym wydaniu było:

  • kolumny znakowe są teraz dozwolone w kluczach i są preferowane do uwzględnienia. data.table () i setkey () nie wymuszają już znaku na czynnik. Czynniki są nadal obsługiwane. Wdraża FR # 1493, FR # 1224 i (częściowo) FR # 951.

  • Nowe funkcje chmatch () i% chin%, szybsze wersje match () i% in% dla wektorów znaków. Wykorzystywana jest wewnętrzna pamięć podręczna ciągów R (nie jest budowana żadna tablica skrótów). Są około 4 razy szybsze niż funkcja match () na przykładzie w? Chmatch.

Od września 2013 data.table jest w wersji 1.8.10 na CRAN i pracujemy nad wersją 1.9.0. AKTUALNOŚCI są aktualizowane na żywo.


Ale jak napisałem pierwotnie, powyżej:

data.tablema na myśli scalanie szeregów czasowych . Dwa aspekty tego: i) klucze uporządkowane w wielu kolumnach , takie jak (id, datetime) ii) szybkie łączenie dominujące ( roll=TRUE) czyli ostatnia obserwacja przeniesiona do przodu.

Zatem łączenie Pandas equi dwóch kolumn znakowych jest prawdopodobnie nadal szybsze niż data.table. Ponieważ wygląda na to, że haszuje połączone dwie kolumny. data.table nie haszuje klucza, ponieważ ma na myśli dominujące uporządkowane łączenia. „Klucz” w data.table jest dosłownie po prostu porządkiem sortowania (podobnie jak indeks klastrowy w SQL; tj. Tak są uporządkowane dane w pamięci RAM). Na liście można na przykład dodać klucze dodatkowe.

Podsumowując, rażąca różnica prędkości podkreślona przez ten szczególny test dwukolumnowy z ponad 10000 unikalnych ciągów nie powinna być teraz tak zła, ponieważ znany problem został naprawiony.

Matt Dowle
źródło
6
Jeśli dostarczysz przypadek testowy dla dość dużego, realistycznego zestawu danych, z przyjemnością przeprowadzę testy porównawcze. Serdecznie zapraszamy. Właściwie nie zoptymalizowałem jeszcze kodu dla przypadku klucza łączenia liczb całkowitych (umieść to na mojej liście rzeczy do zrobienia!), Ale możesz spodziewać się znacznie lepszej wydajności niż w przypadku ciągu znaków, biorąc pod uwagę badanie tabeli skrótów w połączonej prezentacji.
Wes McKinney
22
Nie korzystam z żadnej z tych bibliotek, ale z przyjemnością widzę konstruktywną odpowiedź ze strony R w postaci Matthew Dowle'a.
SlowLearner
3
Oto niektóre wyniki Rprof pastie.org/3258362 . Wygląda na to, że 20-40% czasu spędza się na sortowaniu w zależności od typu łączenia. Będę musiał przyjrzeć się kolumnom z liczbami całkowitymi innym razem - zrobiłem problem z pandami na GitHubie, aby przypomnieć mi o optymalizacji tego przypadku ( github.com/wesm/pandas/issues/682 )
Wes McKinney
14
@AndyHayden Improvements zostały wprowadzone jakiś czas temu. Będę edytować w elementach NEWS. Wes wybrał jeden konkretny test (equi łączący dwie kolumny znaków), który dotyczył tego znanego problemu. Gdyby wybrał kolumny z liczbami całkowitymi, byłoby inaczej. A gdyby dał mi znać, zanim zaprezentuje benchmark na konferencji, mógłbym mu powiedzieć więcej o znanym problemie.
Matt Dowle,
191

Powodem, dla którego pandy są szybsze, jest to, że wymyśliłem lepszy algorytm, który jest zaimplementowany bardzo ostrożnie przy użyciu szybkiej implementacji tablicy mieszania - klib i C / Cython, aby uniknąć obciążenia interpretera Pythona dla części, których nie można wektoryzować. Algorytm został szczegółowo opisany w mojej prezentacji: Spojrzenie na projekt i rozwój pand .

Porównanie z data.tablejest właściwie trochę interesujące, ponieważ cały punkt R data.tablepolega na tym, że zawiera wstępnie obliczone indeksy dla różnych kolumn, aby przyspieszyć operacje, takie jak wybór i scalanie danych. W tym przypadku (łączenie się z bazą danych) DataFrame pand nie zawiera wstępnie obliczonych informacji, które są używane do scalania, więc tak powiem, jest to scalanie „na zimno”. Gdybym przechowywał rozłożone na czynniki wersje kluczy łączenia, łączenie byłoby znacznie szybsze - ponieważ faktoryzacja jest największym wąskim gardłem dla tego algorytmu.

Powinienem również dodać, że wewnętrzny projekt DataFrame pand jest znacznie bardziej podatny na tego rodzaju operacje niż data.frame R. (która jest tylko wewnętrzną listą tablic).

Wes McKinney
źródło
76
Oczywiście, teraz, kiedy już wszystko rozgryzłeś w Pythonie, powinno być łatwo przetłumaczyć na R;)
hadley
37
Ale dlaczego ktoś miałby kiedykolwiek chcieć? :)
ely
9
Umm ... może dlatego, że chcieliby, aby operacje na danych były szybsze w R? Zgaduję :))
lebatsnok
28
Cześć Wes! Wygląda na to, że wyniki dla zapytania data.tablebyły głównie spowodowane błędem, który został już naprawiony. Jest jakaś szansa, że ​​mógłbyś ponownie uruchomić swój test porównawczy i napisać zaktualizowany post na blogu?
Zach
6
Zach upewnij się, że to sprawdziłeś: github.com/Rdatatable/data.table/wiki/Benchmarks-:-Grouping
Merik
37

Ten temat ma dwa lata, ale wydaje się, że jest to prawdopodobne miejsce, w którym ludzie mogą wylądować, gdy szukają porównań pand i danych. Tabela

Ponieważ oba z nich ewoluowały w czasie, chcę opublikować tutaj stosunkowo nowsze porównanie (z 2014 r.) Dla zainteresowanych użytkowników: https://github.com/Rdatatable/data.table/wiki/Benchmarks-:-Grouping

Byłoby interesujące wiedzieć, czy Wes i / lub Matt (którzy, nawiasem mówiąc, są twórcami odpowiednio Pand i data.table i obaj skomentowali powyżej) również mają tutaj jakieś nowości do dodania.

-- AKTUALIZACJA --

Komentarz zamieszczony poniżej przez jangoreckiego zawiera link, który moim zdaniem jest bardzo przydatny: https://github.com/szilard/benchm-databases

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

Ten wykres przedstawia średnie czasy operacji agregacji i łączenia dla różnych technologii ( niższy = szybszy ; ostatnio zaktualizowano porównanie we wrześniu 2016 r.). To było dla mnie naprawdę pouczające.

Wracając do pytania R DT keyi R DTodwołując się do typów keyed / unkeyed R's data.table, okazuje się, że jest szybszy w tym teście porównawczym niż Pandas ( Py pandas) w Pythonie .

Merik
źródło
1
Właśnie miałem to opublikować! Dziękuję za dodanie.
Zach,
7
@Zach zobacz: github.com/szilard/benchm-databases i to też jest miłe: speakerdeck.com/szilard/ ...
jangorecki
1
@Zach cztery lata później w końcu pojawiły się nowe wyniki testów porównawczych, zobacz moją odpowiedź poniżej.
jangorecki
7

Istnieją świetne odpowiedzi, zwłaszcza autorstwa autorów obu narzędzi, o które pyta się pytanie. Odpowiedź Matta wyjaśnia przypadek zgłoszony w pytaniu, że był on spowodowany błędem, a nie algorytmem scalania. Błąd został naprawiony następnego dnia, już ponad 7 lat temu.

W mojej odpowiedzi podam aktualne terminy operacji scalania danych.table i pand. Należy pamiętać, że scalanie plyr i podstawowego R nie jest uwzględnione.

Czasy, które prezentuję, pochodzą z projektu db-benchmark , ciągle działającego, odtwarzalnego benchmarku. Uaktualnia narzędzia do najnowszych wersji i ponownie uruchamia skrypty testowe. Obsługuje wiele innych rozwiązań programowych. Jeśli interesuje Cię Spark, Dask i kilka innych, koniecznie sprawdź link.


W tej chwili ... (nadal w realizacji: jeszcze jeden rozmiar danych i 5 dodatkowych pytań)

Testujemy 2 różne rozmiary danych tabeli LHS.
Dla każdego z tych rozmiarów danych uruchamiamy 5 różnych pytań scalających.

q1: Łączenie wewnętrzne LHS RHS- małe na liczbie całkowitej
q2: Łączenie wewnętrzne LHS RHS-średnie na liczbie całkowitej
q3: Łączenie zewnętrzne LHS RHS-średnie na liczbie całkowitej
q4: Łączenie wewnętrzne LHS RHS-średnie na współczynniku (kategorialne)
q5: Łączenie wewnętrzne LHS RHS- duża na liczbie całkowitej

Stół RHS ma 3 różne rozmiary

  • small przekłada się na rozmiar LHS / 1e6
  • medium przekłada się na rozmiar LHS / 1e3
  • duży przekłada się na rozmiar LHS

We wszystkich przypadkach istnieje około 90% pasujących wierszy między LHS i RHS i nie ma duplikatów w kolumnie łączącej RHS (brak produktu kartezjańskiego).


Od teraz (uruchomiony 2 listopada 2019)

pandy 0.25.3 wydane 1 listopada 2019 r
tabela 0.12.7 (92abb70) wydane 2 listopada 2019 r.

Poniższe czasy są w sekundach, dla dwóch różnych rozmiarów danych LHS. Do kolumny pd2dtdodaje się współczynnik przechowywania pola określający, ile razy pandy są wolniejsze niż data.table.

  • 0,5 GB danych 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 danych 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
źródło
Dziękuję za aktualizację z przyszłości! Czy możesz dodać kolumnę dla implementacji data.table w języku R vs Python?
Zach
1
Myślę, że dobrze jest po prostu wejść na stronę internetową i to sprawdzić, nawet patrząc na R dt vs pandy. PyDT tak naprawdę nie był częścią oryginalnego pytania.
jangorecki