PHP7.2 Data Structures 使用

1. 安装

pecl install ds

Salin selepas log masuk

brew install homebrew/php/php71-ds

Salin selepas log masuk

目前PHP7.2不支持使用 brew 安装。

2. PHP 原始的数据结构`Array`

PHP5.x 的时代，Array是唯一的表示集合的数据类型，在 PHP 中，他既是 List 也是 Map，他就是一切。

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

Salin selepas log masuk

这种数据类型的确是给开发者带来了便捷性，但让PHPer 会主键的忽略掉数据结构带来的好处，特别是在学习其他的语言时，给PHPer 带来困扰。

在 PHP 升级到7后，Array也同时得到了优化，但是他的结构并没有发生变化， “optimised for everything; optimised for nothing” with room for improvement。那如果我们可以通过引入更便利的数据结构优化性能，同时写代码反而更方便了，那何乐而不为呢?

“SPL数据结构怎么样？”
Unfortunately they are terrible. They did offer some benefits prior to PHP 7, but have since been neglected to the point of having no practical value.
“我们为什么不能修正和改进它们？”
We could, but I believe their design and implementation is so poor that it would be better to replace them with something brand new.

“SPL数据结构的设计非常可怕。” - 安东尼费拉拉

Array 缺点

PHP 的 Array 访问不存在的 key 可以得到 null，不会产生 fatal error，但会有一个 E_NOTICE。这个 E_NOTICE 会被 set_error_handler 注册的函数截获。显然，这种代码上的不干净和性能上的无谓开销完全是可以避免的。

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

Salin selepas log masuk

一般的 PHPer 都不会用array_key_exists 和 if else 来处理，这样做会显得有些麻烦。

有时候Array 的使用，性能会变得很差。Array 本质上是一个 Map，unshift 一个元素进来，将会改变每个元素的 key，这是一个 O(n)操作。另外，PHP 的 Array 将其 value(包括 key 和它的 hash) 保存在一个 bucket 中，所以我们需要查看每一个 bucket 并更新 hash。

PHP 内部其实是通过创建新的 array 来完成 array_unshift 操作的，其性能问题可想可知。

DataStructures，PHP7的一个扩展，数组(Array)的一个替代品。

Github: https://github.com/php-ds

Namespace: Ds\

接口类: Collection, Sequence, Hashable

实现类(final class): Vector, Deque, Map, Set, Stack, Queue, PriorityQueue, Pair

2169471553-5b361c44601cc_articlex[1].png

接口类

Collection 是一个基础接口，定义了一个数据集合（这里的集合指的是 Collection，不是 Set）的基本操作，比如 foreach, echo, count, print_r, var_dump, serialize, json_encode, and clone.等。
Sequence 是类数组数据结构的基础接口，定义了很多重要且方便的方法，比如 contains, map, filter, reduce, find, first, last 等。从图中可知，Vector, Deque, Stack, Queue 都直接或者间接的实现了这个接口。它的特点如下：

值始终会被索引 [0, 1, 2, …, size - 1]
删除或插入更新所有连续值的位置。
只允许访问索引在 [0, size-1]的值。

Hashable 在图中看起来比较孤立，但对于 Map 和 Set 很重要。一个 Object 如果实现了 Hashable，就可以作为 Map 的 key，可以作为 Set 的元素。这样 Map 和 Set 就能像 Java 一样方便的使用了。

实现类

Vector 应该是最为常用的数据结构之一了，可以把它当成 Ruby 的 Array 或者 Python 的 List。其元素的值的 index 就是它在 buffer 中的 index，所以效率很高。只要有使用数组的需求且不需要 insert, remove, shift 和 unshift 的都可以用它。

视频说明

PhotoShop中使用主要的数据结构就是 Vector ---- Sean Parent

insert, remove, shift, and unshift 的复杂度为 O(n)
低内存使用量
get, set, push and pop的复杂度为 O(1)
优点：
缺点：
Deque（发音[dek] ）是一种双端队列“double-ended queue”。在 queue 的基础上增加了一个头指针，因此 shift 和 unshift 也是 O(1) 复杂度了。但带来的性能损耗并不多。

两个指针用于跟踪头部和尾部，指针可以“wrap around”缓冲区的末尾，这避免了需要移动其他值来腾出空间。这使得移位和移位非常快 - Vector无法与之竞争。视频说明

inser,remove 的复杂度为 O(n)。
缓冲区容量必须是2的n次方。
低内存使用量。
get,set, push, pop, shift, and unshift 的复杂度为 O(1)。
优点：
缺点：
Stack 是一种“LIFO” 结构，按照“后进先出”的原则允许访问、遍历、销毁结构顶部的值。DsStack 的内部使用的是 DsVector 的实现。
Queue 是一种“FIFO”结构，按照“先进先出”的原则允许访问、遍历、销毁结构顶部的值。DsQueue 内部使用的是 DsDeque 的实现。
PriorityQueue（优先级队列）与 Queue 非常的相似，按照分配的优先级将值推入队列，优先级最高的值始终位于队列的前端。遍历 PriorityQueue 具有破坏性，相当于连续的弹出操作，直到队列为空。使用最大堆实现。
Hashable , 一个允许用对象作键的接口。注意：并不是hashTable。Hashable只引入了两种方法：hash和equals。支持Hashable接口的数据结构是Map和Set。
Map , 一种连续的键值对集合。同 array 的使用是一致的，key 可是是任意的类型，但是必须唯一。如果相同的 key 添加到 Map 中，那么会替换掉原有的。同array 一样，插入的顺序会被保留。

当key 为对象时，不能转成 Array 。

效率和内存使用几乎和 Array 一致
当Map 的大小下降到足够小时，会自动释放已分配的内存。
key 和 value 可以是任意类型，甚至是对象。
put, get, remove, 和 hasKey 的复杂度为 O(1)

优点：
缺点：

Set，是一个无序唯一值的集合。Map 内部使用了 set 的实现，他们都是基于Array 相同的内部结构，这意味这Set 的排序具有 O(n*log n) 的复杂度。

不支持 push, pop, insert, shift, unshift
如果在索引之前删除了值，那么复杂度会从 O(1) 降到 O(n)

添加、删除、引用都是 O(1)的复杂度
使用 Hashable 的接口
支持任何类型的值。

优点：
缺点：

这里在说明一点，Array中的值本身是没有索引的，因此在使用 in_array()的时候呈线性搜索，复杂度为 O(n)。
如果想要创建一个唯一值数组，可以使用 array_unique()，由于array_unique()针对的是 value 而不是 key，所以每个数组成员都会被限行搜索，复杂度会变为 O(n²)。

以上就是本文的全部内容，希望对大家的学习有所帮助，更多相关内容请关注PHP中文网！