Jaki jest cel ustawiania klucza w data.table?


113

Używam data.table i jest wiele funkcji, które wymagają ustawienia klucza (np X[Y].). W związku z tym chciałbym zrozumieć, co robi klucz, aby poprawnie ustawić klucze w moich tabelach danych.


Jednym ze źródeł, które przeczytałem, było ?setkey.

setkey()sortuje a data.tablei zaznacza jako posortowane. Kluczem są posortowane kolumny. Kluczem mogą być dowolne kolumny w dowolnej kolejności. Kolumny są zawsze sortowane rosnąco. Tabela jest zmieniana przez odniesienie. W ogóle nie jest wykonywana żadna kopia, poza tymczasową pamięcią roboczą o wielkości jednej kolumny.

Moim wnioskiem jest to, że klucz „posortowałby” plik data.table, dając bardzo podobny efekt do order(). Nie wyjaśnia to jednak celu posiadania klucza.


W sekcji FAQ 3.2 i 3.3 tabeli danych wyjaśniono:

3.2 Nie mam klucza na dużym stole, ale grupowanie jest nadal bardzo szybkie. Dlaczego?

data.table korzysta z sortowania radix. Jest to znacznie szybsze niż inne algorytmy sortowania. Radix dotyczy tylko liczb całkowitych, zobacz ?base::sort.list(x,method="radix"). Jest to również jeden z powodów, dla których setkey()jest szybki. Gdy żaden klucz nie jest ustawiony lub grupujemy w innej kolejności niż klucz, nazywamy to ad hoc według.

3.3 Dlaczego grupowanie według kolumn w kluczu jest szybsze niż ad hoc przez?

Ponieważ każda grupa jest ciągła w pamięci RAM, minimalizując w ten sposób pobieranie stron, a pamięć może być kopiowana zbiorczo ( memcpyw C), a nie zapętlana w C.

Stąd wydaje mi się, że ustawienie klucza w jakiś sposób pozwala R na użycie „sortowania radix” w stosunku do innych algorytmów i dlatego jest szybsze.


10-minutowa skrócona instrukcja obsługi zawiera również instrukcje dotyczące klawiszy.

  1. Klucze

Zacznijmy od rozważenia data.frame, konkretnie nazw wierszy (lub w języku angielskim, nazw wierszy). Oznacza to, że wiele nazw należących do jednego wiersza. Wiele nazw należących do jednego wiersza? To nie jest to, do czego jesteśmy przyzwyczajeni w data.frame. Wiemy, że każdy wiersz ma co najwyżej jedną nazwę. Osoba ma co najmniej dwa imiona, pierwsze imię i drugie imię. Jest to przydatne na przykład do zorganizowania książki telefonicznej, która jest sortowana według nazwiska, a następnie pierwszego imienia. Jednak każdy wiersz w data.frame może mieć tylko jedną nazwę.

Klucz składa się z jednej lub więcej kolumn nazw wierszy, które mogą być liczbą całkowitą, współczynnikiem, znakiem lub inną klasą, a nie zwykłym znakiem. Ponadto wiersze są sortowane według klucza. Dlatego data.table może mieć co najwyżej jeden klucz, ponieważ nie można jej sortować na więcej niż jeden sposób.

Unikalność nie jest wymuszana, tj. Dozwolone są zduplikowane wartości kluczy. Ponieważ wiersze są sortowane według klucza, wszelkie duplikaty w kluczu pojawią się kolejno

Książka telefoniczna była pomocna w zrozumieniu, czym jest klucz, ale wydaje się, że klucz nie różni się od tego, który ma kolumnę czynnikową. Ponadto nie wyjaśnia, dlaczego potrzebny jest klucz (zwłaszcza do korzystania z niektórych funkcji) i jak wybrać kolumnę, która ma być kluczem. Wydaje się również, że w tabeli data.table z czasem jako kolumną, ustawienie dowolnej innej kolumny jako klucza prawdopodobnie również zepsułoby kolumnę czasu, co czyni ją jeszcze bardziej zagmatwaną, ponieważ nie wiem, czy wolno mi ustawić dowolną inną kolumnę jako klucz. Czy ktoś może mnie oświecić, proszę?


"Wydaje mi się, że ustawienie klucza w jakiś sposób pozwala R na użycie" sortowania radix "zamiast innych algorytmów" - w ogóle nie mam tego z pomocy. Czytam, że ustawianie rodzajów kluczy według klucza. Możesz przeprowadzić sortowanie „ad hoc” według kolumn innych niż klucz i jest szybkie, ale nie tak szybkie, jak w przypadku wcześniejszego sortowania.
Ari B. Friedman

Myślę, że przy wybieraniu wierszy wyszukiwanie binarne jest szybsze niż skanowanie wektorowe. Nie jestem informatykiem, więc nie wiem, co to właściwie oznacza. Oprócz często zadawanych pytań zobacz wprowadzenie .
Frank

Odpowiedzi:


125

Niewielka aktualizacja: zapoznaj się również z nowymi winietami HTML . W tym numerze wyróżniono inne winiety, które planujemy.


Zaktualizowałem tę odpowiedź ponownie (luty 2016) w świetle nowej on=funkcji, która umożliwia również połączenia ad-hoc . Zobacz historię wcześniejszych (nieaktualnych) odpowiedzi.

Co dokładnie robi setkey(DT, a, b)?

Robi dwie rzeczy:

  1. przestawia rzędy data.table DT przez kolumnę (-y), pod warunkiem ( , b ) , przez odniesienie , zawsze zwiększa zamówienia.
  2. oznacza te kolumny jako kolumny kluczowe , ustawiając atrybut wywoływany sorteddo DT.

Zmiana kolejności jest zarówno szybka (ze względu na wewnętrzne sortowanie radix w data.table ), jak i wydajna pamięć ( przydzielana jest tylko jedna dodatkowa kolumna typu double ).

Kiedy jest to setkey()wymagane?

W przypadku operacji grupowych setkey()nigdy nie było wymogiem bezwzględnym. Oznacza to, że możemy przeprowadzić przeziębienie lub doraźnie .

## "cold" by
require(data.table)
DT <- data.table(x=rep(1:5, each=2), y=1:10)
DT[, mean(y), by=x] # no key is set, order of groups preserved in result

Jednak przed v1.9.6dołączeniem formularza x[i]wymagane keybyło włączenie x. Wraz z nowym on=argumentem z wersji 1.9.6 + to już nie jest prawdą, a zatem ustawianie kluczy również nie jest tutaj bezwzględnym wymogiem.

## joins using < v1.9.6 
setkey(X, a) # absolutely required
setkey(Y, a) # not absolutely required as long as 'a' is the first column
X[Y]

## joins using v1.9.6+
X[Y, on="a"]
# or if the column names are x_a and y_a respectively
X[Y, on=c("x_a" = "y_a")]

Zauważ, że on=argument można jawnie określić nawet dla keyedzłączeń.

Jedyną operacją, która wymaga keyabsolutnego ustawienia, jest funkcja foverlaps () . Ale pracujemy nad kilkoma innymi funkcjami, które po zakończeniu usuwają ten wymóg.

  • Więc jaki jest powód implementacji on=argumentacji?

    Jest kilka powodów.

    1. Pozwala to wyraźnie rozróżnić operację jako operację obejmującą dwie tabele danych . Samo wykonanie X[Y]tego również nie rozróżnia, chociaż można to wyjaśnić, odpowiednio nazywając zmienne.

    2. Pozwala również zrozumieć kolumny, w których wykonywane jest łączenie / podzbiór natychmiast, patrząc na tę linię kodu (bez konieczności śledzenia wstecznego do odpowiedniej setkey()linii).

    3. W operacjach, w których kolumny są dodawane lub aktualizowane przez odniesienie , on=operacje są znacznie wydajniejsze, ponieważ nie wymagają zmiany kolejności całej tabeli data.table tylko w celu dodania / aktualizacji kolumn. Na przykład,

      ## compare 
      setkey(X, a, b) # why physically reorder X to just add/update a column?
      X[Y, col := i.val]
      
      ## to
      X[Y, col := i.val, on=c("a", "b")]

      W drugim przypadku nie musieliśmy ponownie zamawiać. Nie obliczanie kolejności jest czasochłonne, ale fizyczna zmiana kolejności danych. Tabela w pamięci RAM, a unikając tego, zachowujemy oryginalną kolejność, a także jest wydajna.

    4. Nawet w przeciwnym razie, o ile nie wykonujesz połączeń powtarzalnie, nie powinno być zauważalnej różnicy w wydajności między połączeniami kluczowanymi i ad-hoc .

To prowadzi do pytania, jaką korzyść ma już kluczowanie data.table ?

  • Czy istnieje korzyści z kluczowania data.table?

    Wprowadzenie klucza do tabeli danych powoduje fizyczną zmianę jej kolejności na podstawie tych kolumn w pamięci RAM. Obliczanie kolejności nie jest zwykle czasochłonną częścią, a raczej samą zmianą kolejności . Jednak po posortowaniu danych w pamięci RAM wiersze należące do tej samej grupy są wszystkie sąsiadujące w pamięci RAM, a zatem są bardzo wydajne w pamięci podręcznej. To sortowanie przyspiesza operacje na kluczowanych danych. Tabele.

    Dlatego ważne jest, aby dowiedzieć się, czy czas spędzony na ponownym uporządkowaniu całej tabeli danych jest warty czasu, aby wykonać łączenie / agregację wydajne dla pamięci podręcznej. Zwykle nie powinno być zauważalnej różnicy , chyba że są wykonywane powtarzające się operacje grupowania / łączenia na tych samych danych z kluczem. Tabela.

Dlatego w większości przypadków nie powinno już być potrzeby ustawiania kluczy. Zalecamy używanie on=wszędzie tam, gdzie jest to możliwe, chyba że ustawienie klucza daje radykalną poprawę wydajności, którą chcesz wykorzystać.

Pytanie: Jak myślisz, jaka byłaby wydajność w porównaniu do sprzężenia kluczowanego , jeśli użyjesz setorder()do zmiany kolejności data.table i użycia on=? Jeśli postępowałeś do tej pory, powinieneś być w stanie to rozgryźć :-).


3
Fajne dzięki! Do tej pory nie zastanawiałem się, co właściwie oznacza „wyszukiwanie binarne”, ani naprawdę nie rozumiałem, dlaczego zostało użyte zamiast hasha.
Frank

@Arun, jest DT[J(1e4:1e5)]naprawdę odpowiednikiem DF[DF$x > 1e4 & DF$x < 1e5, ]? Czy możesz mi wskazać, co Jto znaczy? Również to wyszukiwanie nie zwróci żadnych wierszy, ponieważ sample(1e4, 1e7, TRUE)nie obejmuje liczb powyżej 1e4.
akwarium

@fishtank, w tym przypadku powinno być >=i <=- naprawione. J(i .) są aliasami list(tj. są równoważne). Wewnętrznie, gdy ijest listą, jest konwertowane do postaci data.table, po której wyszukiwanie binarne jest używane do obliczania indeksów wierszy. Naprawiono, 1e4aby 1e5uniknąć nieporozumień. Dzięki za wykrycie. Zauważ, że możemy on=teraz bezpośrednio użyć argumentu do wykonania podzbiorów binarnych zamiast ustawiania klucza. Przeczytaj więcej na temat nowych winiet HTML . Miej oko na tę stronę, aby zobaczyć winiety do dołączeń.
Arun

może to mogłoby przejść do dokładniejszej aktualizacji? sekcja „w razie potrzeby” wydaje się nieaktualna, np.
MichaelChirico,

Jaka funkcja informuje o używanym kluczu?
skan

20

Klucz jest w zasadzie indeksem zbioru danych, który umożliwia bardzo szybkie i wydajne operacje sortowania, filtrowania i łączenia. Są to prawdopodobnie najlepsze powody, aby używać tabel danych zamiast ramek danych (składnia korzystania z tabel danych jest również znacznie bardziej przyjazna dla użytkownika, ale nie ma to nic wspólnego z kluczami).

Jeśli nie rozumiesz indeksów, zastanów się nad tym: książka telefoniczna jest „indeksowana” według nazwy. Więc jeśli chcę sprawdzić czyjś numer telefonu, jest to całkiem proste. Ale przypuśćmy, że chcę wyszukiwać według numeru telefonu (np. Sprawdzić, kto ma określony numer telefonu)? Jeśli nie uda mi się „ponownie zindeksować” książki telefonicznej według numeru telefonu, zajmie to bardzo dużo czasu.

Rozważmy następujący przykład: załóżmy, że mam tabelę ZIP ze wszystkimi kodami pocztowymi w Stanach Zjednoczonych (> 33 000) wraz z powiązanymi informacjami (miasto, stan, ludność, średni dochód itp.). Jeśli chcę wyszukać informacje dotyczące określonego kodu pocztowego, wyszukiwanie (filtr) jest około 1000 razy szybsze, jeśli setkey(ZIP,zipcode)najpierw.

Kolejna korzyść wiąże się z połączeniami. Załóżmy, że masz listę osób i ich kody pocztowe w tabeli danych (nazwij to „PPL”) i chcę dołączyć informacje z tabeli ZIP (np. Miasto, stan itp.). Poniższy kod zrobi to:

setkey(ZIP,zipcode)
setkey(PPL,zipcode)
full.info <- PPL[ZIP, nomatch=F]

Jest to „złączenie” w tym sensie, że łączę informacje z 2 tabel opartych na wspólnym polu (kod pocztowy). Takie sprzężenia w bardzo dużych tabelach są bardzo wolne w przypadku ramek danych i niezwykle szybkie w przypadku tabel danych. W prawdziwym przykładzie musiałem wykonać więcej niż 20 000 takich połączeń na pełnej tabeli kodów pocztowych. W przypadku tabel danych skrypt trwał około 20 minut. biegać. Nawet nie próbowałem tego z ramkami danych, ponieważ zajęłoby to więcej niż 2 tygodnie.

IMHO powinieneś nie tylko czytać, ale przestudiować FAQ i materiał wprowadzający. Łatwiej jest pojąć, jeśli masz rzeczywisty problem, aby to zastosować.

[Odpowiedź na komentarz @ Frank]

Odp .: sortowanie a indeksowanie - na podstawie odpowiedzi na to pytanie wydaje się, że setkey(...)faktycznie zmienia kolejność kolumn w tabeli (np. Sortowanie fizyczne) i nie tworzy indeksu w sensie bazy danych. Ma to pewne praktyczne implikacje: po pierwsze, jeśli ustawisz klucz w tabeli za pomocą, setkey(...)a następnie zmienisz dowolną z wartości w kolumnie klucza, data.table po prostu deklaruje, że tabela nie jest już sortowana (wyłączając sortedatrybut); robi nie dynamicznie re-index do utrzymania prawidłowego porządek (jak stałoby się w bazie danych). Również „wyjęciu kluczyka” używając setky(DT,NULL)ma nie przywrócić stół do jej pierwotnego, niesegregowanych kolejności.

Re: filter a join - praktyczna różnica polega na tym, że filtrowanie wyodrębnia podzbiór z pojedynczego zbioru danych, podczas gdy łączenie łączy dane z dwóch zbiorów danych na podstawie wspólnego pola. Istnieje wiele różnych rodzajów złączeń (wewnętrzne, zewnętrzne, lewe). Powyższy przykład to sprzężenie wewnętrzne (zwracane są tylko rekordy z kluczami wspólnymi dla obu tabel), które ma wiele podobieństw do filtrowania.


1
+1. Jeśli chodzi o twoje pierwsze zdanie ... jest już uporządkowane, prawda? I czy złączenie nie jest specjalnym przypadkiem filtru (lub operacją, w której filtrowanie jest pierwszym krokiem)? Wydaje się, że „lepsze filtrowanie” podsumowuje całą korzyść.
Frank

1
Albo lepsze skanowanie, jak przypuszczam.
Wet Feet

1
@jlhoward Thanks. Wcześniej uważałem, że sortowanie nie należy do korzyści wynikających z ustawienia klucza (ponieważ jeśli chcesz sortować, powinieneś po prostu sortować), a także to setkeyfaktycznie powoduje nieodwracalną zmianę kolejności wierszy. Jeśli jest to tylko do celów wyświetlania, to w jaki sposób mogę wydrukować pierwsze dziesięć wierszy zgodnie z „prawdziwą” kolejnością (którą widziałem przed setkey)? Jestem prawie pewien, że setkey(DT,NULL)tego nie robi ... (cd.)
Frank,

... (cd.) Poza tym nie patrzyłem na kod pakietu, ale aby dołączyć X[Y,...], musisz „przefiltrować” wiersze X za pomocą klucza. To prawda, że ​​po tym zdarzają się inne rzeczy (kolumny Y są udostępniane i istnieje domniemana opcja by-without-by), ale nadal nie uważam tego za koncepcyjnie odrębną korzyść. Wydaje mi się, że twoja odpowiedź jest podana w kategoriach operacji, które możesz chcieć wykonać, gdzie rozróżnienie może być pomocne.
Frank

1
@Frank - setkey(DT,NULL)usuwa klucz, ale nie wpływa na porządek sortowania. Postawione pytanie o to tutaj . Zobaczmy.
jlhoward
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.