这篇文章主要介绍了关于PHP7.2 Data Structures的使用,有着一定的参考价值,现在分享给大家,有需要的朋友可以参考一下
pecl install ds
brew install homebrew/php/php71-ds
目前PHP7.2不支持使用 brew 安装。
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数据结构的设计非常可怕。” - 安东尼 费拉拉
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 的都可以用它。
视频说明
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中文网!
相关推荐:
以上是PHP7.2 Data Structures的使用的详细内容。更多信息请关注PHP中文网其他相关文章!