如何在C级上实现PHP数组？

Question

PHP array是PHP的核心功能之一.它是稀疏的,允许同一数组中的多类型键,并支持集合,字典,数组,堆栈/队列和迭代功能.

但是在使用PHP一段时间之后,我发现很多array_*功能都比你初看起来慢得多.就像在array_rand一个非常大的阵列(10000+)的情况下.array_rand实际上是这么慢,在你使用php数组作为索引数组的情况下,像rand( 0, array_length( $array ) - 1 )运行MUCH 的函数要快array_rand.

现在我的问题.

如何在C级上实现PHP数组？这对于预测大量使用PHP数组数据类型的不同功能的函数的Big O非常有用.

Answer 1

阅读完zend/zend_hash.h和ext/standard/array.c之后,我想我找到了答案(谢谢Chris和gumbo的建议).

PHP数组是一个链式哈希表(在键冲突上查找O(c)和O(n)),它允许使用int和string键.它使用2种不同的散列算法将这两种类型拟合到相同的散列键空间中.此外,存储在散列中的每个值都链接到它之前存储的值和存储在(链接列表)之后的值.它还有一个临时指针,用于保存当前项,以便可以迭代哈希.

用于捕捉array_rand功能是,为了确保该键是真正随机的,该array_rand函数必须遍历阵列rand(0, count($array))倍(O(N)).这是因为在O(c)时间内无法移动到散列表中的偏移量,因为无法保证该范围内没有丢失的键.

这个发现让我感到有些困扰,因为这意味着PHP中没有数据类型具有正常的C数组特征.现在大部分时间都没问题,因为哈希查找速度非常快,但是在类似情况下会出现故障array_rand.

让我困扰的另一件事是执行array_key_exists和之间的区别in_array.array_key_exists使用哈希查找(大部分时间为O(c))来查看密钥是否在数组中,而in_array必须线性搜索哈希值(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(尽管是令人烦恼的长名称)非常快(O(c)或接近).

总结:我希望zend HashTable数据结构中有一个透明标志,在使用array_push或者array[] = $value允许像C数组而不是链表一样扩展的情况下设置.

Answer 2

PHP关联数组实际上是HashTables的实现.

在内部,可以制作数字数组或关联数组.如果将它们组合在一起,则它是关联数组.

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

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

在PHP中,类型是ZVAL结构(因为它实现了动态类型),但它也有助于关联数组,因为你可以假设固定长度.因此,即使直接访问数组较慢,它仍然被认为是O(1).

那么字符串键会发生什么？PHP使用哈希函数将它们转换为整数.

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

由于附加级别(散列函数),只能直接访问数组键.

Answer 3

由于PHP数组是有序映射(即使使用连续的整数索引),array_rand()可能必须通过一系列键来选择元素.我猜测缓存(经常无效的)密钥列表将是空间和时间无效,因此每次调用将至少产生O(n)遍历和建设成本.

因为您的rand(... length ...)实现利用了您所拥有的特殊知识,即密钥是连续的整数,所以您将获得O(log n)查找成本.这似乎与Chacha102的数据一致.