Пользователь
0,0
рейтинг
9 декабря 2012 в 19:34

Разработка → Standard PHP Library (SPL) — Часть 1: Структуры данных из песочницы tutorial

PHP*
Привет, Хабр! В данной статье речь пойдет про 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; $i<$count; $i++)
	{
		$a[$i] = $i;
		
		if ($i==9999) $a->setSize(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, который работает быстрей чем обычный массив. Однако это очень маленькая часть применения данной библиотеки. В следующих статьях будут рассмотрены итераторы, интерфейсы, функции и обработка исключений.
Александр @kpuzuc
карма
18,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (36)

  • –28
    Это что, ASSEMBLER экспортируется в PHP? Зачем они это делают? Интерпретатор должен интерпретировать, а не создавать виртуальный стек, который здесь ни к чему.
    • +2
      Ну почему, очередей в PHP раньше не было (встроенных), а теперь хоть какие-то есть :).
      • +2
        Да вобщем-то давно оно уже есть ) Хотя хороший пост хотябы для популизации
      • +1
        Ну, простые-то очереди были через array_push() / array_shift(). Или, соответственно, array_unshift() / array_pop().
        • 0
          Проблема в том, что «очереди» через array_shift() обладают производительностью O(N), потому что массив пересоздается заново.
          • 0
            Простые и с O(N) потянут. А сложные — это уже, скорее, будет не уровень одного PHP-процесса. А межпроцессное взаимодействие, отдельные клиенты и обработчики. И тут уже лучше пойдут более специфичные инструменты, типа реализаций AMQP или Gearman.

            То есть безусловно новое решение наверняка полезно, но ответ был на комментарий «теперь хоть какие-то есть».
    • +7
      Классическое «слышал звон — не знаю где он»,
  • –25
    По моему эти никто никогда не пользуется.
    • +2
      Пользуюсь регулярно, так как проект хайлоадный и место узкое. Не говорите глупостей, это полезные вещи.
    • +2
  • +4
    Наверное правильнее спросить где и когда можно это использовать. Мне допустим это очень интересно. Например как на практике можно решить какую либо проблему с помощью этой библиотеки. Если привести короткий пример из жизни было бы супер.
    • +1
      В следующей части статьи будут рассмотрены итераторы. Там будут примеры из жизни.
      Насчет структур данных: тут например можно про «кучу» прочитать и область ее применения, а тут про очереди. На самом деле вещи довольно полезные, да и код теперь будет намного красивее
    • +4
      При реализации forth-машины на php :)

      А так, например, стэки широко используются при анализе или обработке вложенных структур данных, в частности при вычислении математических выражений. Очереди при обработке списков «заданий», скажем сначала парсим текстовый ввод в виде какого-то списка на отдельные элементы, нормализуя его в одном цикле, а потом обрабатываем нормализованный список в другом.

      Собственно какие-то особенные проблемы эти типы данных не решают, но бывает решаешь задачу и смотришь «о-па, стандартный тип, можно велосипед не изобретать, он уже есть в „ядре“» или даже «блин, писал-писал, а стандартный тип получился, надо нафиг удалять, чтобы не позориться». Типа паттернов, но чисто для данных. Упрощают не сколько написание кода, сколько его понимание другими (или собой через некоторое время :). Естественно при целевом использовании.

  • 0
    Я не смог понять вот эту фразу: "… — это список узлов, связанных в обоих направлениях друг между другом."
    Автор, ты не мог бы перефразировать это как-то более по-русски?
    Заранее спасибо.
    • +2
      Второй узел указывает как на первый, так и на третий. Третий на второй и четвёртый. В общем для любого элемента списка определен предыдущий узел и последующий без явной нумерации. Кроме граничных, конечно, у первого нет предыдущего, а у последнего нет последующего.
    • +6
      Господи, как можно хоть сколько-нибудь знать о программировании, и не знать, что такое и как устроен двусвязный список?
      • 0
        Новое поколение не читали Кнута и не изучали структуры данных. Про деревья лучше не упоминать ;)
      • +1
        Не учиться в универе например. И быть «крутым самоучкой». =) Это не про всех конечно. Но зачастую тенденция такова =)
  • +1
    Зачем лезть в программирование, даже на PHP, если не знать элементарных вещей типа двусвязных списки? И причем тут ассемблер? И как это никто это не использует? В PHP есть, конечно, очень удобный и гибкий array, но для некоторых задач более оптимальным решением будет использование специфичных структур данных. Не для удобства, а для экономии ресурсов, если кто-то об этом вообще думает.
    • +1
      pop/push стандартные операции по работе со стеком в ассемблере. Хотя есть popw и тому подобное… расширяющее это дело. Конечно, оно мало связанно, иначе, чем названием.

      Мне более интересно как это использовать. Вот, скажем, есть список продуктов и список их модификаций, в связанном списке (с ценой, названием и т.п.). Как ускорить сортировку, получая это дело в связанный список, как сделать аналог array_multisort(). Скажем 2000 продуктов. 20 тыщ. цен. А хостинг слабый (rssites, masterhost) — как ускорить этим делом.

      Извините, приземлен к своим задачам…

      ПС. Лезу (за деньги) 16-й год. Зачем? Чтобы выжить.
      • +1
        Да тогда можно приводить в пример практически любой другой язык, так как почти везде есть очереди, стеки, списки и т.п.

        В случае со списком продуктов и сортировкой связные списки ничего не дадут. Они эффективны тогда, когда нам нужен последовательный доступ к данным, то есть когда порядок обхода такой же, как при записи. В случае же, когда нужен случайный доступ к данным, в частности при сортировке, связные списки будут плохо работать. А сортировку в вашем случае лучше осуществлять на уровне запросов к БД, так как вряд ли там она будет выполняться медленней, чем если вы будете это делать в коде.
    • +4
      А я именно для удобства использую :) Вернее для семантики. Если написал, что это стэк, значит это стэк и незачем лезть в его середину или начало, бери элементы только с вершины.
    • 0
      Зачем лезть за руль машины, если не знать элементарной структуры атома железа, как выращивать каучуковые деревья и добывать каучук?
      Зачем заниматься сексом, если не знать что выделяет элементарные гормоны и как они влияют на организм?
      Примеров на данную тему в общем то масса.
      • 0
        На самом деле нет.
  • +1
    Включите, пожалуйста, в статью код тестов SplStack. Странно, что специализированная структура данных не дает преимущества в скорости перед стандартным массивом. Вы ведь его имели в виду, говоря об использовании функций array_pop и array_push?

    Еще хорошо бы протестировать и сравнить потребление памяти array и специализированными структурами — это зачастую даже важнее прироста производительности.
    • 0
      Вот да. Из статьи получается, что специализированные структуры дают лишь минимальный прирост скорости, а то и вообще никакого не дают — не очень понятно тогда, есть ли смысл вообще с ними заморачиваться.
      • +1
        Тесты какие-то очень синтетические. Скажем самый простой случай стандартного типа FixedArray меряет скорость заполнения массива, но никак не меряет скорость доступа к нему. А на практике как-то заполнение операция одноразовая, а вот доступ постоянная.
        • +2
          На днях постараюсь провести новые тесты и разместить их результаты в этой или новой статье.
  • +8
    Я вот наверное злой какойто. Но блин, эта штука есть в php уже давно и поэтому меня немного поражают неокторые комментарии к статье. Статья то хорошая. Но какой блин нахрен ассемблер, причем он тут вообще? Причем тут списки продуктов? Ну то есть понятно, что оно так или иначе приведет либо к прикладной задаче, либо будет прослеживаться ряд аналогий. Но это же библиотека, которая позволяет использовать классические структуры данных в своих задачах и делать это удобно.
    Насчет использования — очереди собственно для очередей чего угодно: сообщения, задачи… ну многие другие ситуации часто являются подмножествами. FixedArray — очевидно для того, чтобы знать о размере занимаемой памяти. Хранилище объектов удобная штука когда нужно хранить набор объектов определенного типа + оно реализует ряд интерфейсов типа итератор, array access и других, что тоже полезно.
    Это же хорошие и удобные штуки, да еще и в ООП стиле.
  • +9
    Хотелось бы спросить, чем статья лучше мануала?

    Статья оформлена по принципу
    — берём раздел мануала
    — смотрим в википедии незнакомые слова или слова которые автор думает будут незнакомы среднему хабраюзеру, копипастим описание
    — если в мануале есть описание, берём его тоже
    — добавляем слова «РАССМОТРИМ ПРИМЕР» или «НАПРИМЕР»
    — копипастим пример из мануала
    — добавляем слова «На этом мы закончили изучать структуры данных SPL.»

    Мне кажется, было бы гораздо больше пользы, если бы автор внёс всё это в русскую документацию по php, а здесь просто отставил ссылку. И ему карма и рейтинг, и польза какая-никакая.
    • 0
      я ен сравнивал статью с маном, но в целом статья не плохая.
      было бы не плохо, если автор действительно прислушиется Вашего совета и внесет свой вклад в развитие рускоязычного мана.
    • +3
      Цель статьи — популяризовать такие вещи, как эта библиотека. Чтобы новички увидели какие есть штуки и использовали их. После написания последней части я постараюсь перенести это в русскую документацию.
      • 0
        Я конечно злой, но… ни продолжения цикла, ни уточненных тестов которые обещали, ни собственно русской документации)
  • 0
    Наверное, основное отличии структур-списков от массивов с позиции использования — передеча их аргументом в функции. Очевидно, что массив передается по значению, а список (например, SplFixedArray) — по ссылке. Из-за этого они как минимум не взаимозаменяемы логически. И в зависимости от потребностей одна из двух структур (массив против списка) может быть удобнее.
    • –2
      Ничто не мешает нам передать в функцию массив по ссылке при помощи &.

      Даже если согласно сигнатуре функции массив должен быть передан по значению, на самом деле он передается по ссылке и только при попытке внести в него изменения будет на лету скопирован (copy on write). Поэтому не вижу, чем использование SplFixedArray будет оптимальнее.
  • +1
    В SplStack
    echo $stack->serialize();
    
    не выполнится, если версия PHP 5 < 5.4.0. И что интересно, там был баг с неправильной сериализацией, который закрыли в день написания этого топика :)

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.