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

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

1. $test=array(); 
2.  
3. for($run=0; $run<10000; $run++) 
4.  
5. $test[]=rand(0,100); 
6.  
7. $time=microtime(true); 
8.  
9. $out = array_unique($test); 
10.  
11. $time=microtime(true)-$time; 
12.  
13. echo 'Array Unique: '.$time."/n"; 
14.  
15. $time=microtime(true); 
16.  
17. $out=array_keys(array_flip($test)); 
18.  
19. $time=microtime(true)-$time; 
20.  
21. echo 'Keys Flip: '.$time."/n"; 
22.  
23. $time=microtime(true); 
24.  
25. $out=array_flip(array_flip($test)); 
26.  
27. $time=microtime(true)-$time; 
28.  
29. 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底层，这两个函数是怎么实现的。

源码分析:

1. /* {{{ proto array array_keys(array input [, mixed search_value[, bool strict]]) 
2.  
3.   Return just the keys from the input array, optionally only for the specified       search_value */ 
4.  
5. PHP_FUNCTION(array_keys) 
6.  
7. { 
8.  
9.   //变量定义 
10.  
11.   zval *input,        /* Input array */ 
12.  
13.      *search_value = NULL,  /* Value to search for */ 
14.  
15.      **entry,        /* An entry in the input array */ 
16.  
17.       res,          /* Result of comparison */ 
18.  
19.      *new_val;        /* New value */ 
20.  
21.   int  add_key;        /* Flag to indicate whether a key should be added */ 
22.  
23.   char *string_key;      /* String key */ 
24.  
25.   uint  string_key_len; 
26.  
27.   ulong num_key;        /* Numeric key */ 
28.  
29.   zend_bool strict = 0;    /* do strict comparison */ 
30.  
31.   HashPosition pos; 
32.  
33.   int (*is_equal_func)(zval *, zval *, zval * TSRMLS_DC) = is_equal_function; 
34.  
35.   
36.  
37.   //程序解析参数 
38.  
39.   if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a|zb", &input, &search_value, &strict) == FAILURE) { 
40.  
41.     return; 
42.  
43.   } 
44.  
45.   
46.  
47.   // 如果strict是true，则设置is_equal_func为is_identical_function，即全等比较 
48.  
49.   if (strict) { 
50.  
51.     is_equal_func = is_identical_function; 
52.  
53.   } 
54.  
55.   
56.  
57.   /* 根据search_vale初始化返回的数组大小 */ 
58.  
59.   if (search_value != NULL) { 
60.  
61.     array_init(return_value); 
62.  
63.   } else { 
64.  
65.     array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL_P(input))); 
66.  
67.   } 
68.  
69.   add_key = 1; 
70.  
71.   
72.  
73.   /* 遍历输入的数组参数，然后添加键值到返回的数组 */ 
74.  
75.   zend_hash_internal_pointer_reset_ex(Z_ARRVAL_P(input), &pos);//重置指针 
76.  
77.   //循环遍历数组 
78.  
79.   while (zend_hash_get_current_data_ex(Z_ARRVAL_P(input), (void **)&entry, &pos) == SUCCESS) { 
80.  
81.     // 如果search_value不为空 
82.  
83.     if (search_value != NULL) { 
84.  
85.       // 判断search_value与当前的值是否相同，并将比较结果保存到add_key变量 
86.  
87.       is_equal_func(&res, search_value, *entry TSRMLS_CC); 
88.  
89.       add_key = zval_is_true(&res); 
90.  
91.     } 
92.  
93.   
94.  
95.     if (add_key) { 
96.  
97.       // 创建一个zval结构体 
98.  
99.       MAKE_STD_ZVAL(new_val); 
100.  
101.   
102.  
103.       // 根据键值是字符串还是整型数字将值插入到return_value中 
104.  
105.       switch (zend_hash_get_current_key_ex(Z_ARRVAL_P(input), &string_key, &string_key_len, &num_key, 1, &pos)) { 
106.  
107.         case HASH_KEY_IS_STRING: 
108.  
109.           ZVAL_STRINGL(new_val, string_key, string_key_len - 1, 0); 
110.  
111.           // 此函数负责将值插入到return_value中，如果键值已存在，则使用新值更新对应的值，否则直接插入 
112.  
113.           zend_hash_next_index_insert(Z_ARRVAL_P(return_value), &new_val, sizeof(zval *), NULL); 
114.  
115.           break; 
116.  
117.   
118.  
119.         case HASH_KEY_IS_LONG: 
120.  
121.           Z_TYPE_P(new_val) = IS_LONG; 
122.  
123.           Z_LVAL_P(new_val) = num_key; 
124.  
125.           zend_hash_next_index_insert(Z_ARRVAL_P(return_value), &new_val, sizeof(zval *), NULL); 
126.  
127.           break; 
128.  
129.       } 
130.  
131.     } 
132.  
133.  //Vevb.com 
134.  
135.     // 移动到下一个 
136.  
137.     zend_hash_move_forward_ex(Z_ARRVAL_P(input), &pos); 
138.  
139.   } 
140.  
141. } 
142.  
143. /* }}} */ 

以上是array_keys函数底层的源码。为方便理解，笔者添加了一些中文注释。如果需要查看原始代码，可以点击查看。这个函数的功能就是新建一个临时数组，然后将键值对重新复制到新的数组，如果复制过程中有重复的键值出现，那么就用新的值替换。

这个函数的主要步骤是地57和63行调用的zend_hash_next_index_insert函数。该函数将元素插入到数组中，如果出现重复的值，则使用新的值更新原键值指向的值，否则直接插入，时间复杂度是O(n)。

1. /* {{{ proto array array_flip(array input) 
2.  
3.   Return array with key <-> value flipped */ 
4.  
5. PHP_FUNCTION(array_flip) 
6.  
7. { 
8.  
9.   // 定义变量 
10.  
11.   zval *array, **entry, *data; 
12.  
13.   char *string_key; 
14.  
15.   uint str_key_len; 
16.  
17.   ulong num_key; 
18.  
19.   HashPosition pos;  
20.  
21.   // 解析数组参数 
22.  
23.   if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a", &array) == FAILURE) { 
24.  
25.     return; 
26.  
27.   }
28.   
29.  
30.   // 初始化返回数组 
31.  
32.   array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL_P(array))); 
33.  
34.   // 重置指针 
35.  
36.   zend_hash_internal_pointer_reset_ex(Z_ARRVAL_P(array), &pos); 
37.  
38.   // 遍历每个元素，并执行键<->值交换操作 
39.  
40.   while (zend_hash_get_current_data_ex(Z_ARRVAL_P(array), (void **)&entry, &pos) == SUCCESS) { 
41.  
42.     // 初始化一个结构体 
43.  
44.     MAKE_STD_ZVAL(data); 
45.  
46.     // 将原数组的值赋值为新数组的键 
47.  
48.     switch (zend_hash_get_current_key_ex(Z_ARRVAL_P(array), &string_key, &str_key_len, &num_key, 1, &pos)) { 
49.  
50.       case HASH_KEY_IS_STRING: 
51.  
52.         ZVAL_STRINGL(data, string_key, str_key_len - 1, 0); 
53.  
54.         break; 
55.  
56.       case HASH_KEY_IS_LONG: 
57.  
58.         Z_TYPE_P(data) = IS_LONG; 
59.  
60.         Z_LVAL_P(data) = num_key; 
61.  
62.         break; 
63.  
64.     }  
65.     // 将原数组的键赋值为新数组的值，如果有重复的，则使用新值覆盖旧值 
66.  
67.     if (Z_TYPE_PP(entry) == IS_LONG) { 
68.  
69.       zend_hash_index_update(Z_ARRVAL_P(return_value), Z_LVAL_PP(entry), &data, sizeof(data), NULL); 
70.  
71.     } else if (Z_TYPE_PP(entry) == IS_STRING) { 
72.  
73.       zend_symtable_update(Z_ARRVAL_P(return_value), Z_STRVAL_PP(entry), Z_STRLEN_PP(entry) + 1, &data, sizeof(data), NULL); 
74.  
75.     } else { 
76.  
77.       zval_ptr_dtor(&data); /* will free also zval structure */ 
78.  
79.       php_error_docref(NULL TSRMLS_CC, E_WARNING, "Can only flip STRING and INTEGER values!"); 
80.  
81.     } 
82.  
83.     // 下一个 
84.  
85.     zend_hash_move_forward_ex(Z_ARRVAL_P(array), &pos); 
86.  
87.   } 
88.  
89. } 
90.  
91. /* }}} */ 

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

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

1. /* {{{ proto array array_unique(array input [, int sort_flags]) 
2.  
3.   Removes duplicate values from array */ 
4.  
5. PHP_FUNCTION(array_unique) 
6.  
7. { 
8.  
9.   // 定义变量 
10.  
11.   zval *array, *tmp; 
12.  
13.   Bucket *p; 
14.  
15.   struct bucketindex { 
16.  
17.     Bucket *b; 
18.  
19.     unsigned int i; 
20.  
21.   }; 
22.  
23.   struct bucketindex *arTmp, *cmpdata, *lastkept; 
24.  
25.   unsigned int i; 
26.  
27.   long sort_type = PHP_SORT_STRING; 
28.  
29.   
30.  
31.   // 解析参数 
32.  
33.   if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a|l", &array, &sort_type) == FAILURE) { 
34.  
35.     return; 
36.  
37.   } 
38.  
39.   
40.  
41.   // 设置比较函数 
42.  
43.   php_set_compare_func(sort_type TSRMLS_CC); 
44.  
45.   
46.  
47.   // 初始化返回数组 
48.  
49.   array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL_P(array))); 
50.  
51.   // 将值拷贝到新数组 
52.  
53.   zend_hash_copy(Z_ARRVAL_P(return_value), Z_ARRVAL_P(array), (copy_ctor_func_t) zval_add_ref, (void *)&tmp, sizeof(zval*)); 
54.  
55.   
56.  
57.   if (Z_ARRVAL_P(array)->nNumOfElements <= 1) {  /* 什么都不做 */ 
58.  
59.     return; 
60.  
61.   } 
62.  
63.   
64.  
65.   /* 根据target_hash buckets的指针创建数组并排序 */ 
66.  
67.   arTmp = (struct bucketindex *) pemalloc((Z_ARRVAL_P(array)->nNumOfElements + 1) * sizeof(struct bucketindex), Z_ARRVAL_P(array)->persistent); 
68.  
69.   if (!arTmp) { 
70.  
71.     zval_dtor(return_value); 
72.  
73.     RETURN_FALSE; 
74.  
75.   } 
76.  
77.   for (i = 0, p = Z_ARRVAL_P(array)->pListHead; p; i++, p = p->pListNext) { 
78.  
79.     arTmp[i].b = p; 
80.  
81.     arTmp[i].i = i; 
82.  
83.   } 
84.  
85.   arTmp[i].b = NULL; 
86.  
87.   // 排序 
88.  
89.   zend_qsort((void *) arTmp, i, sizeof(struct bucketindex), php_array_data_compare TSRMLS_CC); 
90.  
91.   
92.  
93.   /* 遍历排序好的数组，然后删除重复的元素 */ 
94.  
95.   lastkept = arTmp; 
96.  
97.   for (cmpdata = arTmp + 1; cmpdata->b; cmpdata++) { 
98.  
99.     if (php_array_data_compare(lastkept, cmpdata TSRMLS_CC)) { 
100.  
101.       lastkept = cmpdata; 
102.  
103.     } else { 
104.  
105.       if (lastkept->i > cmpdata->i) { 
106.  
107.         p = lastkept->b; 
108.  
109.         lastkept = cmpdata; 
110.  
111.       } else { 
112.  
113.         p = cmpdata->b; 
114.  
115.       } 
116.  
117.       if (p->nKeyLength == 0) { 
118.  
119.         zend_hash_index_del(Z_ARRVAL_P(return_value), p->h); 
120.  
121.       } else { 
122.  
123.         if (Z_ARRVAL_P(return_value) == &EG(symbol_table)) { 
124.  
125.           zend_delete_global_variable(p->arKey, p->nKeyLength - 1 TSRMLS_CC); 
126.  
127.         } else { 
128.  
129.           zend_hash_quick_del(Z_ARRVAL_P(return_value), p->arKey, p->nKeyLength, p->h); 
130.  
131.         } 
132.  
133.       } 
134.  
135.     } 
136.  
137.   } 
138.  
139.   pefree(arTmp, Z_ARRVAL_P(array)->persistent); 
140.  
141. } 
142.  
143. /* }}} */ 

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

结论:

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