r - Quel est le but de la définition d'une clé dans data.table?




(2)

J'utilise data.table et il y a beaucoup de fonctions qui me demandent de définir une clé (par exemple X[Y] ). En tant que tel, je souhaite comprendre ce qu'une clé fait pour définir correctement les clés dans mes tableaux de données.

Une source que j'ai lue était ?setkey .

setkey() trie un data.table et le marque comme trié. Les colonnes triées sont la clé. La clé peut être n'importe quelle colonne dans n'importe quel ordre. Les colonnes sont triées dans l'ordre croissant toujours. La table est modifiée par référence. Aucune copie n'est faite du tout, autre qu'une mémoire de travail temporaire aussi grande qu'une colonne.

Mon truc à retenir ici est qu'une clé "trierait" le data.table, résultant en un effet très similaire à order() . Cependant, cela n'explique pas le but d'avoir une clé.

La FAQ data.table 3.2 et 3.3 explique:

3.2 Je n'ai pas de clé sur une grande table, mais le regroupement est toujours très rapide. Pourquoi donc?

data.table utilise le tri radix. Ceci est nettement plus rapide que d'autres algorithmes de tri. La base est spécifiquement pour les entiers, voir ?base::sort.list(x,method="radix") . C'est aussi une raison pour laquelle setkey() est rapide. Quand aucune clé n'est définie, ou que nous groupons dans un ordre différent de celui de la clé, nous l'appelons ad hoc par.

3.3 Pourquoi le regroupement par colonne dans la clé est-il plus rapide qu'un ad hoc?

Parce que chaque groupe est contigu en RAM, minimisant ainsi les extractions de pages, et la mémoire peut être copiée en masse ( memcpy en C) plutôt qu'en boucle en C.

A partir de là, j'imagine que la définition d'une clé permet en quelque sorte à R d'utiliser le "tri radix" par rapport à d'autres algorithmes, et c'est pourquoi c'est plus rapide.

Le guide de démarrage rapide de 10 minutes a également un guide sur les clés.

  1. Clés

Commençons par considérer data.frame, en particulier les noms de famille (ou en anglais, les noms de lignes). Autrement dit, les noms multiples appartenant à une seule ligne. Les noms multiples appartenant à la seule rangée? Ce n'est pas ce à quoi nous sommes habitués dans un data.frame. Nous savons que chaque rangée a au plus un nom. Une personne a au moins deux noms, un premier nom et un deuxième nom. C'est utile pour organiser un annuaire téléphonique, par exemple, qui est trié par nom de famille, puis par nom. Cependant, chaque ligne d'un data.frame ne peut avoir qu'un seul nom.

Une clé se compose d'une ou de plusieurs colonnes de noms, qui peuvent être un entier, un facteur, un caractère ou une autre classe, et pas simplement un caractère. De plus, les lignes sont triées par la clé. Par conséquent, une table de données peut avoir au plus une clé, car elle ne peut pas être triée de plusieurs manières.

L'unicité n'est pas appliquée, c'est-à-dire que les valeurs clés en double sont autorisées. Puisque les lignes sont triées par la clé, tous les doublons dans la clé apparaîtront consécutivement

L'annuaire téléphonique a été utile pour comprendre ce qu'est une clé, mais il semble qu'une clé ne soit pas différente lorsqu'on la compare à une colonne de facteur. De plus, cela n'explique pas pourquoi une clé est nécessaire (en particulier pour utiliser certaines fonctions) et comment choisir la colonne à définir comme clé. En outre, il semble que dans une table de données avec l'heure comme une colonne, la définition de toute autre colonne serait probablement gâcher la colonne de temps, ce qui rend encore plus confus car je ne sais pas si je peux définir une autre colonne comme clé. Quelqu'un peut-il m'éclairer s'il vous plaît?


Une clé est essentiellement un index dans un ensemble de données, ce qui permet des opérations de tri, de filtrage et de jointure très rapides et efficaces. Ce sont probablement les meilleures raisons d'utiliser des tables de données à la place des trames de données (la syntaxe pour l'utilisation des tables de données est également beaucoup plus conviviale, mais cela n'a rien à voir avec les clés).

Si vous ne comprenez pas les index, considérez ceci: un annuaire téléphonique est "indexé" par son nom. Donc, si je veux rechercher le numéro de téléphone de quelqu'un, c'est assez simple. Mais supposons que je veuille faire une recherche par numéro de téléphone (par exemple, cherchez qui a un numéro de téléphone particulier)? À moins que je puisse «ré-indexer» le répertoire téléphonique par numéro de téléphone, cela prendra beaucoup de temps.

Prenons l'exemple suivant: supposons que j'ai une table, ZIP, de tous les codes postaux aux États-Unis (> 33 000) avec les informations associées (ville, état, population, revenu médian, etc.). Si je veux rechercher les informations pour un code postal spécifique, la recherche (filtre) est environ 1000 fois plus rapide si je setkey(ZIP,zipcode) premier.

Un autre avantage a à voir avec les jointures. Supposons que vous ayez une liste de personnes et leurs codes postaux dans une table de données (appelez-le "PPL"), et je veux ajouter des informations de la table ZIP (par exemple, ville, état, et ainsi de suite). Le code suivant le fera:

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

C'est une "jointure" dans le sens où je joins l'information de 2 tables basées dans un champ commun (code postal). Les jointures de ce type sur de très grandes tables sont extrêmement lentes avec les trames de données et extrêmement rapides avec les tables de données. Dans un exemple concret, j'ai dû faire plus de 20 000 jointures comme ça sur une table complète de codes postaux. Avec les tables de données, le script a pris environ 20 minutes. courir. Je n'ai même pas essayé avec des trames de données car cela aurait pris plus de 2 semaines.

À mon humble avis, vous ne devriez pas simplement lire mais étudier la FAQ et le matériel d'introduction. C'est plus facile à saisir si vous avez un problème réel à résoudre.

[Réponse au commentaire de @ Frank]

Re: tri vs indexation - Basé sur la réponse à cette question , il semble que setkey(...) réorganise en fait les colonnes dans la table (par exemple, un tri physique), et ne crée pas un index dans la base de données sens. Cela a des implications pratiques: d'une part, si vous définissez la clé dans une table avec setkey(...) puis que vous modifiez l'une des valeurs de la colonne key, data.table déclare simplement que la table n'est plus triée (par désactiver l'attribut sorted ); il ne réindexe pas dynamiquement pour maintenir l'ordre de tri correct (comme cela arriverait dans une base de données). En outre, "supprimer la clé" en utilisant setky(DT,NULL) ne restaure pas la table à son ordre original, non trié.

Re: filtre vs jointure - la différence pratique est que le filtrage extrait un sous-ensemble d'un seul ensemble de données, tandis que joint combine des données provenant de deux ensembles de données basés sur un champ commun. Il existe plusieurs types de jointure (interne, externe, gauche). L'exemple ci-dessus est une jointure interne (seuls les enregistrements avec des clés communes aux deux tables sont renvoyés), ce qui présente de nombreuses similitudes avec le filtrage.


Mise à jour mineure: Veuillez également vous reporter aux nouvelles vignettes HTML . Ce numéro met en évidence les autres vignettes que nous prévoyons.

J'ai mis à jour cette réponse à nouveau (février 2016) à la lumière de la nouvelle fonctionnalité on= qui permet également des jointures ad-hoc . Voir l'historique pour les réponses antérieures (périmées).

Que fait exactement setkey(DT, a, b) ?

Il fait deux choses:

  1. réorganise les lignes du data.table DT par la ou les colonnes fournies ( a , b ) par référence , toujours dans l' ordre croissant .
  2. marque ces colonnes comme des colonnes clés en définissant un attribut appelé sorted sur DT .

La réorganisation est à la fois rapide (en raison du tri interne de la base de données de data.table ) et efficace en termes de mémoire (une seule colonne supplémentaire de type double est allouée).

Quand est-ce que setkey() requis?

Pour les opérations de regroupement, setkey() n'a jamais été une exigence absolue. Autrement dit, nous pouvons effectuer un cold-by ou adhoc-by .

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

Cependant, avant v1.9.6 , les jointures de la forme x[i] requéraient que la key soit mise sur x . Avec le nouvel argument on= de v1.9.6 + , ce n'est plus vrai, et la définition de clés n'est donc pas non plus une exigence absolue ici.

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

Notez que l'argument on on= peut être explicitement spécifié même pour les jointures par keyed .

La seule opération nécessitant une key à définir absolument est la fonction foverlaps() . Mais nous travaillons sur d'autres fonctionnalités qui, une fois terminées, supprimeraient cette exigence.

  • Alors, quelle est la raison de la mise on= œuvre on= argument?

    Il y a plusieurs raisons.

    1. Il permet de distinguer clairement l'opération comme une opération impliquant deux tables de données . Juste faire X[Y] ne le distingue pas non plus, bien qu'il puisse être clair en nommant les variables de manière appropriée.

    2. Il permet également de comprendre les colonnes sur lesquelles la jointure / sous-ensemble est effectuée immédiatement en regardant cette ligne de code (et ne pas avoir à remonter à la ligne setkey() correspondante).

    3. Dans les opérations où les colonnes sont ajoutées ou mises à jour par référence , on= opérations on on= sont beaucoup plus performantes car elles n'ont pas besoin de toute la table data.table pour être réorganisées juste pour ajouter / mettre à jour les colonnes. Par exemple,

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

      Dans le second cas, nous n'avons pas eu à réorganiser. Il ne s'agit pas de calculer l'ordre qui prend du temps, mais de réorganiser physiquement la table data.table en RAM, et en l'évitant, nous conservons l'ordre d'origine, et il est également performant.

    4. Même dans le cas contraire, à moins que vous n'effectuiez des jointures de façon répétitive, il ne devrait pas y avoir de différence de performance notable entre une jointure clée et une jointure ad-hoc .

Cela conduit à la question: quel avantage a la manipulation d'une table de données?

  • Y a-t-il un avantage à entrer une table data.table?

    L' indexation d' un fichier data.table le réorganise physiquement en fonction de ces colonnes dans la RAM. Le calcul de la commande n'est généralement pas la partie qui prend du temps, mais plutôt la réorganisation elle-même. Cependant, une fois que nous avons trié les données en RAM, les lignes appartenant au même groupe sont toutes contiguës dans la RAM, et sont donc très efficaces dans le cache. C'est le tri qui accélère les opérations sur data.tables avec clé.

    Il est donc essentiel de déterminer si le temps passé à réorganiser l'ensemble de data.table vaut la peine d'effectuer une jointure / agrégation efficace en cache. Habituellement, à moins que des opérations répétitives de regroupement / jointure soient effectuées sur le même data.table avec clé , il ne devrait pas y avoir de différence notable.

Dans la plupart des cas, il ne devrait donc plus être nécessaire de définir des clés. Nous vous recommandons d'utiliser on= mesure du possible, à moins que la définition de la clé n'améliore considérablement les performances que vous souhaitez exploiter.

Question: A votre avis, quelle serait la performance par rapport à une jointure par clé , si vous utilisez setorder() pour réorganiser le data.table et utiliser on= ? Si vous avez suivi jusqu'à présent, vous devriez être capable de le comprendre :-).







data.table