Explication détaillée des extensions de structure de données PHP

Avertissement : cet article est sous licence CC BY-NC-ND 4.0.

En PHP, il n'existe qu'un seul type de données qui représente une collection : Array. Je pense que tous ceux qui découvrent PHP seront confus à ce sujet. Cette chose devrait ressembler à un tableau ou à une liste dans d'autres langages, mais en PHP, c'est tout, à la fois une liste et une carte :

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

Cela semble bien. Quoi qu'il en soit, tout le monde utilise la même structure de données. De plus, après la mise à niveau vers PHP7, les performances d'Array se sont également améliorées. . Mais si nous pouvons optimiser les performances en introduisant des structures de données plus pratiques et que l'écriture de code sera plus pratique, alors pourquoi pas ?

Tutoriel recommandé : "Tutoriel PHP"

Inconvénients de Array

Parfois, nous devons sauvegarder un ensemble (Set), mais Array ne garantit pas l'unicité des éléments, et array_unique a des pertes de performances inévitables. Un compromis consiste à utiliser l'élément comme clé et la valeur comme vraie pour réaliser la fonction de Tableau Unique :

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

Le tableau de PHP peut devenir nul lors de l'accès à une clé inexistante et ne générera pas d'erreur fatale, mais il y aura un E_NOTICE. Ce E_NOTICE sera intercepté par la fonction enregistrée par set_error_handler. De toute évidence, ce type de code impur et cette surcharge inutile en termes de performances peuvent être complètement évités.

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

Vous pouvez utiliser array_key_exists et if else pour rendre le code plus propre, mais cela semblera verbeux.

Certaines méthodes fonctionnelles de array sont difficiles à utiliser, comme array_map, array_walk, etc., et elles sont également laides à écrire. Bien sûr, il n’existe pas de bonne manière de procéder avec PHP natif. Après tout, les gènes orientés objet de PHP ne sont pas très forts.

<?php array_map(function($user){
  return $user->is_deleted();
}, $users);
// 就是这么难看

users.map { |user| user.is_deleted? }
# ruby 的就好看多了

Dans certains cas, les performances d'utilisation d'Array sont très mauvaises¹, comme le code suivant :

<?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

Cela peut sembler rien, mais il convient de noter que Array est essentiellement une carte. Déplacer un élément changera la clé de chaque élément. Il s'agit d'une opération $O(n)$. De plus, Array de PHP enregistre sa valeur (y compris la clé développée et son hachage) dans un bucket, nous devons donc vérifier chaque bucket et mettre à jour le hachage. PHP effectue en fait l'opération array_unshift en interne en créant un nouveau tableau, et ses problèmes de performances peuvent être imaginés².

Il existe bien d’autres défauts.

Plug-in de structure de données PHP

Array a été critiqué, des alternatives apparaîtront donc. PHP5 a spl, mais les performances dans certains scénarios sont très mauvaises et la conception est très mauvaise ¹. La collection de Laravel fournit une carte plus utile, mais après tout, il ne s'agit que d'une structure de données unique, et elle a conçu de nombreuses interfaces uniques pour les opérations ORM, et son utilisation est limitée.

Le nouveau plug-in Data Structures de PHP7 (ds en abrégé) est le prochain excellent ajout à PHP, qui prend pleinement en compte les besoins de commodité, de sécurité et de propreté. Comme indiqué ci-dessous.

Il fournit 3 classes d'interface : Collection, Sequence, Hashable et 7 classes d'implémentation (classe finale) : Vector, Deque, Map, Set, Stack, Queue, PriorityQueue.

Interface

Collection est l'interface de base, qui définit les opérations de base d'une collection de données (la collection fait ici référence à Collection, pas à Set), telles que foreach, json_encode, var_dump, etc.

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

La séquence est l'interface de base des structures de données de type tableau et définit de nombreuses méthodes importantes et pratiques, telles que contenir, mapper, filtrer, réduire, rechercher, premier, dernier, etc. Comme le montre la figure, Vector, Deque, Stack et Queue implémentent tous directement ou indirectement cette interface.

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

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

Hashable semble isolé dans le diagramme, mais il est important pour Map et Set. Si un objet implémente Hashable, il peut être utilisé comme clé de Map et élément de Set. De cette façon, Map et Set peuvent être utilisés aussi facilement que Java.

Classe d'implémentation

Vector devrait être l'une des structures de données les plus couramment utilisées. Vous pouvez le considérer comme Ruby's Array ou Python's List. L'index de la valeur de son élément est son index dans le tampon, c'est donc très efficace. Vous pouvez l'utiliser aussi longtemps que vous avez besoin d'utiliser un tableau et que vous n'avez pas besoin d'insérer, de supprimer, de décaler et d'annuler le décalage.

Deque([dek]) est une file d'attente à double extrémité, qui ajoute un pointeur de tête vers Vector, donc shift et unshift sont également $O(1)$ complexes. Mais la perte de performances n'est pas importante, il y a donc également une discussion pour savoir si un seul Deque est suffisant et si aucun vecteur n'est nécessaire (discussion) ³.

Stack 栈，嗯没什么好说的，它继承自 Collection，但内部使用 Vector 实现。这样做的好处是实现方便，且同时可以屏蔽不需要的和不应该出现的方法。

Queue 队列，内部使用 Deque 实现。

PriorityQueue，最大堆实现。

Map。以前使用 Array 来实现 map 的地方，改用 Map 更好。二者性能几乎一致，但 Map 对内存的管理更好。而且，Map 的语法要更加友好。

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

$req = new \Ds\Map(["a" => 1, "b" => 2, "c" => 3]);
$req->get(&#39;user_id&#39;);// OutOfBoundsException
$req->get(&#39;user_id&#39;, 0); // 0 是默认值
// 即可以方便的指定默认值，也可以选择抛出异常。不用 array，不会产生 E_NOTICE

$req->keys();

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

不仅如此，只要 object 继承了 Hashable，Map 还允许使用 object 作为 key。

<?php
class Photo implements \Ds\Hashable {
    
    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 Ds\Map();
$map->put($p1, 1);
$map->put($p2, 2);

Set 集合是一种元素唯一的数据结构。和 array_unique 相比性能有很大提升，而且用法也更加优雅¹。

<?php
$set = new Ds\Set();
$set->add($p1);
$set->add($p2);

1. php ds 插件性能测试 ↩ ↩²  ↩³

2. 当然，这一点可能稍嫌牵强，毕竟即使是数据量很大的情况下，array_unshift 的耗时也没有那么大 ↩

3. github 上还在讨论可以增加一个不可变类型 Tuple，以及取消 Vector 直接使用 Deque，讨论地址和 2.0API 计划 ↩