Avantages des performances du chaînage sur AND lors du filtrage d'une table de données

12

J'ai l'habitude de regrouper des tâches similaires en une seule ligne. Par exemple, si j'ai besoin de filtrer sur a, bet cdans un tableau de données, je vais les regrouper en un []avec des AND. Hier, j'ai remarqué que dans mon cas particulier, c'était des filtres de chaînage incroyablement lents et testés à la place. J'ai inclus un exemple ci-dessous.

Tout d'abord, générateur de nombres aléatoires, charge et crée un ensemble de données factices.

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

Ensuite, je définis mes méthodes. Les premières chaînes d'approche filtrent ensemble. Le second ET combine les filtres.

# 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)]
}

Ici, je vérifie qu'ils donnent les mêmes résultats.

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

Enfin, je les compare.

# 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

Créé le 2019-10-25 par le package reprex (v0.3.0)

Dans ce cas, le chaînage réduit le temps d'exécution d'environ 70%. pourquoi est-ce le cas? Je veux dire, que se passe-t-il sous le capot dans le tableau de données? Je n'ai vu aucun avertissement contre l'utilisation &, j'ai donc été surpris que la différence soit si grande. Dans les deux cas, ils évaluent les mêmes conditions, donc cela ne devrait pas faire de différence. Dans le cas ET, &est un opérateur rapide et il n'a alors qu'à filtrer la table de données une fois (c'est-à-dire en utilisant le vecteur logique résultant des ET), par opposition au filtrage trois fois dans le cas de chaînage.

Question bonus

Ce principe est-il valable pour les opérations sur les tableaux de données en général? La modularisation des tâches est-elle toujours une meilleure stratégie?

Lyngbakr
la source
1
Je répète cette observation, je me suis demandé la même chose. D'après mon expérience, l'enchaînement de la prise de vitesse est observé dans toutes les opérations générales.
JDG
9
tandis que data.tavle fait quelques optimisations pour des cas comme celui-ci (c'est à lui seul un exploit et une grande amélioration par rapport à la base R!), en général, A & B & C & D évalueront tous les N conditions logiques fois avant de combiner les résultats et le filtrage . alors qu'avec l'enchaînement, les 2e, 3e et 4e appels logiques ne sont évalués que n fois (où n <= N est le nombre de lignes restantes après chaque condition)
MichaelChirico
@MichaelChirico WOW. C'est surprenant! Je ne sais pas pourquoi, mais j'ai simplement supposé que cela fonctionnerait comme un court-circuitage C ++
duckmayr
Suite au commentaire de @ MichaelChirico, vous pouvez faire une baseobservation similaire avec des vecteurs en procédant comme suit: chain_vec <- function() { x <- which(a < .001); x[which(b[x] > .999)] }et and_vec <- function() { which(a < .001 & b > .999) }. (où aet bsont des vecteurs de la même longueur runif- j'ai utilisé n = 1e7pour ces coupures).
ClancyStats
@MichaelChirico Ah, je vois. Donc, la grande différence est qu'à chaque étape de la chaîne, le tableau de données est sensiblement plus petit et donc plus rapide pour évaluer la condition et filtrer? Ça a du sens. Merci pour vos idées!
Lyngbakr

Réponses:

8

Généralement, la réponse a été donnée dans les commentaires: la "méthode de chaînage" data.tableest plus rapide dans ce cas que la "méthode de anding" car le chaînage exécute les conditions les unes après les autres. Comme chaque étape réduit la taille de la, data.tableil y a moins à évaluer pour la suivante. "Anding" évalue à chaque fois les conditions pour les données en taille réelle.

Nous pouvons le démontrer avec un exemple: lorsque les étapes individuelles ne diminuent PAS la taille de la data.table(c'est-à-dire que les conditions à vérifier sont les mêmes pour les deux approches):

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)]
}

En utilisant les mêmes données mais le benchpackage, qui vérifie automatiquement si les résultats sont identiques:

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

Comme vous pouvez le voir ici, l' approche anding est 2,43 fois plus rapide dans ce cas . Cela signifie que l' enchaînement ajoute en fait des frais généraux , ce qui suggère que l'anding devrait être plus rapide. SAUF si les conditions réduisent la taille de l'data.table étape par étape. Théoriquement, l'approche de chaînage pourrait même être plus lente (même en laissant de côté les frais généraux), à savoir si une condition augmenterait la taille des données. Mais pratiquement je pense que ce n'est pas possible car le recyclage des vecteurs logiques n'est pas autorisé data.table. Je pense que cela répond à votre question bonus.

A titre de comparaison, des fonctions originales sur ma machine avec 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
la source