Korzyści z wydajności łączenia łańcuchowego nad ANDingiem podczas filtrowania tabeli danych

12

Mam w zwyczaju zlepianie podobnych zadań w jedną linię. Na przykład, jeśli trzeba filtrować a, bi cw tabeli danych, będę je razem w jednym []z AND. Wczoraj zauważyłem, że w moim konkretnym przypadku było to niezwykle wolne i zamiast tego przetestowałem filtry łańcuchowe. Podałem przykład poniżej.

Najpierw zaszczepiam generator liczb losowych, i tworzę zestaw danych.

# Set RNG seed
set.seed(-1)

# Load libraries
library(data.table)

# Create data table
dt <- data.table(a = sample(1:1000, 1e7, replace = TRUE),
                 b = sample(1:1000, 1e7, replace = TRUE),
                 c = sample(1:1000, 1e7, replace = TRUE),
                 d = runif(1e7))

Następnie określam swoje metody. Łańcuchy pierwszego podejścia filtrują razem. Drugi AND razem filtruje.

# Chaining method
chain_filter <- function(){
  dt[a %between% c(1, 10)
     ][b %between% c(100, 110)
       ][c %between% c(750, 760)]
}

# Anding method
and_filter <- function(){
  dt[a %between% c(1, 10) & b %between% c(100, 110) & c %between% c(750, 760)]
}

Tutaj sprawdzam, że dają te same wyniki.

# Check both give same result
identical(chain_filter(), and_filter())
#> [1] TRUE

Wreszcie dokonuję ich analizy porównawczej.

# Benchmark
microbenchmark::microbenchmark(chain_filter(), and_filter())
#> Unit: milliseconds
#>            expr      min        lq      mean    median        uq       max
#>  chain_filter() 25.17734  31.24489  39.44092  37.53919  43.51588  78.12492
#>    and_filter() 92.66411 112.06136 130.92834 127.64009 149.17320 206.61777
#>  neval cld
#>    100  a 
#>    100   b

Utworzono 25.10.2019 przez pakiet reprezentx (v0.3.0)

W takim przypadku tworzenie łańcuchów skraca czas działania o około 70%. Dlaczego tak jest? Mam na myśli, co się dzieje pod maską w tabeli danych? Nie widziałem żadnych ostrzeżeń przed używaniem &, więc byłem zaskoczony, że różnica jest tak duża. W obu przypadkach oceniają te same warunki, więc nie powinno być różnicy. W przypadku AND &jest szybkim operatorem, a następnie musi tylko raz przefiltrować tabelę danych (tj. Przy użyciu wektora logicznego wynikającego z AND), a nie trzykrotnie w przypadku łańcucha.

Pytanie bonusowe

Czy zasada ta dotyczy ogólnie operacji na tabelach danych? Czy zadania modularne są zawsze lepszą strategią?

Lyngbakr
źródło
1
Zrobiłem to spostrzeżenie, zastanawiałem się nad tym samym. Z mojego doświadczenia wynika, że ​​zwiększenie szybkości łączenia łańcuchów obserwuje się w operacjach ogólnych.
JDG
9
podczas gdy data.tavle wykonuje pewne optymalizacje dla takich przypadków (to samo jest wyczyn i świetna poprawa w porównaniu z podstawową R!), ogólnie A, B, C i D ocenią wszystkie N warunków logicznych przed połączeniem wyników i filtrowaniem . mając na uwadze, że przy łączeniu 2., 3. i 4. połączenia logiczne są oceniane tylko n razy (gdzie n <= N to liczba wierszy pozostałych po każdym warunku)
MichaelChirico
@MichaelChirico WOW. To zaskakujące! Nie wiem dlaczego, ale po prostu założyłem, że zadziała jak zwieranie C ++
duckmayr
Po komentarzu @ MichaelChirico możesz dokonać podobnej baseobserwacji za pomocą wektorów, wykonując następujące czynności: chain_vec <- function() { x <- which(a < .001); x[which(b[x] > .999)] }i and_vec <- function() { which(a < .001 & b > .999) }. (gdzie ai bsą wektory o tej samej długości od runif- użyłem n = 1e7dla tych wartości granicznych).
ClancyStats
@MichaelChirico Ach, rozumiem. Tak duża różnica polega na tym, że na każdym etapie łańcucha tabela danych jest znacznie mniejsza, a zatem szybsza ocena stanu i włączenie filtra? To ma sens. Dzięki za wgląd!
Lyngbakr

Odpowiedzi:

8

Przeważnie odpowiedź została podana w komentarzach aleady: „metoda łączenia” data.tablejest w tym przypadku szybsza niż „metoda łączenia”, ponieważ łańcuch łączy warunki jeden po drugim. Ponieważ każdy krok zmniejsza rozmiar, data.tablejest mniej do oceny na następny. „Anding” każdorazowo ocenia warunki dla danych w pełnym rozmiarze.

Możemy to zademonstrować na przykładzie: gdy poszczególne kroki NIE zmniejszają rozmiaru data.table(tj. Warunki do sprawdzenia są takie same dla obu podejść):

chain_filter <- function(){
  dt[a %between% c(1, 1000) # runs evaluation but does not filter out cases
     ][b %between% c(1, 1000)
       ][c %between% c(750, 760)]
}

# Anding method
and_filter <- function(){
  dt[a %between% c(1, 1000) & b %between% c(1, 1000) & c %between% c(750, 760)]
}

Używając tych samych danych, ale benchpakietu, który automatycznie sprawdza, czy wyniki są identyczne:

res <- bench::mark(
  chain = chain_filter(),
  and = and_filter()
)
summary(res)
#> # A tibble: 2 x 6
#>   expression      min   median `itr/sec` mem_alloc `gc/sec`
#>   <bch:expr> <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl>
#> 1 chain         299ms    307ms      3.26     691MB     9.78
#> 2 and           123ms    142ms      7.18     231MB     5.39
summary(res, relative = TRUE)
#> # A tibble: 2 x 6
#>   expression   min median `itr/sec` mem_alloc `gc/sec`
#>   <bch:expr> <dbl>  <dbl>     <dbl>     <dbl>    <dbl>
#> 1 chain       2.43   2.16      1         2.99     1.82
#> 2 and         1      1         2.20      1        1

Jak widać tutaj, podejście anding jest w tym przypadku 2,43 razy szybsze . Oznacza to, że łączenie w łańcuchy faktycznie dodaje trochę narzutu , co sugeruje, że zwykle andinging powinien być szybszy. Z WYJĄTKIEM, jeśli warunki zmniejszają rozmiardata.table krok po kroku. Teoretycznie podejście łańcuchowe może być nawet wolniejsze (nawet z pominięciem kosztów ogólnych), a mianowicie, jeśli warunek zwiększyłby rozmiar danych. Ale praktycznie myślę, że nie jest to możliwe, ponieważ recykling wektorów logicznych nie jest dozwolony data.table. Myślę, że to odpowiada na twoje dodatkowe pytanie.

Dla porównania, oryginalne funkcje na moim komputerze z bench:

res <- bench::mark(
  chain = chain_filter_original(),
  and = and_filter_original()
)
summary(res)
#> # A tibble: 2 x 6
#>   expression      min   median `itr/sec` mem_alloc `gc/sec`
#>   <bch:expr> <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl>
#> 1 chain        29.6ms   30.2ms     28.5     79.5MB     7.60
#> 2 and         125.5ms  136.7ms      7.32   228.9MB     7.32
summary(res, relative = TRUE)
#> # A tibble: 2 x 6
#>   expression   min median `itr/sec` mem_alloc `gc/sec`
#>   <bch:expr> <dbl>  <dbl>     <dbl>     <dbl>    <dbl>
#> 1 chain       1      1         3.89      1        1.04
#> 2 and         4.25   4.52      1         2.88     1
JBGruber
źródło