The standard php library

Standard PHP Library (SPL) — Часть 1: Структуры данных

Привет, Хабр! В данной статье речь пойдет про Standard PHP Library (SPL). На хабре до сих пор нет толкового мануала об этой библиотеке, которая уже стала частью ядра PHP (с версии 5.3). Данная библиотека содержит набор интерфейсов, классов структур данных, итераторов и функций, с помощью которых можно значительно упростить себе жизнь и повысить качество кода. В данной статье я рассматриваю такую часть библиотеки, как структуры данных. Также я покажу альтернативные решения поставленных задач и сравню скорость выполнения в обоих случаях.

Итак. Прежде всего хочу дать ссылку на официальную документацию: php.net/manual/en/book.spl.php
В библиотеке SPL содержатся такие структуры данных:

• SplDoublyLinkedList — Двусвязные списки
• SplStack — Стек
• SplQueue — Очередь
• SplHeap — Куча
• SplMaxHeap — Сортировка кучи по убыванию
• SplMinHeap — Сортировка кучи по возрастанию
• SplPriorityQueue — Приоритетные очереди
• SplFixedArray — Массив с ограниченной длиной
• SplObjectStorage — Хранилище объектов

Рассмотри по порядку каждую из структур.

SplDoublyLinkedList

Двусвязный список (DLL) — это список узлов, связанных в обоих направлениях друг между другом. Как известно, есть два принципа извлечения значения из списка – FIFO (First In First Out – первый зашел, первый ушел) и LIFO (Last In First Out – последний зашел, первый ушел). С помощью SplDoublyLinkedList можно извлекать значения по любому из этих принципов. Следовательно, с его помощью можно легко организовать стек или очередь.

SplStack

Данный класс является наследником SplDoublyLinkedList и реализует стек, например:

$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 

Ранее для создания мы использовали процедурный способ, а именно использовали функции array_push – добавление элементов в конец массива и array_pop – извлечение последнего элемента. Теперь мы работаем с объектами.

Сравним быстродействие двух способов. Тестовые условия: PHP 5.3.18, Core 2 Duo P7350, Windows. Добавляем в стек число от 1 до n и извлекаем все из стека.

Количество push и pop	Использование функций	Использование SplStack	Отношение
1000	0.007686	0.008559	0,898002
100000	0.793184	0.884979	0,896274375

В данном тесте способ с использованием функций сработал быстрее примерно на 10-15%.

Ради интереса провел еще тест в PHP 5.4.8

Количество push и pop	Использование функций	Использование SplStack	Отношение
1000	0.008186	0.008735	0,937149399
100000	0.732347	0.771456	0,949304951

По этому тесту можно увидеть, что PHP 5.4.8 быстрее чем PHP 5.3.18 при работе со стеком примерно на 10% и также улучшена работа с объектами. Поэтому все последующие тесты я буду проводить на этой версии PHP.

Однако если добавлять в стек более сложные объекты, то разница между результатами уже на уровне погрешности.

В этом тесте мы добавляли и извлекали из стека следующий объект:

$obj = array("10", "20", "qwerty", "100", array("one", "two", array("100") ) ); 

Количество push и pop	Использование функций	Использование SplStack	Отношение
1000	0.007974	0.008301	0,960607156
100000	0.818596	0.826363	0,990600983

В реальных приложениях объекты будут намного сложнее, поэтому смею предположить, что значительный перевес будет на стороне метода из SPL.

SplQueue

Данная структура используется для создания очередей. Все аналогично стеку, рассмотрим лишь небольшой пример:

$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

Кучи являются древовидными структурами: каждый узел больше или равен своим потомкам, при этом для сравнения используется внедренный метод сравнения, который является общим для всей кучи. SplHeap реализует основную функциональность кучи и является абстрактным классом.

SplMaxHeap и SplMinHeap

От SplHeap наследуются два класса: SplMaxHeap – для сортировки массива по убыванию его значений, SplMinHeap – для сортировки массива по возрастанию.

 $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

Данная структура представляет собой очередь с приоритетами. Для каждого элемента можно задать его приоритет. Сортировка производится в зависимости от приоритета.

 $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

Структура представляет собой массив с фиксированным количеством элементов. SplFixedArray хранит данные в непрерывном виде, доступные через индексы, а обычные массивы реализованы в виде упорядоченных хэш-таблиц. Данный вид массива работает быстрее, чем обычные массивы, но существуют некоторые ограничении:

• в качестве ключей могут быть только целые числа > 0
• длина может быть изменена, но это затратная операция

Данная структура хорошо подходит для нумерованных списков. Давайте рассмотрим пример и проведем тесты:

 $a = new SplFixedArray(10000); $count = 100000; for($i =0; $isetSize(100000); > 

Количество push и pop	Обычный массив	Использование SplFixedArray	Отношение
100	8.2 х 10E-5	6.3 х 10E-5	1,301587301
10000	0.004953	0.003983	1,243535024
100000	0.053586	0.0385701	1,389314521
1000000	0.533003	0.384391	1,386616752

Тесты подтвердили, что при любом заранее известном количестве элементов массива лидирует SplFixedArray. Однако если в процессе размер массива изменяется, то преимущество становится менее существенным: (первоначально размер был задан 10000, потом расширен до 100000):

Количество push и pop	Обычный массив	Использование SplFixedArray	Отношение
1000000	0.051937	0.049462	1,050038413

SplObjectStorage

Данная структура представляет собой хранилище объектов. Объекты можно прикреплять к хранилищу, удалять, получать текущий объект. Рассмотрим несколько примеров с оффициального мануала:

$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) 

$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"; >

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) > 

На этом мы закончили изучать структуры данных SPL. Мы научились быстро создавать стек, очередь и списки. Мы теперь знаем о SplFixedArray, который работает быстрей чем обычный массив. Однако это очень маленькая часть применения данной библиотеки. В следующих статьях будут рассмотрены итераторы, интерфейсы, функции и обработка исключений.

Источник