Quel est le but de définir une clé dans data.table?

Question

Je suis d'utilisation des données.table et il y a beaucoup de fonctions qui m'obligent à définir une clé (par exemple, X[Y] ). En tant que tel, je veux comprendre ce qu'est une clé afin de définir correctement les touches dans mes tableaux de données.

---

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

setkey() sortes, une data.table et le marque comme triés. Les colonnes triées sont la clé. La clé peut être de toutes les colonnes dans un ordre quelconque. Les colonnes sont triées dans l'ordre croissant toujours. La table est modifiée par référence. Aucune copie n'est faite à tous, autres que temporaires de la mémoire de travail à une colonne.

Mon résumé est qu'ici la clé de "trier" les données.tableau, résultant en un effet très semblable à l' order(). Cependant, elle n'explique pas le but d'avoir une clé.

---

Les données.tableau FAQ 3.2 et 3.3 explique:

3.2 je n'ai pas de clé sur une grande table, mais le groupe est encore très rapide. Pourquoi est-ce?

les données.table utilise une base de tri. C'est sensiblement plus rapide que les autres algorithmes de tri. Radix est spéciquement pour les entiers uniquement, voir ?base::sort.list(x,method="radix"). C'est aussi une des raisons pour lesquelles setkey() est rapide. Lorsqu'aucune touche n'est définie, ou nous groupe dans un ordre différent à partir de la clé, nous l'appelons une ad-hoc par.

3.3 Pourquoi est-regroupement par des colonnes de la clé plus rapide qu'un groupe ad hoc?

Parce que chaque groupe est contiguë en mémoire vive, ce qui minimise la page extrait, et la mémoire peut être copié en vrac (memcpy C) plutôt que de boucle en C.

À partir d'ici, je suppose que la fixation d'une touche en quelque sorte, permet de R pour utiliser "radix tri" sur les autres algorithmes, et c'est pourquoi il est plus rapide.

---

Les 10 minutes guide de démarrage rapide dispose également d'un guide sur les touches.

1. Touches

Nous allons commencer par un examen des données.cadre, en particulier rownames (ou dans En anglais, les noms de lignes). C'est, aux noms multiples appartenant à un seul ligne. Les multiples noms appartenant à la ligne? Ce n'est pas ce nous sommes habitués dans un ensemble de données.cadre. Nous savons que chaque ligne a au plus un nom. Une personne a au moins deux noms, un prénom et un nom. C'est utile d'organiser un annuaire téléphonique, par exemple, qui est triée par nom, puis le prénom. Cependant, chaque ligne dans une les données.cadre peut avoir qu'un seul nom.

Une clé se compose d'un ou de plusieurs les colonnes de rownames, qui peut être un entier, un facteur de caractères ou certains les autres de la classe, pas simplement de caractère. En outre, les lignes sont triées par à la clé. Par conséquent, un ensemble de données.le tableau peut avoir au plus une clé, parce que c' ne peuvent pas être classés dans plus d'une façon.

L'unicité n'est pas appliquée, c'est à dire, des valeurs de clés dupliquées sont autorisés. Puisque les lignes sont triées par la clé, tous les doublons dans la clé apparaît consécutivement

L'annuaire téléphonique a été utile dans la compréhension de ce qu'est une clé, mais il semble que la clé n'est pas différent quand par rapport à avoir un facteur de colonne. En outre, il ne permet pas d'expliquer pourquoi l'une des clés nécessaires (en particulier pour l'utilisation de certaines fonctions) et la façon de choisir la colonne à définir comme clé. Aussi, il semble que dans un ensemble de données.table avec le temps, comme une colonne, la fixation de l'autre colonne comme clé serait probablement désordre de la colonne heure de trop, ce qui rend encore plus confus que je ne sais pas si je me suis permis de définir n'importe quelle autre colonne comme clé. Quelqu'un peut-il m'éclairer s'il vous plaît?

Answer 1

J'ai réécrit la réponse à un Q&a mode et de a supprimé certaines choses qui ne sont pas directement pertinents. J'espère que c'est mieux.

Qu'est-ce exactement ne setkey(DT, a, b) ?

Il trie DT par colonne a d'abord, puis par colonne b. C'est tout. Cependant, il le fait par référence - 1) aucune copie et 2) utilisation très efficace de la mémoire, une seule colonne supplémentaire (de type double - la plus grande taille) est alloué.

Quand est - setkey requis?

setkey est requis pour joins - X[Y]. Il n'est pas absolument nécessaire pour by= d'agrégation. Qui est, vous pouvez effectuer un "froid" - sans setkey comme suit:

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

Est-il un avantage à mettre la clé sur by= des opérations?

Très probablement sur le big data et les grands groupes. Dans ces cas, les groupes (tri) dans la mémoire peuvent accélérer les opérations un peu (efficacité de la mémoire cache). Notez que cela ne signifie pas que vous ne devriez pas touche set sur les données de petite taille. Juste que le bien-fondé de l'utilisation, il sera potentiellement plus élevé sur les données big data. Cela dit, la plupart des gens qui choisissent data.table invariablement le faire en raison de big data et donc les plus susceptibles d'être des clés.

Pourquoi avons-nous besoin d' setkey pour joins?

Parce qu'il utilise le binaire de recherche interne pour effectuer des jointures. Et il est requis par la recherche binaire pour conserver les données triées. Pour paraphraser Matthieu de réponse à partir d' ici - pour garder les choses gérable en interne, le tri est toujours dans l'ordre croissant. C'est pourquoi, setkey toujours trie dans l'ordre croissant.

Que fait exactement un binaire de recherche, de faire et comment il speeden rejoint ici?

Pas exactement la question de l'OP, mais depuis c'est la raison pour setkey, je trouve qu'il est approprié pour répondre ici.

L'idée de base est assez simple. Supposons que vous avez un vecteur trié,

x <- c(1, 5, 9, 12, 18, 19, 44)

et vous voulez trouver recherche de 5. Puisque vous savez que c'est triée, vous commencez par comparaison avec la moyenne de la valeur de "x" (ici 12).

5 < 12. So, repeat with values < 12 from x = c(1,5,9)
5 = 5.  done. Search complete and you can fetch the index

Remarquez qu'à chaque étape récursive, vous la moitié du nombre d'éléments à rechercher (conduisant à un moment de l'exécution de la complexité de l' O(log n)). C'est pourquoi le faire:

require(data.table)
options(datatable.verbose=TRUE)
set.seed(1)
DT <- data.table(x=sample(1e4, 1e7, TRUE), y=sample(1e4, 1e7, TRUE), key="x")
DT[J(1e4:1e5)]
# Starting binary search ...done in 0.01 secs

est incroyablement plus rapide que de faire ceci:

DF <- data.frame(DT)
system.time(DF[DF$x > 1e4 & DF$x < 1e5, ])
#   user  system elapsed 
#  1.614   0.043   1.672 

Il est extrêmement lent ici, car il utilise un vecteur d'analyse de l'approche continue à travers chaque valeur dans le DF$x et vérifier si elle satisfait à la condition souhaitée.

Donc les données triées nous permet d'utiliser les binaires de recherche qui à son tour nous permet de faire de rapides-des jointures et/ou rapide-des sous-ensembles.

Ce qui se passe sous le capot de l' setkey?

Ordering (ou sorting) est essentiel pour la plupart des data.table des opérations. Par conséquent, il est important d'avoir "de la commande" aussi vite que possible. base:::order n'a pas vraiment le couper. Bien que pour les entiers, la base n'rapide (mal nommé comme radix de tri) de comptage de tri (qui a quelques restrictions, comme range <= 1e5 et de non-cinq valeurs).

Par conséquent, data.tables' setkey utilise en interne fastorder qui met en œuvre un comptage de tri sur les personnages en utilisant efficacement les activités internes de R cache de chaîne et depuis v1.8.11, 3 passe-radix ordre pour les entiers, 6-passer radix commande double (numérique) adaptée de Michael Herf de l'article+code (qui a été inspiré par Pierre Tardiman de l'article).

Par rapport aux versions <= 1.8.10, l'ordre sur les entiers et les types numériques sont plus rapides d'environ 5-8x comme un résultat de cette. Veuillez cocher ici pour trouver la vitesse/temps des différences dans la commande des opérations entre les v1.8.10 et v1.8.11.

Pourquoi binaire de recherche?

De Matthieu de réponse ici, la raison en data.table implémente binaire de recherche est parce qu'il a le temps de la série se joindre à l'esprit. Plus précisément, il n'a pas les clés de hachage, car il a en vigueur commandé rejoint dans l'esprit (roll=TRUE option) - ex: Rouler vers l'avant ou vers l'arrière, Rouleau fin, en avant ou pas, commencer à Rouler vers l'arrière ou pas, de se Joindre à la valeur la plus proche etc..

---

En résumé, setkey est essentiel pour la recherche binaire qui prend la plupart des données.le tableau de la magie. (Matthieu et les autres, n'hésitez pas à ajouter/corriger quoi que ce soit dans ce post).

---

PS: la Plupart de ce matériel est de la récente parler Matthieu et j'ai donné à R groupe d'utilisateurs de Cologne. Il est maintenant disponible sur la page d'accueil. Voici un lien direct vers le fichier pdf.

Answer 2

Une clé est fondamentalement un index dans un jeu de données, ce qui permet très rapide et efficace de tri, de filtre, et les opérations de jointure. Ces sont probablement les meilleures raisons d'utiliser les données des tables au lieu de trames de données (la syntaxe d'utilisation de tables de données est également beaucoup plus conviviale, mais qui n'a rien à voir avec les clés).

Si vous ne comprenez pas les index, considérez ceci: un annuaire est "indexée" par son nom. Donc, si je veux rechercher un numéro de téléphone, c'est assez simple. Mais supposons que je recherche par numéro de téléphone (par exemple, de rechercher qui a un numéro de téléphone particulier)? Sauf que je peux "re-" index de l'annuaire téléphonique par le numéro de téléphone, il va prendre un temps très long.

Considérons l'exemple suivant: supposons que j'ai un tableau, ZIP, de tous les codes postaux aux états-unis (>à 33 000) ainsi que les informations associées (la ville, l'état, la population, le revenu médian, etc.). Si je veux regarder les informations pour un code postal, la recherche (filtre) est environ 1000 fois plus rapide si j' setkey(ZIP,zipcode) première.

Un autre avantage a faire avec des jointures. Supposons disposer d'une liste de personnes et de leurs codes postaux dans un tableau de données (que l'on appellera "PPL"), et je tiens à ajouter des informations à partir de la table de fermeture éclair (ex: ville, état, et ainsi de suite). Le code suivant va le faire:

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

C'est un "join" dans le sens que je suis de rejoindre les informations à partir de 2 tables de base dans un champ commun (code postal). Les jointures de ce genre sur de très grandes tables sont extrêmement lents avec des trames de données, et extrêmement rapide avec des tables de données. Dans un exemple réel que j'avais à faire plus de 20 000 rejoint comme ça sur une table pleine de codes postaux. Avec les tableaux de données le script a fallu environ 20 min. pour l'exécuter. Je n'ai même pas essayer avec des trames de données parce que cela aurait pris plus de 2 semaines.

À mon humble avis, vous ne devriez pas juste lire, mais l'étude de la FAQ et d'introduction de matériel. Il est plus facile à saisir si vous avez un problème réel pour l'appliquer.

[Réponse à @Frank commentaire]

Re: tri vs indexation Basée sur la réponse à cette question, il semble que l' setkey(...) , dans les faits, réorganiser les colonnes dans la table (par exemple, une sorte physique), et de ne pas créer un index dans la base de données des sens. Cela a des conséquences pratiques: pour une chose si vous définissez la clé dans une table avec setkey(...) , puis modifiez les valeurs dans la colonne de clé de données.table simplement déclare la table n'est plus trié (en éteignant l' sorted d'attribut); il n'est pas dynamiquement re-index pour maintenir le bon ordre de tri (comme ce serait le cas dans une base de données). Aussi, "la suppression de la clé" à l'aide de setky(DT,NULL) ne pas restaurer la table d'origine, non trié.

Re: filtre de vs joindre la pratique, la différence est que le filtrage extrait un sous-ensemble à partir d'un seul jeu de données, tandis que rejoindre combine des données provenant de deux ensembles de données basé sur un champ commun. Il ya beaucoup de différents types de jointure (intérieure, extérieure, à gauche). L'exemple ci-dessus est une jointure interne (uniquement les enregistrements avec des touches commun aux deux tables sont retournées), et cela a de nombreuses similitudes avec le filtrage.