06.05.19 в 09:34

Standard PHP Library: взгляд изнутри

Теги: структуры данных, программирование на php, списки, php spl, библиотека spl

PHP_Deep_16.5_site-5020-a43c0f.png

Сегодня речь пойдёт о встроенной в PHP библиотеке SPL. В сети интернет достаточно много справочной информации по разным частям библиотеки. Я решил свести всё воедино. Получилась, этакая, лекция-дайджест.

1. Что такое SPL?

Стандартная библиотека PHP (SPL) — это набор интерфейсов и классов, предназначенных для решения стандартных задач. Не требуется никаких внешних библиотек для сборки этого расширения, и оно доступно по умолчанию в PHP 5.0.0 и выше.

SPL предоставляет ряд стандартных структур данных, итераторов для «оббегания» объектов, интерфейсов, стандартных исключений, некоторое количество классов для работы с файлами и предоставляет ряд функций, например spl_autoload_register().

2. Структуры данных в SPL

2.1. Двусвязный список ( DLL )

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

Зачем они нужны? Их преимущество перед массивом — это структурная гибкость: порядок элементов может не совпадать с порядком расположения данных в памяти, а обход всегда явно задаётся внутренними связями. Списки бывают трёх типов: одно-, дву- и XOR-связные.

Линейный однонаправленный список — это структура данных, состоящая из элементов одного типа, связанных между собой последовательно посредством указателей. Каждый элемент списка имеет указатель на следующий элемент. Последний элемент списка указывает на NULL. Элемент, на который нет указателя, является первым (головным) элементом списка. Здесь ссылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла, невозможно.

Двусвязный список — это список, ссылки в каждом узле которого указывают на предыдущий и на последующий узел. По двусвязному списку можно эффективно передвигаться в любом направлении — как к началу, так и к концу. В этом списке проще производить удаление и перестановку элементов, так как легко доступны адреса тех элементов списка, указатели которых направлены на изменяемый элемент.

XOR-связный список — структура данных, похожая на обычный двусвязный список, однако в каждом элементе хранящая только один адрес — результат выполнения операции XOR над адресами предыдущего и следующего элементов списка. Чтобы перемещаться по списку, необходимо взять два последовательных адреса и выполнить над ними операцию XOR, которая и даст реальный адрес следующего элемента.

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

Сам класс обеспечивает основные возможности двусвязного списка. Не секрет, что есть два принципа работы с элементами списка — FIFO и LIFO. В DLL можно работать по любому из этих принципов. Это и позволяет реализовывать стэк и очередь.

Все операции итератора, удаления, добавления и т. п. имеют алгоритмическую сложность O(1), что является очень дешёвой операцией.

Вот операции, которые предоставляет SPL класс DLL: — add ( mixed $index , mixed $newval ) – добавление нового значение по указанному индексу; — bottom ( void ) — получает узел, находящийся в начале двусвязного списка; — count ( void ) — подсчитывает количество элементов в двусвязном списке; — current ( void ) — возвращает текущий элемент массива; — getIteratorMode ( void ) — возвращает режим итерации (LIFO, FIFO, DELETE, KEEP); — isEmpty ( void ) — проверяет, является ли двусвязный список пустым; — key ( void ) — возвращает индекс текущего узла; — next ( void ) — перемещает итератор к следующему элементу; — offsetExists ( mixed $index ) — проверяет, существует ли запрашиваемый индекс; — offsetGet ( mixed $index ) — возвращает значение по указанному индексу; — offsetSet ( mixed $index , mixed $newval ) — Устанавливает значение по заданному индексу $index в $newval; — offsetUnset ( mixed $index ) — удаляет значение по указанному индексу $index; — pop ( void ) — удаляет (выталкивает) узел, находящийся в конце двусвязного списка; — prev ( void ) — перемещает итератор к предыдущему элементу; — push ( mixed $value ) — помещает элемент в конец двусвязного списка; — rewind ( void ) — возвращает итератор в начало; — serialize ( void ) — сериализует хранилище; — setIteratorMode ( int $mode ) — устанавливает режим итерации.

Направление итерации (одно из двух): — SplDoublyLinkedList::IT_MODE_LIFO (стэк); — SplDoublyLinkedList::IT_MODE_FIFO (очередь).

Поведение итератора (одно из двух): — SplDoublyLinkedList::IT_MODE_DELETE (элементы удаляются итератором); — SplDoublyLinkedList::IT_MODE_KEEP (итератор обходит элементы, не удаляя их); — shift ( void ) — удаляет узел, находящийся в начале двусвязного списка; — top ( void ) — получает узел, находящийся в конце двусвязного списка; — unserialize ( string $serialized ) — десериализует хранилище; — unshift ( mixed $value ) — вставляет элемент в начало двусвязного списка; — valid ( void ) — проверяет, содержит ли узлы двусвязный список.

2.1.1. SplStack

SplStack — это наследник DLL, реализующий структуру стэка. Стэк — это абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO.

Вот пример реализации простого стэка:

push('1'); 
$stack->push('2');
$stack->push('3');

echo $stack->count(); // 3
echo "\n";
echo $stack->top(); // 3
echo "\n";
echo $stack->bottom(); // 1
echo "\n";
echo $stack->serialize(); // i:6;:s:1:"1";:s:1:"2";:s:1:"3";
echo "\n";

// извлекаем элементы из стека
echo $stack->pop(); // 3
echo "\n";
echo $stack->pop(); // 2
echo "\n";
echo $stack->pop(); // 1
echo "\n";

Наследует основные операции от DLL.

2.1.2. SplQueue

SplQueue – структура для создания очереди. Очередь — абстрактный тип данных с дисциплиной доступа к элементам FIFO. Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.

По сути – то же самое, что стэк, только FIFO:

setIteratorMode(SplQueue::IT_MODE_DELETE);

$queue->enqueue('one');
$queue->enqueue('two');
$queue->enqueue('qwerty');

$queue->dequeue();
$queue->dequeue();

echo $queue->top(); // qwerty

2.2. SplHeap

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

insert('111');
    $heap->insert('666');
    $heap->insert('777');

    echo $heap->extract(); // 777
    echo "\n";
    echo $heap->extract(); // 666
    echo "\n";
    echo $heap->extract(); // 111
    echo "\n";

    echo "SplMinHeap \n";
    $heap = new SplMinHeap();
    $heap->insert('111');
    $heap->insert('666');
    $heap->insert('777');

    echo $heap->extract(); // 111
    echo "\n";
    echo $heap->extract(); // 666
    echo "\n";
    echo $heap->extract(); // 777
    echo "\n";

2.3. SplPriorityQueue

Обеспечивает основные функциональные возможности приоритетной очереди, реализованный при помощи кучи (max-heap). Сортировка производится в зависимости от приоритета. Далее следует обычный алгоритм вытаскивания элементов из структуры.

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

2.4. SplFixedArray

Представляет собой массив с фиксированным количеством элементов. SplFixedArray хранит данные в непрерывном виде, доступные через индексы, а обычные массивы реализованы в виде упорядоченных хэш-таблиц. Данный вид массива работает быстрее, чем обычные массивы, но существуют некоторые ограничения: 1) в качестве ключей могут быть только целые числа > 0; 2) длина может быть изменена, но это затратная операция.

Тут стоит уделить внимание тому, как же реализованы массивы в PHP – именно те, с которыми мы обычно работаем. На уровне PHP, массив — это упорядоченный список, скрещенный с мэпом. Грубо говоря, PHP смешивает эти два понятия, в итоге получается, с одной стороны, очень гибкая структура данных, с другой стороны, возможно, не самая оптимальная.

На уровне C (да и вообще на системном уровне) не бывает массивов с нефиксированным размером. Каждый раз, когда вы создаете массив в C, вы должны указать его размер, чтобы система знала, сколько нужно памяти на него выделить.

Тогда как это реализовано в PHP?

Когда вы создаёте пустой массив, PHP создаёт его с определённым размером. Если вы заполняете массив и в какой-то момент достигаете и превышаете этот размер, то создаётся новый массив с вдвое большим размером, все элементы копируются в него и старый массив уничтожается.

На самом деле для реализации массивов в PHP используется вполне себе стандартная структура данных Hash Table. Этот самый Hash Table хранит в себе указатель на самое первое и последнее значения, указатель на текущее значение, кол-во элементов, представленных в массиве, массив указателей на Bucket-ы (о них далее), и ещё кое-что. Есть две главные сущности, первая — это собственно сам Hash Table, и вторая — это Bucket (далее ведро).

В вёдрах хранятся сами значения, то есть на каждое значение — своё ведро. Но помимо этого в ведре хранится оригинал ключа, указатели на следующее и предыдущее вёдра (они нужны для упорядочивания массива, ведь в PHP ключи могут идти в любом порядке, в каком вы захотите), и, опять же, ещё кое-что.

Таким образом, когда вы добавляете новый элемент в массив, если такого ключа там ещё нет, то под него создаётся новое ведро и добавляется в Hash Table. У Hash Table есть некий массив указателей на вёдра, при этом вёдра доступны в этом массиве по некоему индексу, а этот индекс можно вычислить, зная ключ ведра.

То, что происходит после переполнения массива, называется rehash. И именно тут происходит операция копирования массива, о которой я сказал ранее. И именно по этой причине в PHP нельзя применять стандартные оценки сложности сортировок и других алгоритмов при работе со стандартными массивами.

Теперь вернёмся к нашему SplFixedArray. Учитывая описание данной структуры, можно смело сказать, что это реализация массива в классическом его понимании. Данная структура хорошо подходит для нумерованных списков.

3. Итераторы

Раз уж мы говорим о структурах данных, то стоит упомянуть и такие механизмы, как итераторы.

Итератор – это интерфейс, предоставляющий доступ к элементам коллекции (массива или контейнера) и навигацию по ним.

Обработка объектов итераторов очень похожа на обработку массивов. Многие начинающие программисты начинают с использования итераторов для массивов. Но реальные преимущества итераторы дают при переборе большого количества гораздо более сложных данных, чем простой массив.

Цикл foreach делает копию массива, который ему передаётся. Если происходит обработка большого объёма данных, то копирование массивов при каждом использовании цикла foreach может быть нежелательным. Итераторы SPL инкапсулируют список и делают видимым один элемент в конкретный момент времени, что гораздо эффективнее.

При создании структур данных итераторы могут существенно повлиять на производительность, так как позволяют организовать отложенную загрузку данных. Отложенная загрузка даёт возможность получать данные только тогда, когда они нужны. Также можно манипулировать данными (фильтровать, преобразовывать и так далее) перед передачей их пользователю.

Решение об использовании итераторов всегда остаётся за разработчиком. Итераторы имеют ряд преимуществ, но в некоторых случаях их применение может оказаться избыточным (например, для небольших наборов данных). Поэтому нужно принимать во внимание все факторы проекта.

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

3.1. ArrayIterator

Позволяет сбрасывать и модифицировать значения и ключи в процессе итерации по массивам и объектам. Конструктор принимает массив в качестве параметра и предоставляет набор методов для его обработки.

 $value) {
    echo $key . ":  " . $value . "
";
}

Обычно используется ArrayObject, класс для обработки объектов как массивов в определённом контексте, вместо непосредственного применения ArrayIterator. В данном случае автоматически создается ArrayIterator когда используется цикл foreach или можно вызвать метод ArrayIterator::getIterator().

Обратите внимание, что, хотя ArrayObject и ArrayIterator ведут себя как массивы в данном контексте, они являются объектами. Попытка использовать встроенные функции для массивов, например, sort() или array_keys() для них приведет к ошибке.

Использование ArrayIterator ограничивается одномерными массивами. Тогда, когда можно обрабатывать многомерные массивы, нужно использовать RecursiveArrayIterator.

 $value) {
    echo $key . ": " . $value . "
";
}

3.2. DirectoryIterator

Итератор для работы с директориями:

";
}

С помощью набора различных методов, таких как DirectoryIterator::isDot(), DirectoryIterator::getType() и DirectoryIterator::getSize(), можно получить практически любую информацию о директории. Также можно комбинировать DirectoryIterator с FilterIterator или RegexIterator для получения списка файлов по определенным критериям.

getExtension(), $this->ext);
    }
}

//Создаём новый итератор
$dir = new FileExtensionFilter(new DirectoryIterator("./"));

// Создан итератор в итераторе

В SPL также имеется RecursiveDirectoryIterator, который можно использовать также, как и RecursiveArrayIterator. Есть одна особенность. RecursiveDirectoryIterator не возвращает пустых директорий: если директория содержит много поддиректорий, но без файлов, результат будет пустым.

4. SPL функции

Помимо прочего, SPL предоставляет набор очень удобных функций, которые позволяют строить мощную архитектуру каркасов приложений: — class_implements — возвращает список интерфейсов, реализованных в заданном классе или интерфейсе; — class_parents — возвращает список родительских классов заданного класса; — class_uses — возвращает список трэйтов, используемых заданным классом; — iterator_apply — вызывает функцию для каждого элемента в итераторе; — iterator_count — подсчитывает количество элементов в итераторе; — iterator_to_array — копирует итератор в массив; — spl_autoload_call — попытка загрузить описание класса всеми зарегистрированными методами __autoload(); — spl_autoload_extensions — регистрация и вывод расширений файлов для spl_autoload; — spl_autoload_functions — получение списка всех зарегистрированных функций __autoload(); — spl_autoload_register — регистрирует заданную функцию в качестве реализации метода __autoload(). Является более предпочтительным вызовом автозагрузчиков. Активно используется во многих каркасах; — spl_autoload_unregister — отмена регистрации функции в качестве реализации метода __autoload(); — spl_autoload — реализация по умолчанию метода __autoload(); — spl_classes — возвращает доступные классы SPL; — spl_object_hash — возвращает хеш-идентификатор для объекта;

Ну что ж, лекция окончена. Буду рад ответить на возникшие вопросы, пишите их в комментариях.

Компьютерное зрение