加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 大数据 > 正文

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

发布时间:2020-12-15 21:26:01 所属栏目:大数据 来源:网络整理
导读:在使用R之前,我使用了相当多的Perl。在Perl中,我经常使用散列,并且在Perl中查找散列通常被认为是快速的。 例如,以下代码将填充最多10000个键/值对的散列,其中键是随机字母,值是随机整数。然后,它在该哈希中执行10000次随机查找。 #!/usr/bin/perl -wu
在使用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的哈希数据结构比本机list()?

解决方法

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

正如Dirk所说,使用哈希包。这是一个巨大的限制是,它使用环境(哈希)和覆盖的方法来模仿哈希表。但是一个环境不能包含另一个环境,所以你不能使用哈希函数嵌套哈希。

一开始我在C / R中实现了一个可以嵌套的纯哈希表数据结构,但是在我处理其他事情时,它继续我的项目。这将是很高兴有虽然:-)

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读