PHP數組如何在C級上實現？

Question

PHP array是PHP的核心功能之一。它很稀疏，允許在同一個數組中使用多類型鍵，並且支持集合，字典，數組，堆棧/隊列和迭代功能。

但是在使用PHP一段時間後，我發現array_*函數中的相當一部分比第一眼看得慢得多。就像在非常大的陣列（10000+）上的array_rand一樣。 array_rand實際上非常慢，在使用php數組作爲索引數組的情況下，像rand(0, array_length($array) - 1)這樣的函數的運行速度要快於array_rand。

現在到我的問題。

如何在C級別上實現PHP數組？這對預測大量使用PHP數組數據類型的不同功能的函數的大O很有幫助。

Answer 1

PHP關聯數組實際上是HashTables的實現。

在內部，可以製作數值數組或關聯數組。 如果你把它們結合起來，它就是關聯數組。

在數值數組中，它非常類似於C.您有指向ZVAL結構體的指針數組。因爲指針具有固定長度（我們稱它爲n），所以偏移量（x）的計算很容易：x * n。

在PHP中，類型是ZVAL結構體（因爲它實現動態類型），但它也有助於關聯數組，因爲您可以假定爲固定長度。所以即使直接訪問數組速度較慢，它仍然被認爲是O（1）。

那麼在字符串鍵中會發生什麼？ PHP使用散列函數將它們轉換爲整數。

在數字和關聯數組中搜索具有相似的效率，因爲它們在內部都是數字的。

由於額外的級別（散列函數），只能直接訪問數組鍵。

Answer 2

在文檔中查看此評論，以確認array_rand的問題，儘管對於小陣列來說速度很快，但擴展性很差。

我改性fake_array_rand總是隻返回1個元件，並做了一些針對基準調用array_rand與爲1。我跑100個樣本爲元件的每個號碼的各功能，並採取了平均結果的第二個參數。雖然內部array_rand對於少數元素來說速度更快，但其比例很差。

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

Answer 3

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

我不知道C，但對我來說，它看起來像一個鏈接的哈希表。

Answer 4

由於PHP數組are ordered maps（即使使用連續的整數索引）array_rand()可能不得不考慮從中選擇元素的鍵列表。我猜測，如果緩存（通常是無效的）密鑰列表會導致空間和時間過於縮短，所以每次調用至少需要O（n）遍歷和建設成本。

因爲您的rand(... length ...)實施利用了您所擁有的關鍵是連續整數的特殊知識，您將獲得O（log n）查找成本。這似乎與Chacha102的數據一致。

Answer 5

在閱讀了zend/zend_hash.h和ext/standard/array.c之後，我想我已經找到了答案（謝謝Chris和gumbo的建議）。

PHP數組是一個鏈式哈希表（在關鍵衝突中查找O（c）和O（n）），允許使用int和string鍵。它使用2種不同的哈希算法將兩種類型合併到相同的哈希鍵空間中。另外，存儲在散列中的每個值都與其之前存儲的值以及存儲在（鏈接列表）之後的值鏈接。它還有一個臨時指針，用於保存當前項目，以便迭代散列。

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）或關閉）。

總之： 我希望有在將在其中陣列是使用array_push或array[] = $value創建情況下，將允許用於縮放像C數組代替鏈接的設置了Zend哈希表的數據結構的透明標誌名單。