PHP的in_array函數如何工作？

我不是計算機科學家，或者有很強的算法知識，但是今天我開始懷疑PHP的in_array方法是如何工作的。它看起來很直接，循環遍歷所有數組的元素，並根據給定的值檢查當前元素。但即使是較大的陣列，它仍然可以很快地工作。怎麼樣？PHP的in_array函數如何工作？

<?php 
$distros = ["Mint", "Debian", "Ubuntu", "Fedora", "CentOS", "Arch"]; 
if (in_array("Ubuntu", $distros)) { 
    echo "Got Ubuntu"; 
}

來源

2016-05-13 IntrovertedRoot

定義「非常快」。這並不是特別難以逐個檢查值是否相等... –

沒有什麼特別的魔法，它仍然循環遍歷每個條目，直到找到匹配（或到達數組的末尾）爲止，這意味着它是O（n），並且在數組中「進一步下降」可以找到任何匹配，它需要的時間越長;或者陣列沒有任何匹配的時間越長，則花費的時間越長 –

這樣的事情確實強調了大O符號所代表的「最壞情況」。平均情況是n/2，最好情況是1.如果你想測試'in_array'的速度，你正在查找的東西不能出現在數組中，以獲得最壞情況的測量結果。 –

這就是：

/* void php_search_array(INTERNAL_FUNCTION_PARAMETERS, int behavior) 
* 0 = return boolean 
* 1 = return key 
*/ 
static inline void php_search_array(INTERNAL_FUNCTION_PARAMETERS, int behavior) /* {{{ */ 
{ 
    zval *value,    /* value to check for */ 
     *array,    /* array to check in */ 
     *entry;    /* pointer to array entry */ 
    zend_ulong num_idx; 
    zend_string *str_idx; 
    zend_bool strict = 0;  /* strict comparison or not */ 

#ifndef FAST_ZPP 
    if (zend_parse_parameters(ZEND_NUM_ARGS(), "za|b", &value, &array, &strict) == FAILURE) { 
     return; 
    } 
#else 
    ZEND_PARSE_PARAMETERS_START(2, 3) 
     Z_PARAM_ZVAL(value) 
     Z_PARAM_ARRAY(array) 
     Z_PARAM_OPTIONAL 
     Z_PARAM_BOOL(strict) 
    ZEND_PARSE_PARAMETERS_END(); 
#endif 

    if (strict) { 
     ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_idx, str_idx, entry) { 
      ZVAL_DEREF(entry); 
      if (fast_is_identical_function(value, entry)) { 
       if (behavior == 0) { 
        RETURN_TRUE; 
       } else { 
        if (str_idx) { 
         RETVAL_STR_COPY(str_idx); 
        } else { 
         RETVAL_LONG(num_idx); 
        } 
        return; 
       } 
      } 
     } ZEND_HASH_FOREACH_END(); 
    } else { 
     ZVAL_DEREF(value); 
     if (Z_TYPE_P(value) == IS_LONG) { 
      ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_idx, str_idx, entry) { 
       if (fast_equal_check_long(value, entry)) { 
        if (behavior == 0) { 
         RETURN_TRUE; 
        } else { 
         if (str_idx) { 
          RETVAL_STR_COPY(str_idx); 
         } else { 
          RETVAL_LONG(num_idx); 
         } 
         return; 
        } 
       } 
      } ZEND_HASH_FOREACH_END(); 
     } else if (Z_TYPE_P(value) == IS_STRING) { 
      ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_idx, str_idx, entry) { 
       if (fast_equal_check_string(value, entry)) { 
        if (behavior == 0) { 
         RETURN_TRUE; 
        } else { 
         if (str_idx) { 
          RETVAL_STR_COPY(str_idx); 
         } else { 
          RETVAL_LONG(num_idx); 
         } 
         return; 
        } 
       } 
      } ZEND_HASH_FOREACH_END(); 
     } else { 
      ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_idx, str_idx, entry) { 
       if (fast_equal_check_function(value, entry)) { 
        if (behavior == 0) { 
         RETURN_TRUE; 
        } else { 
         if (str_idx) { 
          RETVAL_STR_COPY(str_idx); 
         } else { 
          RETVAL_LONG(num_idx); 
         } 
         return; 
        } 
       } 
      } ZEND_HASH_FOREACH_END(); 
     } 
    } 

    RETURN_FALSE; 
} 
/* }}} */ 

/* {{{ proto bool in_array(mixed needle, array haystack [, bool strict]) 
    Checks if the given value exists in the array */ 
PHP_FUNCTION(in_array) 
{ 
    php_search_array(INTERNAL_FUNCTION_PARAM_PASSTHRU, 0); 
}

來源

2016-05-13 12:04:28 Matheno

我通常不會冷靜下來，但是我必須對這一個下決心......即使我忽視了缺少任何評論或解釋，這隻會顯示C函數的定義，它沒有說明它是如何工作的，因爲定義使用'ZEND_HASH_FOREACH_KEY_VAL'來進行迭代？。它不該被接受。我們真的不知道該功能如何在內部工作... –

PHP的in_array函數如何工作？

回答

相關問題