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 и извлекаем все из стека.

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

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

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

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

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

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

В реальных приложениях объекты будут намного сложнее, поэтому смею предположить, что значительный перевес будет на стороне метода из 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; $i<$count; $i++)
	{
		$a[$i] = $i;
		
		if ($i==9999) $a->setSize(100000);
	}

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

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, который работает быстрей чем обычный массив. Однако это очень маленькая часть применения данной библиотеки. В следующих статьях будут рассмотрены итераторы, интерфейсы, функции и обработка исключений.

Автор: kpuzuc

Источник