[php] PHP 용 Big-O 함수 목록

어딘가에 이것을 참조하는 것이 좋은 생각이라고 생각하기 전에 아무도 이것을 한 것처럼 보이지 않습니다. 나는 array_*기능 을 특성화하기 위해 벤치 마크 또는 코드 스키밍을 통해 갔다 . 더 흥미로운 Big-O를 맨 위에 두려고했습니다. 이 목록은 완전하지 않습니다.

참고 : 해시 조회를 가정하여 계산 된 모든 Big-O는 실제로 O (n)이지만 O (1)입니다. n의 계수가 너무 낮기 때문에 충분히 큰 배열을 저장하는 램 오버 헤드로 인해 Big-O 조회 특성이 적용되기 전에 피해를 입을 수 있습니다. 예를 들어 array_key_existsN = 1과 N = 1,000,000에서 의 통화 차이 는 ~ 50 % 시간 증가입니다.

재미있는 포인트 :

1. isset/ array_key_exists훨씬보다 빨리 in_array와array_search
2. +(연합)보다 약간 빠르며 array_merge멋지게 보입니다. 그러나 다르게 작동하므로 명심하십시오.
3. shuffle 같은 Big-O 계층에 있습니다 array_rand
4. array_pop/ 재 인덱스 페널티로 인해 / array_push보다 빠릅니다array_shiftarray_unshift

조회 :

array_key_existsO (n)이지만 실제로 O (1)에 가깝습니다. 이것은 충돌의 선형 폴링 때문이지만 충돌 가능성이 매우 작기 때문에 계수도 매우 작습니다. 보다 현실적인 big-O를 제공하기 위해 해시 조회를 O (1)로 취급합니다. 예를 들어 N = 1000과 N = 100000의 차이는 약 50 % 만 느려집니다.

isset( $array[$index] )O (n)이지만 실제로 O (1)에 가깝습니다. array_key_exists와 동일한 조회를 사용합니다. 언어 구성이므로 키를 하드 코딩하면 조회를 캐시하여 동일한 키를 반복적으로 사용하는 경우 속도를 높입니다.

in_array O (n)-값을 찾을 때까지 배열을 통해 선형 검색을 수행하기 때문입니다.

array_search O (n)-in_array와 동일한 핵심 함수를 사용하지만 값을 반환합니다.

대기열 기능 :

array_push O (∑ var_i, 모든 i)

array_pop O (1)

array_shift O (n)-모든 키를 다시 색인화해야합니다

array_unshift O (n + ∑ var_i, 모든 i)-모든 키를 다시 색인화해야합니다

배열 교차, 조합, 빼기 :

array_intersect_key 교차로 100 %가 O를 수행하는 경우 (모든 i에 대해 최대 (param_i_size) * ∑param_i_count), 교차로 0 %가 O를 교차하면 (i, 모두 i에 대해 param_i_size)

array_intersect 교차로 100 %가 O (n ^ 2 * ∑param_i_count, 모든 i)를 수행하는 경우 교차로 0 %가 O (n ^ 2)를 교차하는 경우

array_intersect_assoc 교차로 100 %가 O를 수행하는 경우 (모든 i에 대해 최대 (param_i_size) * ∑param_i_count), 교차로 0 %가 O를 교차하면 (i, 모두 i에 대해 param_i_size)

array_diff O (π param_i_size, all i)-모든 param_size의 곱입니다

array_diff_key O (∑ param_i_size, for i! = 1)-첫 번째 배열을 반복 할 필요가 없기 때문입니다.

array_merge O (∑ array_i, i! = 1)-첫 번째 배열을 반복 할 필요가 없습니다.

+ (union) O (n), 여기서 n은 두 번째 배열의 크기입니다 (즉, array_first + array_second)-번호를 다시 매길 필요가 없기 때문에 array_merge보다 오버 헤드가 적습니다.

array_replace O (∑ array_i, 모든 i)

무작위 :

shuffle 의 위에)

array_rand O (n)-선형 폴링이 필요합니다.

명백한 Big-O :

array_fill 의 위에)

array_fill_keys 의 위에)

range 의 위에)

array_splice O (오프셋 + 길이)

array_slice 길이가 NULL 인 경우 O (오프셋 + 길이) 또는 O (n)

array_keys 의 위에)

array_values 의 위에)

array_reverse 의 위에)

array_pad O (패드 _ 크기)

array_flip 의 위에)

array_sum 의 위에)

array_product 의 위에)

array_reduce 의 위에)

array_filter 의 위에)

array_map 의 위에)

array_chunk 의 위에)

array_combine 의 위에)

함수의 Big-O를 쉽게 찾을 수있게 해주신 Eureqa 에게 감사드립니다 . 임의의 데이터에 가장 적합한 기능을 찾을 수 있는 놀라운 무료 프로그램입니다.

편집하다:

PHP 배열 조회가 의심된다는 사람들을 위해 O(N), 나는 그것을 테스트하기 위해 벤치 마크를 작성했습니다 (그들은 여전히 O(1)가장 현실적인 값에 효과적 입니다).

$tests = 1000000;
$max = 5000001;


for( $i = 1; $i <= $max; $i += 10000 ) {
    //create lookup array
    $array = array_fill( 0, $i, NULL );

    //build test indexes
    $test_indexes = array();
    for( $j = 0; $j < $tests; $j++ ) {
        $test_indexes[] = rand( 0, $i-1 );
    }

    //benchmark array lookups
    $start = microtime( TRUE );
    foreach( $test_indexes as $test_index ) {
        $value = $array[ $test_index ];
        unset( $value );
    }
    $stop = microtime( TRUE );
    unset( $array, $test_indexes, $test_index );

    printf( "%d,%1.15f\n", $i, $stop - $start ); //time per 1mil lookups
    unset( $stop, $start );
}

답변

$search_array = array('first' => null, 'second' => 4);

// returns false
isset($search_array['first']);

// returns true
array_key_exists('first', $search_array);

<?php

$bigArray = range(1,100000);

$iterations = 1000000;
$start = microtime(true);
while ($iterations--)
{
    isset($bigArray[50000]);
}

echo 'is_set:', microtime(true) - $start, ' seconds', '<br>';

$iterations = 1000000;
$start = microtime(true);
while ($iterations--)
{
    array_key_exists(50000, $bigArray);
}

echo 'array_key_exists:', microtime(true) - $start, ' seconds';
?>