在使用 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),因为在插入过程中,使用哈希函数将键转换为整数,然后将值放入数组 的
long(这是一个大简化,避免了处理碰撞的复杂性)。键的查找只需要对键进行哈希处理即可找到值的位置(与 O(n) 数组查找相比,其时间复杂度为 O(1))。 R 列表使用名称查找,时间复杂度为 O(n)。 hash(key) % num_spots
空间中num_spots
正如 Dirk 所说,使用 hash 包。一个巨大的限制是它使用环境(经过哈希处理)和重写 [
方法来模拟哈希表。但是一个环境不能包含另一个环境,因此不能使用哈希函数嵌套哈希。
不久前,我致力于在 C/R 中实现一个可以嵌套的纯哈希表数据结构,但当我处理其他事情时,它却在我的项目中被搁置了。不过,如果有的话那就太好了:-)
关于r - 我可以在 R 中使用列表作为哈希吗?如果是这样,为什么这么慢?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3470447/