技術文章 » 詳解PHP的資料結構擴充套件

詳解PHP的資料結構擴充套件

2020-07-16 10:06:16

宣告: 本文採用 CC BY-NC-ND 4.0 授權。

在 PHP 中表示集合的資料型別就一種：Array。相信每個初學 PHP 的都會對它感到疑惑。這個東西看起來應該和其他語言中的 Array 或者 List 一樣，但在 PHP 中，它是一切，即是 List，也是 Map：

<?php
$a = array(1, 2, 3);
$b = array('key1' => 1, 'key2' => 2);

這聽起來似乎很好，反正大家都使用同一種資料結構，偶爾情況下才會有些效能問題，況且升級 PHP7 之後 Array 的效能也提高了，實在不濟還可以加記憶體。但如果我們可以通過引入更便利的資料結構優化效能，同時寫程式碼反而更方便了，那何樂而不為呢?

推薦教學：《PHP教學》

Array 的缺點

有些時候我們需要儲存一個集合（Set），但是 Array 並不能保證元素的唯一性，array_unique 有不可避免的效能損耗。一種折衷方案是，將元素當做 key，同時 value 為 true 來曲線實現 Unique Array 的功能：

<?php
$users = User::find($ids);
$res = [];
foreach ($users as $user) {
  $res[$user->id] = true;
}

PHP 的 Array 存取不存在的 key 可以得到 null，不會產生 fatal error，但會有一個 E_NOTICE。這個 E_NOTICE 會被 set_error_handler 註冊的函數截獲。顯然，這種程式碼上的不乾淨和效能上的無謂開銷完全是可以避免的。

<?php
$req = [];
$req['user_id']; // PHP Notice:  Undefined offset

可以用 array_key_exists 和 if else 來讓程式碼乾淨一些，但這樣就顯得囉嗦了。

array 的一些函數式方法很難用，比如 array_map, array_walk 等，寫起來也很醜陋。當然這一點原生 PHP 沒什麼好方法，畢竟 PHP 的物件導向的基因不是很強。

<?php
array_map(function($user){
  return $user->is_deleted();
}, $users);
// 就是這麼難看
users.map { |user| user.is_deleted? }
# ruby 的就好看多了

在某些情況下，使用 Array 效能很差1，比如下面這段程式碼：

<?php
$a=[1,2,3,4,5,6,7];
echo $a[5];
// 6
array_unshift($a, 0);
// $a: [0,1,2,3,4,5,6,7];
echo $a[5];
// 5

看起來似乎沒什麼，但需要注意的是，Array 本質上是一個 Map，unshift 一個元素進來，將會改變每個元素的 key，這是一個 $O(n)$ 操作。另外，PHP 的 Array 將其 value(包擴 key 和 它的 hash) 儲存在一個 bucket 中，所以我們需要檢視每一個 bucket 並更新 hash。PHP 內部其實是通過建立新的 array 來做 array_unshift 操作的，其效能問題可想可知2。

其他缺點不一而足。

PHP 資料結構外掛

Array 飽受詬病，就會出現替代方案。PHP5 有spl，但是有些場景效能很差，且設計的很不好1。laravel 的 Collection 提供了更好用的 Map，但畢竟只是一種單一的資料結構，而且對 orm 操作設計了不少特有的介面，其用途受到限制。

PHP7 新增的 Data Structures 外掛（簡稱 ds）是 PHP 下一個優秀的補充，它充分考慮了便利、安全和整潔的需求。如下圖所示。

e6ab0f324eb5a7a3e2d8a1a26849e52.png

它提供了 3 個介面類：Collection, Sequence, Hashable 和 7 個實現類（final class）：Vector, Deque, Map, Set, Stack, Queue, PriorityQueue。

介面

Collection 是基礎介面，定義了一個資料集合（這裡的集合指的是 Collection，不是 Set） 的基本操作，比如 foreach, json_encode, var_dump 等。

<?php
$sequence = new DsVector([1, 2, 3]);
json_encode($sequence);

Sequence 是類陣列資料結構的基礎介面，定義了很多重要且方便的方法，比如 contains, map, filter, reduce, find, first, last 等。從圖中可知，Vector, Deque, Stack, Queue 都直接或者間接的實現了這個介面。

<?php
$sequence = new DsVector([1, 2, 3]);

print_r($sequence->map(function($value) { return $value * 2; }));
print_r($sequence);
?>

Hashable 在圖中看起來比較孤立，但對於 Map 和 Set 很重要。一個 Object 如果實現了 Hashable，就可以作為 Map 的 key，可以作為 Set 的元素。這樣 Map 和 Set 就能像 Java 一樣方便的使用了。

實現類

Vector 應該是最為常用的資料結構之一了，可以把它當成 Ruby 的 Array 或者 Python 的 List。其元素的值的 index 就是它在 buffer 中的 index，所以效率很高。只要有使用陣列的需求且不需要 insert, remove, shift 和 unshift 的都可以用它。

Deque([dek]) 是雙端佇列，在 Vector 的基礎上增加了一個頭指標，因此 shift 和 unshift 也是 $O(1)$ 複雜度了。但帶來的效能損耗並不多，因此也有討論是不是只需要一個 Deque 就夠了，不需要 Vector（討論）3。

Stack 棧，嗯沒什麼好說的，它繼承自 Collection，但內部使用 Vector 實現。這樣做的好處是實現方便，且同時可以遮蔽不需要的和不應該出現的方法。

Queue 佇列，內部使用 Deque 實現。

PriorityQueue，最大堆實現。

Map。以前使用 Array 來實現 map 的地方，改用 Map 更好。二者效能幾乎一致，但 Map 對記憶體的管理更好。而且，Map 的語法要更加友好。

<?php
$req = [];
$req['user_id']; // PHP Notice:  Undefined offset

$req = new DsMap(["a" => 1, "b" => 2, "c" => 3]);
$req->get('user_id');// OutOfBoundsException
$req->get('user_id', 0); // 0 是預設值
// 即可以方便的指定預設值，也可以選擇丟擲異常。不用 array，不會產生 E_NOTICE

$req->keys();

$req->map(function($key, $value) { return $value * 2; });

不僅如此，只要 object 繼承了 Hashable，Map 還允許使用 object 作為 key。

<?php
class Photo implements DsHashable {
    
    public function __construct($id) {
        $this->id = $id;
    }
    
    public function hash() {
        return $this->id;
    }

    public function equals($obj): bool {
        return $this->id === $obj->id;
    }
}

$p1 = new Photo(1);
$p2 = new Photo(2);

$map = new DsMap();
$map->put($p1, 1);
$map->put($p2, 2);

Set 集合是一種元素唯一的資料結構。和 array_unique 相比效能有很大提升，而且用法也更加優雅1。

<?php
$set = new DsSet();
$set->add($p1);
$set->add($p2);

  1. php ds 外掛效能測試 ? ?2 ?3

  2. 當然，這一點可能稍嫌牽強，畢竟即使是資料量很大的情況下，array_unshift 的耗時也沒有那麼大 ?

  3. github 上還在討論可以增加一個不可變型別 Tuple，以及取消 Vector 直接使用 Deque，討論地址和 2.0API 計劃 ?

以上就是詳解PHP的資料結構擴充套件的詳細內容，更多請關注TW511.COM其它相關文章！