如何在C级别上实现PHP数组?

PHP array是PHP的核心function之一。 它是稀疏的,可以在同一个数组中使用多types的键,并支持集合,字典,数组,堆栈/队列和迭代function。

但是在使用PHP一段时间之后,我发现相当多的array_*函数比乍看起来要慢得多。 就像array_rand在一个非常大的数组(10000+)上一样。 array_rand实际上太慢了,在使用php数组作为索引数组的情况下,类似rand( 0, array_length( $array ) - 1 )的函数比array_rand快得多。

现在到我的问题。

PHP数组如何在C级上实现? 这对预测大量使用PHP数组数据types的不同function的函数的大O很有帮助。

PHP关联数组实际上是HashTable的实现。

在内部,可以制作数字数组或关联数组。 如果你把它们结合起来,那就是关联数组。

在数值数组中,它与C非常类似。您有指向ZVAL结构体的指针数组。

因为指针具有固定长度(我们称之为n),所以偏移(x)计算很容易:x * n。

在PHPtypes中,ZVAL结构体(因为它实现了dynamictypes),但是它也有助于关联数组,因为您可以假定为固定长度。 所以即使直接访问数组速度较慢,仍然被认为是O(1)。

那么在string键中会发生什么? PHP使用散列函数将它们转换为整数。

在数字和关联数组中search具有相似的效率,因为它们在内部都是数字的。

只有直接访问数组键的速度较慢,因为附加的级别(散列函数)。

读过zend / zend_hash.h和ext / standard / array.c后,我想我已经find了答案(谢谢Chris和gumbo的build议)。

PHP数组是一个链式哈希表(在关键冲突中查找O(c)和O(n)),允许int和string键。 它使用2种不同的哈希algorithm将两种types合并到相同的哈希键空间中。 此外,存储在散列中的每个值都链接到存储在其之前的值和(链接列表)之后存储的值。 它也有一个临时指针,用来保存当前项目,所以哈希可以迭代。

array_rand函数的捕获是为了确保key是真正随机的, array_rand函数必须遍历数组rand(0, count($array))次(O(n))。 这是因为无法在O(c)时间移动到哈希表中的偏移量,因为不能保证范围内没有丢失键。

这个发现有点困扰我,因为这意味着在PHP中没有数据types具有正常的C数组特性。 现在大多数情况下这是可以的,因为哈希查找速度非常快,但是在array_rand情况下会显示错误。

另一件令我困扰的事情是array_key_existsin_array之间的区别。 array_key_exists使用散列查找(大部分时间O(c))来查看一个键是否在数组中,而in_array必须线性search散列(O(n))。

考虑下面的两个例子:

in_array版本

 $array = range(0, 100000); if( in_array( $random_key, $array ) ) { //we found a value } 

array_key_exists版本

 $array = array_fill_keys( range(0, 100000), NULL ); if( array_key_exists( $random_key, $array ) ) { //we found a value, err key } 

虽然in_array版本看起来更简洁易懂,但对于大型数组(O(n)),其实array_key_exists(尽pipe名字很长)很快(O(c)或close)。

总之:我希望在zend HashTable数据结构中有一个透明标志,在数组使用array_pusharray[] = $value创build的情况下,将会设置这个标志,这样可以像C数组一样进行缩放,而不是链接名单。

由于PHP数组是有序的映射 (即使使用连续的整数索引), array_rand()可能必须提供一个键列表来select一个元素。 我猜测,如果caching(通常是无效的)密钥列表,那么每个调用至less会产生O(n)的遍历和构build成本将会是空间和时间上的无效。

因为你的rand(... length ...)实现利用了你所拥有的关键是连续整数的特殊知识,所以你会得到O(log n)查找开销。 这似乎与Chacha102的数据一致。

在文档中看到这个评论,确认array_rand的两难处境,而对于小数组来说,很快就会缩小。

我修改了fake_array_rand总是只返回1个元素,并且做了一些基准来调用array_rand,第二个参数是1.我为每个元素的每个元素运行100个样本,并取平均值。 虽然内部array_rand对于less数元素来说速度更快,但是其比例很差。

 1 elements: 2.0619630813599E-05 sec. for array_rand,8.4352493286133E-05 sec. for fake_array_rand 10 elements: 2.1675825119019E-05 sec. for array_rand,8.427619934082E-05 sec. for fake_array_rand 100 elements: 2.9319524765015E-05 sec. for array_rand,8.4599256515503E-05 sec. for fake_array_rand 1000 elements: 0.0001157283782959 sec. for array_rand,8.5572004318237E-05 sec. for fake_array_rand 10000 elements: 0.0016669762134552 sec. for array_rand,8.5201263427734E-05 sec. for fake_array_rand 100000 elements: 0.015599734783173 sec. for array_rand,8.5580348968506E-05 sec. for fake_array_rand 1000000 elements: 0.18011983394623 sec. for array_rand,8.6690187454224E-05 sec. for fake_array_rand <?php function fake_array_rand ($array) { $count = count ($array); # Help keep the number generator random :) $randval and usleep ("0.$randval"); # Seed the random number generator # Generate a random number srand ((double) microtime() * 10000000); $randval = rand(); # Use the random value to 'pick' an entry from the array # Count the number of times that the entry is picked ++$index[$randval % $count]; return $array[$randval % $count]; } ?> 

http://us.php.net/manual/en/function.array-rand.php#22360

看看zend / zend_hash.c和zend / zend_hash.h

我不知道C,但对我来说,它看起来像一个链式哈希表。