복붙노트

Big-O for PHP 함수 목록

PHP

Big-O for PHP 함수 목록

잠시 동안 PHP를 사용하고 나면 모든 PHP가 예상대로 빨리 작동하지는 않습니다. 숫자가 캐쉬 된 소수 배열을 사용하여 프라임인지를 찾는 함수의 가능한 두 가지 구현을 고려하십시오.

//very slow for large $prime_array
$prime_array = array( 2, 3, 5, 7, 11, 13, .... 104729, ... );
$result_array = array();
foreach( $prime_array => $number ) {
    $result_array[$number] = in_array( $number, $large_prime_array );
}

//speed is much less dependent on size of $prime_array, and runs much faster.
$prime_array => array( 2 => NULL, 3 => NULL, 5 => NULL, 7 => NULL,
                       11 => NULL, 13 => NULL, .... 104729 => NULL, ... );
foreach( $prime_array => $number ) {
    $result_array[$number] = array_key_exists( $number, $large_prime_array );
}

이는 in_array가 선형 검색 O (n)로 구현 되었기 때문에 $ prime_array가 커짐에 따라 선형 적으로 감속하기 때문입니다. 여기서 array_key_exists 함수는 해시 테이블이 극도로 채워지지 않는 한 느려지지 않는 해시 조회 O (1)로 구현됩니다 (이 경우 O (n) 만 해당).

지금까지 나는 trial-and-error를 통해 big-O를 발견해야했으며 때로는 소스 코드를 살펴보아야했습니다. 질문은 ...

함수에 내장 된 모든 PHP *에 대한 이론적 (또는 실용적인) 큰 O 시간 목록이 있습니까?

* 또는 적어도 재미있는 것들

예를 들어 array_merge, array_merge_recursive, array_reverse, array_intersect, array_combine, str_replace (배열 입력 포함) 등 알 수없는 핵심 PHP 데이터 구조에 따라 구현이 달라질 수 있으므로 함수의 큰 기능을 예측하는 것은 매우 어렵습니다.

해결법

  1. ==============================

    1.이후 어딘가에 참조 용으로 사용하는 것이 좋을 것이라고 생각하기 전에는 아무도이 작업을 수행하지 않은 것으로 보입니다. 나는 array_ * 함수를 특성화하기 위해 벤치마킹이나 코드 스키밍을 통해 갔다. 나는 더 흥미로운 Big-O를 맨 위에 놓으려고 노력했다. 이 목록은 완전하지 않습니다.

    이후 어딘가에 참조 용으로 사용하는 것이 좋을 것이라고 생각하기 전에는 아무도이 작업을 수행하지 않은 것으로 보입니다. 나는 array_ * 함수를 특성화하기 위해 벤치마킹이나 코드 스키밍을 통해 갔다. 나는 더 흥미로운 Big-O를 맨 위에 놓으려고 노력했다. 이 목록은 완전하지 않습니다.

    참고 : Big-O는 실제로 O (n) 임에도 불구하고 해시 조회를 가정 할 때 계산 된 위치는 모두 O (1)입니다. n의 계수가 너무 낮기 때문에 조회 Big-O의 특성이 적용되기 전에 충분히 큰 배열을 저장하는 램 오버 헤드로 인해 해를 입을 수 있습니다. 예를 들어 N = 1과 N = 1,000,000의 array_key_exists에 대한 호출의 차이는 ~ 50 %의 시간 증가입니다.

    흥미로운 점 :

    조회 :

    array_key_exists O (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) - 모든 키를 다시 색인해야합니다.

    배열 교차, Union, 빼기 :

    array_intersect_key 교차점이 0 % 교차하는 경우 O (Σparam_i_size, 모든 i에 대해) 교차점 100 %가 O 일 때 (Max (param_i_size) * Σparam_i_count, 모든 i)

    교차점 0 %가 O (n ^ 2)와 교차하는 경우, 교차 100 %가 O (n ^ 2 * Σparam_i_count, 모든 i)

    array_intersect_assoc 모든 교차점 0 %가 교차하는 경우 O (Σparam_i_size, 모든 i에 대해) 교차 100 %가 O (Max (param_i_size) * Σparam_i_count)

    array_diff O (π param_i_size, 모든 i에 대해) - 이것은 모든 param_size의 곱입니다

    array_diff_key O (Σ param_i_size, 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에 대해)

    랜덤 :

    슉 f 혀 소리 (것)

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

    명백한 빅 - 오 :

    array_fill O (n)

    array_fill_keys O (n)

    범위 O (n)

    array_splice O (오프셋 + 길이)

    array_slice 길이가 NULL이면 O (offset + length) 또는 O (n)

    array_keys O (n)

    array_values ​​O (n)

    array_reverse O (n)

    array_pad O (pad_size)

    array_flip O (n)

    array_sum O (n)

    array_product O (n)

    array_reduce O (n)

    array_filter O (n)

    array_map O (n)

    array_chunk O (n)

    array_combine O (n)

    기능의 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 );
}
  2. ==============================

    2.거의 항상 array_key_exists 대신에 isset을 사용하려고합니다. 나는 내부를보고 있지는 않지만, array_key_exists가 O (N) 인 것은 확신한다. 왜냐하면 isset은 배열의 각 키를 반복 할 것이기 때문에 isset은 사용할 때와 동일한 해시 알고리즘을 사용하여 요소에 액세스하려고한다. 배열 인덱스에 액세스합니다. O (1)이어야합니다.

    거의 항상 array_key_exists 대신에 isset을 사용하려고합니다. 나는 내부를보고 있지는 않지만, array_key_exists가 O (N) 인 것은 확신한다. 왜냐하면 isset은 배열의 각 키를 반복 할 것이기 때문에 isset은 사용할 때와 동일한 해시 알고리즘을 사용하여 요소에 액세스하려고한다. 배열 인덱스에 액세스합니다. O (1)이어야합니다.

    주의 할 하나의 "잡았다"는 이것입니다 :

    $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';
?>

    is_set : 0.132308959961 초 array_key_exists : 2.33202195168 초

    물론 이것은 시간 복잡성을 보여주지는 않지만 두 함수가 서로 어떻게 비교되는지 보여줍니다.

    시간 복잡성을 테스트하려면 첫 번째 키와 마지막 키에서 이러한 함수 중 하나를 실행하는 데 걸리는 시간을 비교하십시오.

  3. ==============================

    3.구체적으로 설명하는 경우에 대한 설명은 연관 배열이 해시 테이블로 구현되므로 키 (및 이에 해당하는 array_key_exists)에 의한 조회가 O (1)입니다. 그러나 배열은 값에 의해 인덱싱되지 않으므로 일반적인 경우 값이 배열에 있는지 여부를 확인하는 유일한 방법은 선형 검색입니다. 거기에 놀랄 일이 없습니다.

    구체적으로 설명하는 경우에 대한 설명은 연관 배열이 해시 테이블로 구현되므로 키 (및 이에 해당하는 array_key_exists)에 의한 조회가 O (1)입니다. 그러나 배열은 값에 의해 인덱싱되지 않으므로 일반적인 경우 값이 배열에 있는지 여부를 확인하는 유일한 방법은 선형 검색입니다. 거기에 놀랄 일이 없습니다.

    필자는 PHP 메소드의 알고리즘 복잡성에 대한 포괄적 인 문서가 있다고 생각하지 않습니다. 그러나 노력을 보증 할만큼 충분히 큰 관심사라면 항상 소스 코드를 살펴볼 수 있습니다.

  4. ==============================

    4.사람들이 주요 충돌로 인해 실제로 문제가 발생하는 경우 보조 해시 조회 또는 균형 트리가있는 컨테이너를 구현합니다. 균형 잡힌 나무는 O (log n) 최악의 행동과 O (1) 평균을 줄 것입니다. case (해쉬 자체). 오버 헤드는 메모리 응용 프로그램에서 가장 실용적이지 않지만, 아마도 이러한 혼합 된 형태의 전략을 기본 경우로 구현하는 데이터베이스가 있습니다.

    사람들이 주요 충돌로 인해 실제로 문제가 발생하는 경우 보조 해시 조회 또는 균형 트리가있는 컨테이너를 구현합니다. 균형 잡힌 나무는 O (log n) 최악의 행동과 O (1) 평균을 줄 것입니다. case (해쉬 자체). 오버 헤드는 메모리 응용 프로그램에서 가장 실용적이지 않지만, 아마도 이러한 혼합 된 형태의 전략을 기본 경우로 구현하는 데이터베이스가 있습니다.

    5. from https://stackoverflow.com/questions/2473989/list-of-big-o-for-php-functions by cc-by-sa and MIT license

'PHP' 카테고리의 다른 글

PHP에서 비동기 GET 요청을하는 방법은 무엇입니까?  (0) 2018.09.12
사람들이 플래시 게임의 PHP 기반 최고 점수 테이블을 해킹하는 것을 막는 가장 좋은 방법은 무엇입니까?  (0) 2018.09.12
MySQL과 PHP : 키릴 문자가있는 UTF-8  (0) 2018.09.12
Woocommerce 3에서 주문 항목 및 WC_Order_Item_Product 가져 오기  (0) 2018.09.12
"경고 : 헤더 정보를 수정할 수 없습니다 - 이미 보낸 헤더"error [duplicate]  (0) 2018.09.12
,

티스토리툴바