Standard PHP Library (SPL) - Part 1: Data Structures
Hi, Habr! This article discusses the Standard PHP Library (SPL). On Habré there is still no intelligent manual about this library, which has already become part of the PHP core (since version 5.3). This library contains a set of interfaces, classes of data structures, iterators, and functions with which you can greatly simplify your life and improve the quality of the code. In this article I consider such a part of the library as data structures. I will also show alternative solutions to the tasks and compare the speed of implementation in both cases.
So. First of all I want to give a link to the official documentation: php.net/manual/en/book.spl.php
The SPL library contains the following data structures:
')
Consider in order each of the structures.
A doubly linked list (DLL) is a list of nodes connected in both directions between each other. As you know, there are two principles for extracting values from the list - FIFO (First In First Out - first went, first left) and LIFO (Last In First Out - last went, first left). With SplDoublyLinkedList, values can be retrieved according to any of these principles. Therefore, it can be used to easily organize a stack or a queue.
This class is the successor of SplDoublyLinkedList and implements the stack, for example:
Previously, we used the procedural method to create, namely, we used the functions of array_push - adding elements to the end of the array and array_pop - extracting the last element. Now we work with objects.
Compare the speed of the two ways. Test conditions: PHP 5.3.18, Core 2 Duo P7350, Windows. Add a number from 1 to n to the stack and retrieve everything from the stack.
In this test, the method using functions worked faster by about 10-15%.
For the sake of interest, I conducted another test in PHP 5.4.8
By this test, you can see that PHP 5.4.8 is faster than PHP 5.3.18 when working with a stack by about 10% and work with objects is also improved. Therefore, I will conduct all subsequent tests on this version of PHP.
However, if you add more complex objects to the stack, the difference between the results is already at the level of error.
In this test, we added and removed from the stack the following object:
In real-world applications, objects will be much more complicated, so I dare to suggest that a significant advantage will be on the side of the method from SPL.
This structure is used to create queues. Everything is similar to the stack, consider only a small example:
Heaps are tree structures: each node is greater than or equal to its descendants, and an embedded comparison method is used for comparison, which is common to the entire heap. SplHeap implements the core functionality of the heap and is an abstract class.
Two classes are inherited from SplHeap: SplMaxHeap - to sort an array in descending order of its values, SplMinHeap - to sort an array in ascending order.
This structure is a priority queue. For each element, you can set its priority. Sorting is performed depending on the priority.
The structure is an array with a fixed number of elements. SplFixedArray stores data in a continuous form, accessible through indexes, and regular arrays are implemented as ordered hash tables. This type of array works faster than regular arrays, but there are some constraints:
This structure is well suited for numbered lists. Let's take an example and run tests:
Tests have confirmed that SplFixedArray is leading with any previously known number of array elements. However, if the size of the array changes during the process, the advantage becomes less significant: (initially the size was set to 10,000, then expanded to 100,000):
This structure is a repository of objects. Objects can be attached to the repository, delete, get the current object. Consider a few examples from the official manual:
One more example:
Result:
This concludes our study of SPL data structures. We learned how to quickly create stacks, queues, and lists. We now know about SplFixedArray, which is faster than a regular array. However, this is a very small part of the use of this library. In the following articles, iterators, interfaces, functions, and exception handling will be considered.
So. First of all I want to give a link to the official documentation: php.net/manual/en/book.spl.php
The SPL library contains the following data structures:
- SplDoublyLinkedList - Twofold Lists
- SplStack - Stack
- SplQueue - Queue
- SplHeap - Heap
- SplMaxHeap - Sort Heap Descending
- SplMinHeap - Sort Heap Ascending
- SplPriorityQueue - Priority Queues
- SplFixedArray - Limited Length Array
- SplObjectStorage - Object Storage
')
Consider in order each of the structures.
SplDoublyLinkedList
A doubly linked list (DLL) is a list of nodes connected in both directions between each other. As you know, there are two principles for extracting values from the list - FIFO (First In First Out - first went, first left) and LIFO (Last In First Out - last went, first left). With SplDoublyLinkedList, values can be retrieved according to any of these principles. Therefore, it can be used to easily organize a stack or a queue.
Splstack
This class is the successor of SplDoublyLinkedList and implements the stack, for example:
$stack = new SplStack(); // $stack->push('1'); $stack->push('2'); $stack->push('3'); echo $stack->count(); // 3 echo $stack->top(); // 3 echo $stack->bottom(); // 1 echo $stack->serialize(); // i:6;:s:1:"1";:s:1:"2";:s:1:"3"; // echo $stack->pop(); // 3 echo $stack->pop(); // 2 echo $stack->pop(); // 1 Previously, we used the procedural method to create, namely, we used the functions of array_push - adding elements to the end of the array and array_pop - extracting the last element. Now we work with objects.
Compare the speed of the two ways. Test conditions: PHP 5.3.18, Core 2 Duo P7350, Windows. Add a number from 1 to n to the stack and retrieve everything from the stack.
| Number of push and pop | Use of functions | Using SplStack | Attitude |
|---|---|---|---|
| 1000 | 0.007686 | 0.008559 | 0.898002 |
| 100,000 | 0.793184 | 0.884979 | 0.896274375 |
In this test, the method using functions worked faster by about 10-15%.
For the sake of interest, I conducted another test in PHP 5.4.8
| Number of push and pop | Use of functions | Using SplStack | Attitude |
|---|---|---|---|
| 1000 | 0.008186 | 0.008735 | 0,937149399 |
| 100,000 | 0.732347 | 0.771456 | 0,949304951 |
By this test, you can see that PHP 5.4.8 is faster than PHP 5.3.18 when working with a stack by about 10% and work with objects is also improved. Therefore, I will conduct all subsequent tests on this version of PHP.
However, if you add more complex objects to the stack, the difference between the results is already at the level of error.
In this test, we added and removed from the stack the following object:
$obj = array("10", "20", "qwerty", "100", array("one", "two", array("100") ) );
| Number of push and pop | Use of functions | Using SplStack | Attitude |
|---|---|---|---|
| 1000 | 0.007974 | 0.008301 | 0,960607156 |
| 100,000 | 0.818596 | 0.826363 | 0.990600983 |
In real-world applications, objects will be much more complicated, so I dare to suggest that a significant advantage will be on the side of the method from SPL.
Splquueue
This structure is used to create queues. Everything is similar to the stack, consider only a small example:
$queue = new SplQueue(); $queue->setIteratorMode(SplQueue::IT_MODE_DELETE); $queue->enqueue('one'); $queue->enqueue('two'); $queue->enqueue('qwerty'); $queue->dequeue(); $queue->dequeue(); echo $queue->top(); // qwerty
Splheap
Heaps are tree structures: each node is greater than or equal to its descendants, and an embedded comparison method is used for comparison, which is common to the entire heap. SplHeap implements the core functionality of the heap and is an abstract class.
SplMaxHeap and SplMinHeap
Two classes are inherited from SplHeap: SplMaxHeap - to sort an array in descending order of its values, SplMinHeap - to sort an array in ascending order.
$heap = new SplMaxHeap(); $heap->insert('111'); $heap->insert('666'); $heap->insert('777'); echo $heap->extract(); // 777 echo $heap->extract(); // 666 echo $heap->extract(); // 111 $heap = new SplMinHeap(); $heap->insert('111'); $heap->insert('666'); $heap->insert('777'); echo $heap->extract(); // 111 echo $heap->extract(); // 666 echo $heap->extract(); // 777
SplPriorityQueue
This structure is a priority queue. For each element, you can set its priority. Sorting is performed depending on the priority.
$queue = new SplPriorityQueue(); $queue->setExtractFlags(SplPriorityQueue::EXTR_DATA); // $queue->insert('Q', 1); $queue->insert('W', 2); $queue->insert('E', 3); $queue->insert('R', 4); $queue->insert('T', 5); $queue->insert('Y', 6); $queue->top(); while($queue->valid()) { echo $queue->current(); $queue->next(); } //YTREWQ
SplFixedArray
The structure is an array with a fixed number of elements. SplFixedArray stores data in a continuous form, accessible through indexes, and regular arrays are implemented as ordered hash tables. This type of array works faster than regular arrays, but there are some constraints:
- only integers> 0 can be used as keys
- length can be changed, but it is a costly operation
This structure is well suited for numbered lists. Let's take an example and run tests:
$a = new SplFixedArray(10000); $count = 100000; for($i =0; $i<$count; $i++) { $a[$i] = $i; if ($i==9999) $a->setSize(100000); }
| Number of push and pop | Ordinary array | Using SplFixedArray | Attitude |
|---|---|---|---|
| 100 | 8.2 x 10E-5 | 6.3 x 10E-5 | 1,301587301 |
| 10,000 | 0.004953 | 0.003983 | 1.243535024 |
| 100,000 | 0.053586 | 0.0385701 | 1,389314521 |
| 1,000,000 | 0.533003 | 0.384391 | 1.386616752 |
Tests have confirmed that SplFixedArray is leading with any previously known number of array elements. However, if the size of the array changes during the process, the advantage becomes less significant: (initially the size was set to 10,000, then expanded to 100,000):
| Number of push and pop | Ordinary array | Using SplFixedArray | Attitude |
|---|---|---|---|
| 1,000,000 | 0.051937 | 0.049462 | 1,050038413 |
SplObjectStorage
This structure is a repository of objects. Objects can be attached to the repository, delete, get the current object. Consider a few examples from the official manual:
$s = new SplObjectStorage(); // $o1 = new StdClass; $o2 = new StdClass; $o3 = new StdClass; $s->attach($o1); // $s->attach($o2); var_dump($s->contains($o1)); // bool(true) var_dump($s->contains($o2)); // bool(true) var_dump($s->contains($o3)); // bool(false) $s->detach($o2); // var_dump($s->contains($o1)); // bool(true) var_dump($s->contains($o2)); // bool(false) var_dump($s->contains($o3)); // bool(false)
One more example:
$s = new SplObjectStorage(); $o1 = (object)array('a'=>1); $o2 = (object)array('b'=>2); $o3 = (object)array('c'=>3); $s[$o1] = "data for object 1"; $s[$o2] = array(1,2,3); foreach($s as $i => $key) { echo "Entry $i:\n"; // You get a numeric index var_dump($key, $s[$key]); echo "\n"; }
Result:
Entry 0: object(stdClass)#2 (1) { ["a"]=> int(1) } string(17) "data for object 1" Entry 1: object(stdClass)#3 (1) { ["b"]=> int(2) } array(3) { [0]=> int(1) [1]=> int(2) [2]=> int(3) }
This concludes our study of SPL data structures. We learned how to quickly create stacks, queues, and lists. We now know about SplFixedArray, which is faster than a regular array. However, this is a very small part of the use of this library. In the following articles, iterators, interfaces, functions, and exception handling will be considered.
Source: https://habr.com/ru/post/161987/
All Articles