0

関数 f(1)、f(2)、...、f(1e7) の結果をキャッシュしています。キャッシュ内の要素はランダムに読み取られます。アクセスの複雑さは O(1) であるため、C ではこれをベクトルに格納します。Perl では、キャッシュをベクトルまたはハッシュに格納する必要がありますか?

ハッシュに格納しても、入力が連続した整数であるという事実を利用できないと思います。しかし一方で、私はおそらくこれを考えすぎています。

4

4 に答える 4

7

関数の結果を自分でキャッシュするのではなく、関数を処理するメモ化コアモジュールを使用してください。

use Memoize;
memoize('slow_function');
slow_function(arguments); # Is faster than it was before

これですべてです。長い間使用されており、十分にテストされています。

于 2012-11-29T17:48:54.063 に答える
2

プロファイルを作成するまで効率を心配することについての通常の免責事項を除いて、私はそれを配列に格納すると言います。ハッシュは、ハッシュキーの計算に追加のオーバーヘッドを課します。その上、配列は最も自然な表現であり、パフォーマンスがオフであることがわかっていない限り、明確にするために行ってください。

于 2012-11-29T17:43:15.887 に答える
1

Perl の配列とハッシュはどちらも O(1) です。しかし、絶対クロック時間では、配列の O(1) の方が速いに違いありません。シーケンシャル整数配列の場合、単純なインデックス数学よりもはるかに高速になる場合があります。

于 2012-11-29T17:50:23.677 に答える
0

存在する配列要素へのアクセスは、ハッシュへの挿入よりも高速になります。プラス面としては、両方のパフォーマンスが同様にスケーリングされます。(複雑さの分析は、何かがどれだけ速くスケーリングするかではなく、どれだけスケールするかを測定します。)

配列要素への最悪のアクセス:

$x = $a[$i];           # O(1)
$a[$i] = $x;   $i<@a   # O(1)
$a[$i] = $x;           # O(1), amortized

ハッシュ要素の最悪の場合のアクセス (制限された長さを持つキーの場合):

$x = $h{$k};           # O(1)
$h{$k} = $x;           # O(1), amortized

(「償却 O(1)」は、これらの操作の N に対して O(N) であることを意味します。)

キーが連続する整数であることを考えると、最も確実に配列を使用する必要があります。

my @cache;
sub func {
    my ($n) = @_;
    return $cache[$n] //= ...;
}

代わりにキーがまばらな場合は、メモリを節約するためにハッシュを使用する方がよいでしょう。

my %cache;
sub func {
    my ($n) = @_;
    return $cache{$n} //= ...;
}
于 2012-11-29T21:23:40.007 に答える