O(log(n))是否可以以具有查找和插入的方式使用 Perl 哈希？
默认情况下，我假设查找是O(n)因为它由未排序的列表表示。
我知道我可以创建一个数据结构来满足这一点（即树等），但是，如果它是内置的并且可以用作普通哈希（即，使用 %）会更好
问问题
1383 次
3 回答
17
Perl 5 中的关联数组是用哈希表实现的，哈希表具有分期 O(1)（即常数时间）插入和查找。这就是为什么我们倾向于称它们为哈希而不是关联数组。
很难找到说明 Perl 5 使用哈希表来实现关联数组的文档（除了我们将关联数组称为“哈希”这一事实之外），但至少在perldoc perlfaq4
What happens if I add or remove keys from a hash while iterating over it?
(contributed by brian d foy)
The easy answer is "Don't do that!"
If you iterate through the hash with each(), you can delete the key
most recently returned without worrying about it. If you delete or add
other keys, the iterator may skip or double up on them since perl may
rearrange the hash table. See the entry for "each()" in perlfunc.
更好的报价来自perldoc perldata：
If you evaluate a hash in scalar context, it returns false if the hash
is empty. If there are any key/value pairs, it returns true; more
precisely, the value returned is a string consisting of the number of
used buckets and the number of allocated buckets, separated by a slash.
This is pretty much useful only to find out whether Perl's internal
hashing algorithm is performing poorly on your data set. For example,
you stick 10,000 things in a hash, but evaluating %HASH in scalar
context reveals "1/16", which means only one out of sixteen buckets has
been touched, and presumably contains all 10,000 of your items. This
isn't supposed to happen. If a tied hash is evaluated in scalar
context, a fatal error will result, since this bucket usage information
is currently not available for tied hashes.
当然，O(1) 只是理论上的表现。在现实世界中，我们没有完美的散列函数，所以散列会随着它们变大而变慢，并且有一些退化的情况会使散列变成 O(n)，但是 Perl 会尽力防止这种情况发生。以下是具有 10、100、1,000、10,000、100,000 个键的 Perl 哈希的基准：
Perl version 5.012000
Rate 10^5 keys 10^4 keys 10^3 keys 10^2 keys 10^1 keys
10^5 keys 5688029/s -- -1% -4% -7% -12%
10^4 keys 5748771/s 1% -- -3% -6% -11%
10^3 keys 5899429/s 4% 3% -- -4% -9%
10^2 keys 6116692/s 8% 6% 4% -- -6%
10^1 keys 6487133/s 14% 13% 10% 6% --
这是基准代码：
#!/usr/bin/perl
use strict;
use warnings;
use Benchmark;
print "Perl version $]\n";
my %subs;
for my $n (1 .. 5) {
my $m = 10 ** $n;
keys(my %h) = $m; #preallocated the hash so it doesn't have to keep growing
my $k = "a";
%h = ( map { $k++ => 1 } 1 .. $m );
$subs{"10^$n keys"} = sub {
return @h{"a", $k};
}
};
Benchmark::cmpthese -1, \%subs;
于 2010-06-12T18:28:40.797 回答
7
perl 哈希是一个哈希表，所以它已经有 O(1) 的插入和查找。
于 2010-06-12T18:28:00.033 回答
2
任何认为哈希插入或查找时间在现代硬件上为 O(1) 的人都非常天真。测量相同值的 get 是完全错误的。以下结果将使您更好地了解正在发生的事情。
Perl version 5.010001
Rate 10^6 keys 10^5 keys 10^1 keys 10^4 keys 10^3 keys 10^2 keys
10^6 keys 1.10/s -- -36% -64% -67% -68% -69%
10^5 keys 1.73/s 57% -- -43% -49% -50% -52%
10^1 keys 3.06/s 177% 76% -- -10% -12% -15%
10^4 keys 3.40/s 207% 96% 11% -- -3% -5%
10^3 keys 3.49/s 216% 101% 14% 3% -- -3%
10^2 keys 3.58/s 224% 107% 17% 6% 3% --
以上结果是在具有 5MB CPU 缓存的系统上测量的。请注意，性能从 3.5M/s 显着下降到 1M/s 查找。无论如何，它仍然非常快，并且在某些情况下，如果您知道自己在做什么，甚至可以击败像 RDBMS 这样的系统。您可以使用以下代码测量您的系统：
#!/usr/bin/perl
use strict;
use warnings;
use Benchmark;
print "Perl version $]\n";
my %subs;
for my $n ( 1 .. 6 ) {
my $m = 10**$n;
keys( my %h ) = $m; #preallocated the hash so it doesn't have to keep growing
my $k = "a";
%h = ( map { $k++ => 1 } 1 .. $m );
my $l = 10**( 6 - $n );
my $a;
$subs{"10^$n keys"} = sub {
for ( 1 .. $l ) {
$a = $h{$_} for keys %h;
}
};
}
Benchmark::cmpthese -3, \%subs;
您也不应该忘记哈希查找时间取决于密钥长度。简单地说，没有真正的技术具有 O(1) 访问时间。每种已知的实际技术都具有最佳的 O(logN) 访问时间。只有系统的访问时间为 O(1)，因为它们限制了它们的最大 N 并且降低了低 N 的性能。这就是现实世界中事物的运作方式，这就是为什么有人制作像Judy Array和进化这样的算法变得更糟的原因更糟的是。
于 2010-09-26T16:11:23.737 回答