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) であると考えている人は、非常にナイーブです。同じ値の取得を測定することは明らかに間違っています。次の結果は、何が起こっているかをよりよく理解するのに役立ちます。
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 に答える