我可以在R中使用列表作为哈希吗？如果是这样,为什么这么慢？

Question

在使用R之前,我使用了相当多的Perl.在Perl中,我经常使用哈希,并且在Perl中通常认为哈希的查找速度很快.

例如,以下代码将填充最多10000个键/值对的散列,其中键是随机字母,值是随机整数.然后,它在该哈希中进行10000次随机查找.

#!/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";
}

现在越来越多,我想在R中有一个类似哈希的数据结构.以下是等效的R代码:

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

代码似乎在做同等的事情.但是,Perl的速度要快得多:

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

与R相比:

time R CMD BATCH RHashTest.R

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

什么解释了这种差异？R列表中的查找是不是很好？

增加到100,000个列表长度和100,000个查找只会夸大差异？R中的哈希数据结构是否比本机列表()有更好的替代方案？

Answer 1

根本原因是具有命名元素的R列表不进行哈希处理.散列查找是O(1),因为在插入过程中,使用散列函数将键转换为整数,然后将值放入hash(key) % num_spots数组的空间中num_spots(这是一个很大的简化,避免了处理冲突的复杂性) .查找密钥只需要散列密钥以找到值的位置(即O(1),而不是O(n)数组查找).R列表使用名称查找,即O(n).

正如Dirk所说,使用哈希包.这方面的一个巨大限制是它使用环境(经过哈希处理)和覆盖[模拟哈希表的方法.但是环境不能包含其他环境,因此您不能使用哈希函数嵌套哈希.

前段时间我一直致力于在C/R中实现一个可以嵌套的纯哈希表数据结构,但是当我处理其他事情时,它继续在我的项目上运行.尽管如此,这将是很好的:-)

Answer 2

您可以尝试使用Christopher Brown的环境和/或哈希包(它恰好使用引擎盖下的环境).

Answer 3

你的代码非常不像R一样,也是它如此缓慢的原因之一.我没有优化下面的代码以获得最大速度,只有R'ness.

n <- 10000

keys <- matrix( sample(letters, 3*n, replace = TRUE), nrow = 3 )
keys <- apply(keys, 2, paste0, collapse = '')
value <- floor(1000*runif(n))
testHash <- as.list(value)
names(testHash) <- keys

keys <- sample(names(testHash), n, replace = TRUE)
lookupValue = testHash[keys]
print(data.frame('key', keys, 'lookup', unlist(lookupValue)))

在我的机器上几乎瞬间运行,不包括打印.您的代码运行速度与您报告的速度大致相同.它正在做你想要的吗？您可以将n设置为10,只需查看输出和testHash,看看是否就是这样.

关于语法注: 该apply上面是一个简单的循环,而这些都是缓慢R.那些点申请家庭命令是表现力.随后的许多命令都可以放在一个循环中apply,如果它是一个for循环,那就是诱惑.在R中尽可能多地从循环中取出.使用apply family命令使这更自然,因为该命令旨在将一个函数的应用程序表示为某种类型的列表而不是通用循环(是的,我知道apply可以在多个命令上使用).

Answer 4

我有点像R hack,但我是一名经验主义者,所以我会分享一些我观察过的事情,让那些对R有更多理论上理解的人能够解释为什么.

• R使用标准流比使用Perl慢得多.由于stdin和stout在Perl中更常用,我假设它已经优化了它如何做这些事情.因此,在RI中,使用内置函数(例如write.table)读取/写入文本的速度要快得多.

• 正如其他人所说,R中的向量运算比循环更快...而且速度快,大多数apply()族语法只是循环中的一个漂亮的包装器.

• 索引的东西比非索引的东西工作得更快.(很明显,我知道.)data.table包支持数据帧类型对象的索引.

• 我从来没有使用像@Allen这样的哈希环境(而且我从来没有吸入过哈希...据你所知)

• 您使用的一些语法有效,但可能会收紧.我不认为这对速度有任何影响,但代码更具可读性.我不写的很紧的代码,但我编辑了一些东西像改变floor(1000*runif(1))来sample(1:1000, n, replace=T).我不是故意迂腐,我只是按照从头开始的方式写它.

因此,考虑到这一点,我决定测试@allen使用的哈希方法(因为它对我来说很新颖),而不是我使用索引data.table作为查找表创建的"穷人的哈希".我并不是100%确定@allen和我正在做的正是你在Perl中所做的,因为我的Perl非常生疏.但我认为下面的两种方法做同样的事情.我们都从'hash'中的键中对第二组键进行采样,因为这可以防止哈希未命中.你想测试这些例子如何处理哈希欺骗,因为我没有多想.

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 )

  }

如果我使用100,000次绘制运行每个方法,我得到这样的东西:

> 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 

请记住,这仍然比Perl代码慢得多,Perl代码在我的PC上似乎在一秒钟内运行100K样本.

我希望上面的例子有所帮助.如果您对why@allen 有任何疑问,@ vince和@dirk将能够回答;)

输入上述内容后,我意识到我没有测试@john做了什么.那么,到底是什么,让我们做所有3.我将代码从@john更改为使用write.table(),这是他的代码:

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

和运行时间:

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

你有它.@john写紧/快R代码!

Answer 5

但环境不能包含另一个环境(引自Vince的回答).

也许是前一段时间(我不知道),但这些信息似乎不再准确:

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

因此环境现在可以制作出非常强大的地图/字典.也许你会错过'['运算符,在这种情况下使用哈希包.

从哈希包文档中获取的这个注释也可能是有意义的:

R正在慢慢转向使用环境的本机哈希实现,(参见Extract.使用$和[[已经有一段时间可用,最近的对象可以从环境中继承等等)访问环境.但许多功能使得哈希/词典伟大的仍然缺乏,如切片操作,[.