PHP7.2 Data Structures 使用

1. 安装

pecl install ds

brew install homebrew/php/php71-ds

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

2. PHP 原始的数据结构Array

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

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

这种数据类型的确是给开发者带来了便捷性，但让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

一般的 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

接口类

• 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 的都可以用它。

视频说明

• 优点：

  • 低内存使用量
  • get, set, push and pop的复杂度为 O(1)

• 缺点：

  • insert, remove, shift, and unshift 的复杂度为 O(n)

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

• Deque（发音[dek] ） 是一种双端队列“double-ended queue”。在 queue 的基础上增加了一个头指针，因此 shift 和 unshift 也是 O(1) 复杂度了。但带来的性能损耗并不多。

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

• 优点：

  • 低内存使用量。
  • get,set, push, pop, shift, and unshift 的复杂度为 O(1)。

• 缺点：

  • inser,remove 的复杂度为 O(n)。
  • 缓冲区容量必须是2的n次方。

• 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 一样，插入的顺序会被保留。

  • 优点：

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

  • 缺点：

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

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

  • 优点：

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

  • 缺点：

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

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