PHP中array_keys和array_unique函数源码的分析

性能分析

从运行性能上分析,看看下面的测试代码:

$test=array();
for($run=0; $run<10000; $run++)
$test[]=rand(0,100);

$time=microtime(true);

$out = array_unique($test);

$time=microtime(true)-$time;
echo 'Array Unique: '.$time."\n";

$time=microtime(true);

$out=array_keys(array_flip($test));

$time=microtime(true)-$time;
echo 'Keys Flip: '.$time."\n";

$time=microtime(true);

$out=array_flip(array_flip($test));

$time=microtime(true)-$time;
echo 'Flip Flip: '.$time."\n";

运行结果如下:

从上图可以看到,使用array_unique函数需要0.069s;使用array_flip后再使用array_keys函数需要0.00152s;使用两次array_flip函数需要0.00146s。

测试结果表明,使用array_flip后再调用array_keys函数比array_unique函数快。那么,具体原因是什么呢?让我们看看在PHP底层,这两个函数是怎么实现的。

源码分析

/* {{{ proto array array_keys(array input [, mixed search_value[, bool strict]])
  Return just the keys from the input array, optionally only for the specified       search_value */
PHP_FUNCTION(array_keys)
{
  //变量定义
  zval *input,        /* Input array */
     *search_value = NULL,  /* Value to search for */
     **entry,        /* An entry in the input array */
      res,          /* Result of comparison */
     *new_val;        /* New value */
  int  add_key;        /* Flag to indicate whether a key should be added */
  char *string_key;      /* String key */
  uint  string_key_len;
  ulong num_key;        /* Numeric key */
  zend_bool strict = 0;    /* do strict comparison */
  HashPosition pos;
  int (*is_equal_func)(zval *, zval *, zval * TSRMLS_DC) = is_equal_function;

  //程序解析参数
  if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a|zb", &input, &search_value, &strict) == FAILURE) {
    return;
  }

  // 如果strict是true,则设置is_equal_func为is_identical_function,即全等比较
  if (strict) {
    is_equal_func = is_identical_function;
  }

  /* 根据search_vale初始化返回的数组大小 */
  if (search_value != NULL) {
    array_init(return_value);
  } else {
    array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL_P(input)));
  }
  add_key = 1;

  /* 遍历输入的数组参数,然后添加键值到返回的数组 */
  zend_hash_internal_pointer_reset_ex(Z_ARRVAL_P(input), &pos);//重置指针
  //循环遍历数组
  while (zend_hash_get_current_data_ex(Z_ARRVAL_P(input), (void **)&entry, &pos) == SUCCESS) {
    // 如果search_value不为空
    if (search_value != NULL) {
      // 判断search_value与当前的值是否相同,并将比较结果保存到add_key变量
      is_equal_func(&res, search_value, *entry TSRMLS_CC);
      add_key = zval_is_true(&res);
    }

    if (add_key) {
      // 创建一个zval结构体
      MAKE_STD_ZVAL(new_val);

      // 根据键值是字符串还是整型数字将值插入到return_value中
      switch (zend_hash_get_current_key_ex(Z_ARRVAL_P(input), &string_key, &string_key_len, &num_key, 1, &pos)) {
        case HASH_KEY_IS_STRING:
          ZVAL_STRINGL(new_val, string_key, string_key_len - 1, 0);
          // 此函数负责将值插入到return_value中,如果键值已存在,则使用新值更新对应的值,否则直接插入
          zend_hash_next_index_insert(Z_ARRVAL_P(return_value), &new_val, sizeof(zval *), NULL);
          break;

        case HASH_KEY_IS_LONG:
          Z_TYPE_P(new_val) = IS_LONG;
          Z_LVAL_P(new_val) = num_key;
          zend_hash_next_index_insert(Z_ARRVAL_P(return_value), &new_val, sizeof(zval *), NULL);
          break;
      }
    }

    // 移动到下一个
    zend_hash_move_forward_ex(Z_ARRVAL_P(input), &pos);
  }
}
/* }}} */

以上是array_keys函数底层的源码。为方便理解,笔者添加了一些中文注释。如果需要查看原始代码,可以点击查看。这个函数的功能就是新建一个临时数组,然后将键值对重新复制到新的数组,如果复制过程中有重复的键值出现,那么就用新的值替换。这个函数的主要步骤是地57和63行调用的zend_hash_next_index_insert函数。该函数将元素插入到数组中,如果出现重复的值,则使用新的值更新原键值指向的值,否则直接插入,时间复杂度是O(n)。

/* {{{ proto array array_flip(array input)
  Return array with key <-> value flipped */
PHP_FUNCTION(array_flip)
{
  // 定义变量
  zval *array, **entry, *data;
  char *string_key;
  uint str_key_len;
  ulong num_key;
  HashPosition pos;

  // 解析数组参数
  if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a", &array) == FAILURE) {
    return;
  }

  // 初始化返回数组
  array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL_P(array)));

  // 重置指针
  zend_hash_internal_pointer_reset_ex(Z_ARRVAL_P(array), &pos);
  // 遍历每个元素,并执行键<->值交换操作
  while (zend_hash_get_current_data_ex(Z_ARRVAL_P(array), (void **)&entry, &pos) == SUCCESS) {
    // 初始化一个结构体
    MAKE_STD_ZVAL(data);
    // 将原数组的值赋值为新数组的键
    switch (zend_hash_get_current_key_ex(Z_ARRVAL_P(array), &string_key, &str_key_len, &num_key, 1, &pos)) {
      case HASH_KEY_IS_STRING:
        ZVAL_STRINGL(data, string_key, str_key_len - 1, 0);
        break;
      case HASH_KEY_IS_LONG:
        Z_TYPE_P(data) = IS_LONG;
        Z_LVAL_P(data) = num_key;
        break;
    }

    // 将原数组的键赋值为新数组的值,如果有重复的,则使用新值覆盖旧值
    if (Z_TYPE_PP(entry) == IS_LONG) {
      zend_hash_index_update(Z_ARRVAL_P(return_value), Z_LVAL_PP(entry), &data, sizeof(data), NULL);
    } else if (Z_TYPE_PP(entry) == IS_STRING) {
      zend_symtable_update(Z_ARRVAL_P(return_value), Z_STRVAL_PP(entry), Z_STRLEN_PP(entry) + 1, &data, sizeof(data), NULL);
    } else {
      zval_ptr_dtor(&data); /* will free also zval structure */
      php_error_docref(NULL TSRMLS_CC, E_WARNING, "Can only flip STRING and INTEGER values!");
    }

    // 下一个
    zend_hash_move_forward_ex(Z_ARRVAL_P(array), &pos);
  }
}
/* }}} */

上面就是是array_flip函数的源码。点击链接查看原始代码。这个函数主要的做的事情就是创建一个新的数组,遍历原数组。在26行开始将原数组的值赋值为新数组的键,然后在37行开始将原数组的键赋值为新数组的值,如果有重复的,则使用新值覆盖旧值。整个函数的时间复杂度也是O(n)。因此,使用了array_flip之后再使用array_keys的时间复杂度是O(n)。

接下来,我们看看array_unique函数的源码。点击链接查看原始代码。

/* {{{ proto array array_unique(array input [, int sort_flags])
  Removes duplicate values from array */
PHP_FUNCTION(array_unique)
{
  // 定义变量
  zval *array, *tmp;
  Bucket *p;
  struct bucketindex {
    Bucket *b;
    unsigned int i;
  };
  struct bucketindex *arTmp, *cmpdata, *lastkept;
  unsigned int i;
  long sort_type = PHP_SORT_STRING;

  // 解析参数
  if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a|l", &array, &sort_type) == FAILURE) {
    return;
  }

  // 设置比较函数
  php_set_compare_func(sort_type TSRMLS_CC);

  // 初始化返回数组
  array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL_P(array)));
  // 将值拷贝到新数组
  zend_hash_copy(Z_ARRVAL_P(return_value), Z_ARRVAL_P(array), (copy_ctor_func_t) zval_add_ref, (void *)&tmp, sizeof(zval*));

  if (Z_ARRVAL_P(array)->nNumOfElements <= 1) {  /* 什么都不做 */
    return;
  }

  /* 根据target_hash buckets的指针创建数组并排序 */
  arTmp = (struct bucketindex *) pemalloc((Z_ARRVAL_P(array)->nNumOfElements + 1) * sizeof(struct bucketindex), Z_ARRVAL_P(array)->persistent);
  if (!arTmp) {
    zval_dtor(return_value);
    RETURN_FALSE;
  }
  for (i = 0, p = Z_ARRVAL_P(array)->pListHead; p; i++, p = p->pListNext) {
    arTmp[i].b = p;
    arTmp[i].i = i;
  }
  arTmp[i].b = NULL;
  // 排序
  zend_qsort((void *) arTmp, i, sizeof(struct bucketindex), php_array_data_compare TSRMLS_CC);

  /* 遍历排序好的数组,然后删除重复的元素 */
  lastkept = arTmp;
  for (cmpdata = arTmp + 1; cmpdata->b; cmpdata++) {
    if (php_array_data_compare(lastkept, cmpdata TSRMLS_CC)) {
      lastkept = cmpdata;
    } else {
      if (lastkept->i > cmpdata->i) {
        p = lastkept->b;
        lastkept = cmpdata;
      } else {
        p = cmpdata->b;
      }
      if (p->nKeyLength == 0) {
        zend_hash_index_del(Z_ARRVAL_P(return_value), p->h);
      } else {
        if (Z_ARRVAL_P(return_value) == &EG(symbol_table)) {
          zend_delete_global_variable(p->arKey, p->nKeyLength - 1 TSRMLS_CC);
        } else {
          zend_hash_quick_del(Z_ARRVAL_P(return_value), p->arKey, p->nKeyLength, p->h);
        }
      }
    }
  }
  pefree(arTmp, Z_ARRVAL_P(array)->persistent);
}
/* }}} */

可以看到,这个函数初始化一个新的数组,然后将值拷贝到新数组,然后在45行调用排序函数对数组进行排序,排序的算法是zend引擎的块树排序算法。接着遍历排序好的数组,删除重复的元素。整个函数开销最大的地方就在调用排序函数上,而快排的时间复杂度是O(nlogn),因此,该函数的时间复杂度是O(nlogn)。

结论

因为array_unique底层调用了快排算法,加大了函数运行的时间开销,导致整个函数的运行较慢。这就是为什么array_keys比array_unique函数更快的原因。

(0)

相关推荐

  • php array_keys 返回数组的键名

    array_keys返回数组中部分的或所有的键名 说明 array array_keys ( array $array [, mixed $search_value [, bool $strict = false ]] ) array_keys() 返回 $array 数组中的数字或者字符串的键名. 如果指定了可选参数 search_value,则只返回该值的键名.否则 $array 数组中的所有键名都会被返回. 参数详解 参数 描述 array 必需.一个数组,包含了要返回的键. search

  • php 多文件上传的实现实例

    首先向大家讲解一下实现的方法. 要实现多文件上传,我们可以在form表单中添加多个input file域,然后将这些input file的name属性设置为相同的名称且使用数组的形式命名,例如filename[].至于文件上传的php代码和单个文件上传是一样的道理. 下面看一个多文件上传的实例: html文件example.html <!DOCTYPE html> <html> <head> <meta charset="UTF-8">

  • PHP获取数组中某元素的位置及array_keys函数应用

    众所周知,PHP自身内置了很多函数,这也是使用PHP能够极大提高开发效率的一个重要原因,获取数组中一元素的位置有很多方法,其中PHP自身就已经内置了一个函数array_keys(),下边的代码能够打印出所有PHP的内置函数: 复制代码 代码如下: <?php print_r(get_defined_functions()); ?> array_keys的语法如下: 复制代码 代码如下: array_keys(array,value,[strict]) 其中strict设置为true将触发数据类

  • php 修改上传文件大小限制实例详解

    1. 修改 max_execution_time 在php中,默认的页面最久执行时间为 30 秒,超过30秒,该脚本就停止执行. 这样就会出现无法打开网页的情况.这时我们可以修改 max_execution_time 在php.ini里查找 max_execution_time 默认是30秒.改为 max_execution_time = 0 0表示没有限制 2. 修改 post_max_size post_max_size 设定 POST 数据所允许的最大大小.此设定也影响到文件上传. php

  • php 页面之间传值的三种方法实例代码

    在项目开发中经常见到不同页面之间传值在web工作中,本篇文章给大家列出了三种常见的方式. 一. POST传值 post传值是用于html的<form>表单跳转的方法,很方便使用.例如: <html> <form action='' method=''> <input type='text' name='name1'> <input type='hidden' name='name2' value='value'> <input type='

  • 详解php中空字符串和0之间的关系

    前言 最近在处理关于经纬度的问题时,在建表的时候,选择用字符串varchar存储经度.纬度.为以后的问题埋下伏笔.下面话不多说,我们来看看详细的介绍. $_x=$row["x"]; $_y=$row["y"]; if(isset($_x) && isset($_y)){ if($row["y"] == 0 || $row["x"] == 0){ $d=$this->getDistance($row[&qu

  • php数组函数序列之array_keys() - 获取数组键名

    array_keys() 定义和用法 array_keys() 函数返回包含数组中所有键名的一个新数组. 如果提供了第二个参数,则只返回键值为该值的键名. 如果 strict 参数指定为 true,则 PHP 会使用全等比较 (===) 来严格检查键值的数据类型. 语法 array_keys(array,value) 参数 描述 array 必需.规定输入的数组. value 可选.指定值的索引(键). strict 可选.与 value 参数一起使用.可能的值: true - 根据类型返回带有

  • PHP中array_keys和array_unique函数源码的分析

    性能分析 从运行性能上分析,看看下面的测试代码: $test=array(); for($run=0; $run<10000; $run++) $test[]=rand(0,100); $time=microtime(true); $out = array_unique($test); $time=microtime(true)-$time; echo 'Array Unique: '.$time."\n"; $time=microtime(true); $out=array_k

  • jQuery each函数源码分析

    jQuery.each方法用于遍历一个数组或对象,并对当前遍历的元素进行处理,在jQuery使用的频率非常大,下面就这个函数做了详细讲解: 代码 /*! * jQuery源码分析-each函数 * jQuery版本:1.4.2 * * ---------------------------------------------------------- * 函数介绍 * * each函数通过jQuery.extend函数附加到jQuery对象中: * jQuery.extend({ * each:

  • vue parseHTML 函数源码解析AST基本形成

    目录 AST(抽象语法树)? 子节点 Vue中是如何把html(template)字符串编译解析成AST 解析html 代码重新改造 接着解析 html (template)字符串 解析div AST(抽象语法树)? 在上篇文章中我们已经把整个词法分析的解析过程分析完毕了. 例如有html(template)字符串: <div id="app"> <p>{{ message }}</p> </div> 产出如下: { attrs: [&q

  • vue parseHTML函数源码解析start钩子函数

    目录 正文 platformGetTagNamespace 源码 isForbiddenTag 函数 addIfCondition是什么 processIfConditions 源码 正文 接上章节:parseHTML 函数源码解析 AST 预备知识 现在我们就可以愉快的进入到Vue start钩子函数源码部分了. start: function start(tag, attrs, unary) { // check namespace. // inherit parent ns if ther

  • vue parseHTML函数源码解析 AST预备知识

    目录 正文 createASTElement函数 解析指令所用正则 parse 函数中的变量 正文 接上章节:parseHTML 函数源码解析AST 基本形成 在正式扎进Vue parse源码之前,我们先了解下他周边的工具函数, 这能帮我们快速的去理解阅读. 还记得我们在上章节讲的element元素节点的描述对象吗? var element = { type: 1, tag: tag, parent: null, attrsList: attrs, children: [] } 在源码中定义了一

  • vue parseHTML 函数源码解析

    目录 正文 函数开头定义的一些常量和变量 while 循环 textEnd ===0 parseStartTag 函数解析开始标签 总结: 正文 接上篇: Vue编译器源码分析AST 抽象语法树 function parseHTML(html, options) { var stack = []; var expectHTML = options.expectHTML; var isUnaryTag$$1 = options.isUnaryTag || no; var canBeLeftOpen

  • FilenameUtils.getName 函数源码分析

    目录 一.背景 二.源码分析 2.1 问题1:为什么需要 NonNul 检查 ? 2.1.1 怎么检查的? 2.1.2 为什么要做这个检查呢? 2.2 问题2: 为什么不根据当前系统类型来获取分隔符? 三.Zoom Out 3.1 代码健壮性 3.2 代码严谨性 3.3 如何写注释 四.总结 一.背景 最近用到了 org.apache.commons.io.FilenameUtils#getName 这个方法,该方法可以传入文件路径,获取文件名. 简单看了下源码,虽然并不复杂,但和自己设想略有区

  • Vue中之nextTick函数源码分析详解

    1. 什么是Vue.nextTick()? 官方文档解释如下: 在下次DOM更新循环结束之后执行的延迟回调.在修改数据之后立即使用这个方法,获取更新后的DOM. 2. 为什么要使用nextTick? <!DOCTYPE html> <html> <head> <title>演示Vue</title> <script src="https://tugenhua0707.github.io/vue/vue1/vue.js"&

  • Ruby实现命令行中查看函数源码的方法

    如果要查看 ActiveRecord 的 update_attribute 函数的源代码,一个比较常见的方法是直接在 Rails 源码中搜索 def update_attribute.博客 The Pragmatic Studio 介绍了一个更方便的技巧,在 Ruby 命令行中就能启动编辑器直接访问. 通过 Object#method 方法可以获得 update_attribute 方法的对象,而 Method#source_location 则返回这个方法定义的文件和位置.有了这个信息后,就能

  • Django contrib auth authenticate函数源码解析

    引言 django提供了一个默认的auth系统用于用户的登录和授权,并提供了一定的扩展性,允许开发者自行定义多个验证后台,每个验证后台必须实现authenticate函数,并返回None或者User对象. 默认的后台是django.contrib.auth.backends.ModelBackend,该后台通过用户名和密码进行用户的验证,以settings.AUTH_USER_MODEL作为模型.但是在实际的开发中,相信大家都不会固定的使用用户名以及同一个model进行验证,比如,不同的角色需要

随机推荐