perl - perl 中的数组访问复杂度是 O(1) 还是 O(n)？

Question

我正在缓存函数 f(1)、f(2)、...、f(1e7) 的结果。缓存中的元素将被随机读取。在 C 中，我将其存储在向量中，因为访问复杂度为 O(1)。在 Perl 中，我应该将缓存存储在向量还是散列中？

我觉得将它存储在哈希中不会利用输入是连续整数的事实。但另一方面，我可能想多了。

score 7 · Accepted Answer

与其自己缓存函数的结果，不如使用为您处理它的Memoize 核心模块。

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

这就是它的全部内容，它已经存在了很长时间并且经过了很好的测试。

score 2 · Accepted Answer

除了在您进行分析之前担心效率的通常免责声明之外，我会说将其存储在一个数组中。哈希在计算哈希键时会产生额外的开销。此外，数组是最自然的表示形式，除非您知道自己的表现不佳，否则请务必清楚。

score 1 · Accepted Answer

Perl 中的数组和哈希都是 O(1)。但是，我敢打赌，数组的 O(1) 在绝对时钟时间内会更快。在顺序整数数组的情况下，由于其简单的索引数学，数组可能会更快。

score 0 · Accepted Answer

访问存在的数组元素将比插入散列更快。从好的方面来说，两者的表现相似。（复杂性分析衡量事物的扩展性，而不是它的速度。）

数组元素的最坏情况访问：

$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} //= ...;
}

4 回答 4