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函数如何工作？

回答

相关问题