배열 액세스 복잡성은 perl에서 O (1) 또는 O (n)입니까?

Question

함수 f (1), f (2), ..., f (1e7)의 결과를 캐싱합니다. 캐시의 요소는 무작위로 읽혀집니다. C에서 액세스 복잡성은 O (1)이므로 벡터에 저장합니다. Perl에서는 캐시를 벡터 또는 해시에 저장해야합니까?

해시에 저장하는 것이 입력이 순차적 정수라는 사실을 이용하지 않을 것이라고 생각합니다. 그러나 다른 한편으로, 나는 아마 이것을 overthinking 해요.

Answer 1

프로파일 링 할 때까지 효율성에 대한 일반적인 면책 조항 이외에 어레이에 저장한다고 말하고 싶습니다. 해시는 해시 키 계산시 추가 오버 헤드를 부과합니다. 게다가, 배열은 가장 자연스러운 표현이며, 성능이 좋지 않다면 명확성을 위해 이동하십시오.

Answer 2

직접 함수 결과를 캐시하는 대신 Memoize core module을 사용하십시오.

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

그게 전부이며, 오랫동안 주변에 있었고 잘 테스트되었습니다.

Answer 3

Perl에서 배열과 해시 모두 O (1)입니다. 하지만, 배열에 대한 O (1)은 절대 시계 시간이 더 빠르다고 생각합니다. 순차적 정수의 경우, 배열은 더 빠른 방법 일 수 있습니다. 그 간단한 지수는 수학적입니다.

Answer 4

존재하는 배열 요소에 액세스하는 것이 해시에 삽입하는 것보다 빠를 것입니다. 더하기 측면에서, 두 스케일의 성능은 유사합니다. (복잡성 분석 방법은 뭔가가 아니다 얼마나 빨리, 확장 얼마나 잘.)

배열 요소의

최악의 경우 액세스 : (한정된 길이 키) 해시 요소의

$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에 대한 (N) O입니다.)

당신의 키를 순차적 정수임을 감안할 때, 당신은 가장 확실히 배열을 사용해야합니다.

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

키가 희박한 경우 메모리를 절약하기 위해 해시를 사용하는 것이 좋습니다.

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