Puis-je utiliser une liste comme un hachage dans R? Si oui, pourquoi est-ce si lent?

Question

Avant d'utiliser R, j'ai utilisé un peu de Perl. En Perl, j'ai souvent l'utilisation de tables de hachage, et les recherches de hachages sont généralement considérés comme rapide en Perl.

Par exemple, le code suivant va remplir une table de hachage avec jusqu'à 10 000 paires clé/valeur, où les touches sont aléatoires de lettres et les valeurs sont des entiers aléatoires. Ensuite, il n'10000 hasard des recherches dans ce hachage.

#!/usr/bin/perl -w
use strict;

my @letters = ('a'..'z');

print @letters . "\n";
my %testHash;

for(my $i = 0; $i < 10000; $i++) {
    my $r1 = int(rand(26));
    my $r2 = int(rand(26));
    my $r3 = int(rand(26));
    my $key = $letters[$r1] . $letters[$r2] . $letters[$r3];
    my $value = int(rand(1000));
    $testHash{$key} = $value;
}

my @keyArray = keys(%testHash);
my $keyLen = scalar @keyArray;

for(my $j = 0; $j < 10000; $j++) {
    my $key = $keyArray[int(rand($keyLen))];
    my $lookupValue = $testHash{$key};
    print "key " .  $key . " Lookup $lookupValue \n";
}

Maintenant que de plus en plus, je suis désireux d'avoir une table de hachage, comme la structure des données dans R. ce qui suit est l'équivalent de la R code:

testHash <- list()

for(i in 1:10000) {
  key.tmp = paste(letters[floor(26*runif(3))], sep="")
  key <- capture.output(cat(key.tmp, sep=""))
  value <- floor(1000*runif(1))
  testHash[[key]] <- value
}

keyArray <- attributes(testHash)$names
keyLen = length(keyArray);

for(j in 1:10000) {
  key <- keyArray[floor(keyLen*runif(1))]
  lookupValue = testHash[[key]]
  print(paste("key", key, "Lookup", lookupValue))
}

Le code semble être en train de faire l'équivalent de choses. Cependant, le Perl est beaucoup plus rapide:

>time ./perlHashTest.pl
real    0m4.346s
user    **0m0.110s**
sys 0m0.100s

La comparaison de R:

time R CMD BATCH RHashTest.R

real    0m8.210s
user    **0m7.630s**
sys 0m0.200s

Ce qui explique cette différence? Sont recherches dans les R les listes simplement pas la bonne?

L'augmentation de 100 000 liste de longueur et de 100 000 recherches seulement exagère la différence? Est-il une meilleure alternative pour le hachage de la structure des données dans R que le natif de liste()?

Answer 1

La raison sous-jacente est que la R des listes avec des éléments nommés ne sont pas cryptées. Hachage des recherches sont en O(1), parce que pendant insérez la clé est convertie en un entier en utilisant une fonction de hachage, puis le mettre en valeur l'espace hash(key) % num_spots d'un tableau num_spots long (c'est une grosse simplification et évite la complexité de gérer les collisions). Les recherches de la clé juste besoin de hachage de la clé pour trouver la valeur de position (qui est O(1), par rapport à un O(n) de la matrice de la recherche). R les listes d'utiliser les recherches de noms qui sont en O(n).

Comme Dirk dit, utiliser le hachage paquet. Une énorme limitation de cette approche est qu'il utilise des environnements (qui sont hachés) et d'écraser [ méthodes pour imiter les tables de hachage. Mais l'environnement ne peut pas contenir un autre environnement, de sorte que vous ne peut pas être imbriquées les hachages avec la fonction de hachage.

Un temps, j'ai travaillé sur la mise en œuvre d'un pur table de hachage de la structure de données en C/R qui pourrait être imbriquées, mais il est allé sur mon projet brûleur arrière pendant que je travaillais sur d'autres choses. Il serait agréable d'avoir bien :-)

Answer 2

Vous pouvez essayer les environnements et / ou le paquetage de hachage de Christopher Brown (qui utilise des environnements sous le capot).

Answer 3

Votre code ressemble beaucoup à R et est l’une des raisons pour laquelle il est si lent. Je n'ai pas optimisé le code ci-dessous pour une vitesse maximale, seulement R'ness.

 n <- 10000

keys = sapply(character(n), function(x) paste(letters[ceiling(26*runif(3))], collapse=''))
value <- floor(1000*runif(n))
testHash <- as.list(value)
names(testHash) <- keys

keys <- names(testHash)[ceiling(n*runif(n))]
lookupValue = testHash[keys]
print(data.frame('key', keys, 'lookup', unlist(lookupValue)))
 

Sur ma machine, l'exécution est quasi instantanée, excluant l'impression. Votre code a fonctionné à peu près à la même vitesse que celle que vous avez indiquée. Est-ce qu'il fait ce que tu veux? Vous pouvez définir n à 10 et simplement regarder la sortie et testHash et voir si c'est tout.

Answer 4

Je suis un peu d'un R hack, mais je suis un empiriste donc, je vais partager quelques choses que j'ai observées et que ceux avec une plus grande compréhension théorique de R faire la lumière sur les "pourquois".

• R semble beaucoup plus lentement, en utilisant la norme les flux de Perl. Depuis stdin et stout sont beaucoup plus couramment utilisés dans Perl je suppose qu'il a des optimisations autour de la façon dont il le fait ces choses. Donc, en R I trouver BEAUCOUP plus rapide à lire/écrire du texte en utilisant le construit en les fonctions e.g write.table).

• Comme d'autres l'ont dit, vecteur les opérations dans R sont plus rapides que boucles... et w.r.t. la vitesse, la plupart s'appliquent() de la famille la syntaxe est simplement une jolie wrapper sur une boucle.

• Indexé les choses fonctionnent plus rapidement que non indexés. (Évident, je sais). Les données.tableau package prend en charge l'indexation de la trame de données de type objets.

• Je n'ai jamais utilisé de hachage les environnements comme @Allen illustré (et je n'ai jamais inhalé de hachage... aussi loin que vous le savez)

• Certains de la syntaxe que vous avez utilisé fonctionne, mais pourrait être renforcé. Je ne pense pas que tout cela est vraiment important pour la vitesse, mais le code est un peu plus lisible. Je n'écris pas très serré code, mais j'ai modifié un peu l'évolution des choses comme floor(1000*runif(1)) de sample(1:1000, n, replace=T). Je ne veux pas être pédant, j'ai juste écrit de la façon que je le ferais à partir de zéro.

Donc, avec cela à l'esprit, j'ai décidé de tester la valeur de hachage de l'approche que @allen utilisé (parce que c'est nouveau pour moi) sur mon "pauvre homme de hachage" que j'ai créé à l'aide d'une des données indexées.le tableau comme un tableau de recherche. Je ne suis pas sûr à 100% que ce que @allen et moi sommes en train de faire est exactement ce que vous avez fait en Perl parce que mon Perl est assez rouillé. Mais je pense que les deux méthodes ci-dessous faire la même chose. Nous avons tous les deux de l'échantillon de la deuxième jeu de clés à partir des touches dans le "hachage", car cela empêche de hachage manque. Vous voulez tester la façon dont ces exemples poignée de hachage dupes que je n'ai pas donné beaucoup de pensée.

require(data.table)

dtTest <- function(n) {

  makeDraw <- function(x) paste(sample(letters, 3, replace=T), collapse="")
  key <- sapply(1:n, makeDraw)
  value <- sample(1:1000, n, replace=T)

  myDataTable <- data.table(key, value,  key='key')

  newKeys <- sample(as.character(myDataTable$key), n, replace = TRUE)

  lookupValues <- myDataTable[newKeys]

  strings <- paste("key", lookupValues$key, "Lookup", lookupValues$value )
  write.table(strings, file="tmpout", quote=F, row.names=F, col.names=F )
}

#

hashTest <- function(n) {

  testHash <- new.env(hash = TRUE, size = n)

  for(i in 1:n) {
    key <- paste(sample(letters, 3, replace = TRUE), collapse = "")
    assign(key, floor(1000*runif(1)), envir = testHash)
  }

  keyArray <- ls(envir = testHash)
  keyLen <- length(keyArray)

  keys <- sample(ls(envir = testHash), n, replace = TRUE)
  vals <- mget(keys, envir = testHash)

  strings <- paste("key", keys, "Lookup", vals )
  write.table(strings, file="tmpout", quote=F, row.names=F, col.names=F )

  }

si j'ai l'exécution de chaque méthode à l'aide de 100 000 tirages, j'obtiens quelque chose comme ceci:

> system.time(  dtTest(1e5))
   user  system elapsed 
  2.750   0.030   2.881 
> system.time(hashTest(1e5))
   user  system elapsed 
  3.670   0.030   3.861 

Gardez à l'esprit que c'est toujours beaucoup plus lent que le code Perl qui, sur mon PC, le PC semble fonctionner 100K échantillons en moins d'une seconde.

J'espère que l'exemple ci-dessus aide. Et si vous avez des questions quant à l' why peut-être @allen, @vince, et @dirk sera en mesure de répondre ;)

Après j'ai tapé ci-dessus, j'ai réalisé que je n'avais pas testé ce que @jean l'a fait. Donc, ce que l'enfer, nous allons faire tous les 3. J'ai changé le code de @john à l'utilisation de l'écriture.tableau() et voici son code:

johnsCode <- function(n){
  keys = sapply(character(n), function(x) paste(letters[ceiling(26*runif(3))],
    collapse=''))
  value <- floor(1000*runif(n))
  testHash <- as.list(value)
  names(testHash) <- keys

  keys <- names(testHash)[ceiling(n*runif(n))]
  lookupValue = testHash[keys]

  strings <- paste("key", keys, "Lookup", lookupValue )
  write.table(strings, file="tmpout", quote=F, row.names=F, col.names=F )
}

et le moment de l'exécution:

> system.time(johnsCode(1e5))
   user  system elapsed 
  2.440   0.040   2.544 

Et là vous l'avez. @jean écrit serré rapide/R code!

Answer 5

Mais l'environnement ne peut pas contenir un autre environnement (cité de Vince réponse).

Peut-être que c'était comme ça il y a quelques temps (je ne sais pas), mais cette information ne semble pas être plus précis:

> d <- new.env()
> d$x <- new.env()
> d$x$y = 20
> d$x$y
[1] 20

Si les environnements de faire un joli capable de la carte/dict maintenant. Peut-être que vous manquez de l' '[' opérateur, utilisez le hash paquet dans ce cas.

Cette remarque prises à partir de la valeur de hachage de la documentation du paquet peut aussi être d'intérêt:

R se déplace lentement vers une implémentation native de hachages à l'aide de environnements, (cf. Extrait de. L'accès à des environnements à l'aide de $ et [[ a été disponibles pendant un certain temps, et, récemment, les objets peuvent hériter de les environnements, etc. Mais beaucoup de caractéristiques qui font de hachages/dictionnaires grand manque toujours, comme la tranche de l'opération, [.