Use of PHP7.2 Data Structures

This article mainly introduces the use of PHP7.2 Data Structures, which has certain reference value. Now I share it with everyone. Friends in need can refer to it

PHP7.2 Data Structures use

1. Installation

pecl install ds

brew install homebrew/php/php71-ds

Currently PHP7.2 does not support installation using brew.

2. PHP original data structure Array

In the era of PHP5.x, Array is the only data type that represents a collection in PHP , he is both List and Map, he is everything.

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

This data type does bring convenience to developers, but it allows PHPer to ignore the benefits of the data structure, especially when learning other languages. Troubled.

After PHP was upgraded to 7, Array was also optimized, but its structure did not change, "optimized for everything; optimized for nothing" with room for improvement. So if we can optimize performance by introducing more convenient data structures, and writing code will be more convenient at the same time, then why not?

"What about SPL data structures?"
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.

“Why can’t we fix and improve them?”
We could, but I believe their design and implementation is so poor that it would be better to replace them with something brand new.

“The design of SPL data structures is terrible.” - Anthony Ferrara

Array

• PHP's Array can get null when accessing a non-existent key, and no fatal error will occur, but there will be an E_NOTICE. This E_NOTICE will be intercepted by the function registered by set_error_handler. Obviously, this kind of unclean code and unnecessary performance overhead can be completely avoided.

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

General PHPer will not use array_key_exists and if else to handle it, which will be a bit troublesome.

• Sometimes when using Array, the performance will become very poor. Array is essentially a Map. Unshifting an element will change the key of each element. This is an O(n) operation. In addition, PHP's Array saves its value (including key and its hash) in a bucket, so we need to check each bucket and update the hash.

PHP internally completes the array_unshift operation by creating a new array, and the performance issues can be imagined.

DataStructures, an extension of PHP7, a replacement for array (Array).

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

Namespace: Ds\

Interface class: Collection, Sequence, Hashable

Implementation class (final class): Vector, Deque, Map, Set, Stack, Queue, PriorityQueue, Pair

Interface class

• Collection is a basic interface that defines the basic operations of a data collection (the collection here refers to Collection, not Set) , such as foreach, echo, count, print_r, var_dump, serialize, json_encode, and clone. etc.

• Sequence is the basic interface of array-like data structures and defines many important and convenient methods, such as contains, map, filter, reduce, find, first, last, etc. As can be seen from the figure, Vector, Deque, Stack, and Queue all directly or indirectly implement this interface. Its characteristics are as follows:

• The value will always be indexed [0, 1, 2, …, size - 1]

• Deletion or insertion updates the position of all consecutive values.

• Only allows access to values ​​with indexes in [0, size-1].

• #Hashable looks isolated in the diagram, but is important for Maps and Sets. If an Object implements Hashable, it can be used as the key of Map and the element of Set. In this way, Map and Set can be used as conveniently as Java.

Implementation class

• Vector should be one of the most commonly used data structures. You can think of it as Ruby's Array or Python's List. The index of its element's value is its index in the buffer, so it is very efficient. You can use it as long as you need to use an array and do not need insert, remove, shift and unshift.

Video description

• The main data structure used in PhotoShop is Vector ---- Sean Parent

• ##The complexity of insert, remove, shift, and unshift is O(n)

• Low memory usage

##get, set , the complexity of push and pop is O(1)
Advantages:
Disadvantages:
Deque (pronounced [dek]) is a "double-ended queue". A head pointer is added to the queue, so shift and unshift are also O(1) complex. But the performance loss is not much.
Two pointers are used to track the head and tail. The pointers can be "wrap around" the end of the buffer, which avoids the need to move other values ​​to make room. This makes shift and shift very fast - Vector can't compete with that. Video Description
The complexity of insert and remove is O(n).
The buffer capacity must be 2 to the nth power.
Low memory usage.
The complexity of get,set, push, pop, shift, and unshift is O(1).
Advantages:
Disadvantages:
Stack is a "LIFO" structure, according to The "last in, first out" principle allows accessing, traversing, and destroying the values ​​at the top of the structure. DsStack internally uses the implementation of DsVector.
Queue is a "FIFO" structure that allows access, traversal, and destruction of the values ​​at the top of the structure according to the "first in, first out" principle. DsQueue internally uses the implementation of DsDeque.
PriorityQueue (Priority Queue) is very similar to Queue. Values ​​are pushed into the queue according to the assigned priority. The value with the highest priority is always at the front of the queue. Traversing the PriorityQueue is destructive and amounts to continuous pop operations until the queue is empty.
• Use maximum heap implementation

  .

Hashable , an interface that allows objects to be used as keys. Note: It is not
• hashTable

  . Hashable only introduces two methods: hash and equals. The data structures that support the Hashable interface are Map and Set.

Map , a continuous collection of key-value pairs. It is consistent with the use of array. The key can be of any type, but it must be unique. If the same key is added to the Map, the original one will be replaced. Like array, insertion order is preserved.
When key is an object, it cannot be converted to Array.

Efficiency and memory usage are almost the same as Array
When the size of the Map drops to a small enough size, it will be automatically released Allocated memory.
key and value can be of any type, even objects.
The complexity of put, get, remove, and hasKey is O(1)

Advantages:
Disadvantages:

Set is an unordered collection of unique values. Map uses the implementation of set internally, and they are all based on the same internal structure of Array, which means that the sorting of Set has a complexity of O(n*log n).
Does not support push, pop, insert, shift, unshift
If the value is deleted before indexing, the complexity will be From O(1) to O(n)

Adding, deleting, and referencing are all O(1) complexity
Interface using Hashable
Supports any type of value.

Advantages:
Disadvantages:

Here To clarify, the value in Array itself has no index, so when using
in_array()

, it is a linear search with a complexity of O(n). If you want to create an array of unique values, you can use array_unique()
. Since array_unique() targets value rather than key, each array member will be restricted. Searching, the complexity will become O(n²). The above is the entire content of this article. I hope it will be helpful to everyone's study. For more related content, please pay attention to the PHP Chinese website!

Related recommendations:

How to compile and install extended redis and swoole in php




Service container and dependency injection in PHP Analysis

The above is the detailed content of Use of PHP7.2 Data Structures. For more information, please follow other related articles on the PHP Chinese website!