- Standard PHP Library (SPL) — Часть 1: Структуры данных
- SplDoublyLinkedList
- SplStack
- SplQueue
- SplHeap
- SplMaxHeap и SplMinHeap
- SplPriorityQueue
- SplFixedArray
- SplObjectStorage
- Функции SPL
- Содержание
- User Contributed Notes 8 notes
- /dev/energy
- Сайт о том, как стать программистом и как с этим жить потом
- Лекция-дайджест по PHP SPL
- Standard PHP Library: взгляд изнутри
- 1. Что такое SPL?
- 2. Структуры данных в SPL
- 2.1. Двусвязный список ( DLL )
- 2.1.1. SplStack
- 2.1.2. SplQueue
- 2.2. SplHeap
- 2.3. SplPriorityQueue
- 2.4. SplFixedArray
- Тогда как это реализовано в PHP?
- 3. Итераторы
- 3.1. ArrayIterator
- 3.2. DirectoryIterator
- 4. SPL функции
Standard PHP Library (SPL) — Часть 1: Структуры данных
Привет, Хабр! В данной статье речь пойдет про Standard PHP Library (SPL). На хабре до сих пор нет толкового мануала об этой библиотеке, которая уже стала частью ядра PHP (с версии 5.3). Данная библиотека содержит набор интерфейсов, классов структур данных, итераторов и функций, с помощью которых можно значительно упростить себе жизнь и повысить качество кода. В данной статье я рассматриваю такую часть библиотеки, как структуры данных. Также я покажу альтернативные решения поставленных задач и сравню скорость выполнения в обоих случаях.
Итак. Прежде всего хочу дать ссылку на официальную документацию: php.net/manual/en/book.spl.php
В библиотеке SPL содержатся такие структуры данных:
Рассмотри по порядку каждую из структур.
SplDoublyLinkedList
Двусвязный список (DLL) — это список узлов, связанных в обоих направлениях друг между другом. Как известно, есть два принципа извлечения значения из списка – FIFO (First In First Out – первый зашел, первый ушел) и LIFO (Last In First Out – последний зашел, первый ушел). С помощью SplDoublyLinkedList можно извлекать значения по любому из этих принципов. Следовательно, с его помощью можно легко организовать стек или очередь.
SplStack
Данный класс является наследником SplDoublyLinkedList и реализует стек, например:
Ранее для создания мы использовали процедурный способ, а именно использовали функции 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.
Однако если добавлять в стек более сложные объекты, то разница между результатами уже на уровне погрешности.
В этом тесте мы добавляли и извлекали из стека следующий объект:
Количество push и pop | Использование функций | Использование SplStack | Отношение |
---|---|---|---|
1000 | 0.007974 | 0.008301 | 0,960607156 |
100000 | 0.818596 | 0.826363 | 0,990600983 |
В реальных приложениях объекты будут намного сложнее, поэтому смею предположить, что значительный перевес будет на стороне метода из SPL.
SplQueue
Данная структура используется для создания очередей. Все аналогично стеку, рассмотрим лишь небольшой пример:
SplHeap
Кучи являются древовидными структурами: каждый узел больше или равен своим потомкам, при этом для сравнения используется внедренный метод сравнения, который является общим для всей кучи. SplHeap реализует основную функциональность кучи и является абстрактным классом.
SplMaxHeap и SplMinHeap
От SplHeap наследуются два класса: SplMaxHeap – для сортировки массива по убыванию его значений, SplMinHeap – для сортировки массива по возрастанию.
SplPriorityQueue
Данная структура представляет собой очередь с приоритетами. Для каждого элемента можно задать его приоритет. Сортировка производится в зависимости от приоритета.
SplFixedArray
Структура представляет собой массив с фиксированным количеством элементов. SplFixedArray хранит данные в непрерывном виде, доступные через индексы, а обычные массивы реализованы в виде упорядоченных хэш-таблиц. Данный вид массива работает быстрее, чем обычные массивы, но существуют некоторые ограничении:
Данная структура хорошо подходит для нумерованных списков. Давайте рассмотрим пример и проведем тесты:
Количество 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
Данная структура представляет собой хранилище объектов. Объекты можно прикреплять к хранилищу, удалять, получать текущий объект. Рассмотрим несколько примеров с оффициального мануала:
На этом мы закончили изучать структуры данных SPL. Мы научились быстро создавать стек, очередь и списки. Мы теперь знаем о SplFixedArray, который работает быстрей чем обычный массив. Однако это очень маленькая часть применения данной библиотеки. В следующих статьях будут рассмотрены итераторы, интерфейсы, функции и обработка исключений.
Функции SPL
Содержание
User Contributed Notes 8 notes
For some application I needed to reverse some standard iterators.
So I mocked up this flexible function.
Enjoy
/*
How to store SPL Iterator results (rather than just echo-and-forget):
I have to correct my implementation from before. The example before only supported correct read-access but failed on setting new values after creation of the ArrayMultiObject. Also i had to correct a bug that occured from my CopyPasteChange into the comment textarea.
This snippet now hopefully implements a fully functional multidimensional array, represented by an ArrayObject:
There is a RecursiveFilterIterator that makes the above code much easier. And then ther is ParentIterator thta is already a filtering recursive iterator that only accepts elements that have children, with a RecursiveDirectoryIterator as inner iterator you would obviously get only the directories. Further more it ensures that it creates the correct children. All in all you simply need to do this:
$it = new RecursiveDirectoryIterator($path);
$it = new ParentIterator($it);
$it = new RecursiveIteratorIteator($it);
recurse (new RecursiveDirectoryIterator ( ‘D:/’ ));
?>
Something to note that, at least to me, seems pretty important and is not entirely clear in the documentation is the fact that the ArrayObject class supports get/set on uni-dimensional keys and get ONLY on *passed* multi-dimensional keys/paths (see source below). If you, like me, need to support array accesss overloading for multi-dimensional data, you will need to derive from ArrayObject and overide the ArrayAccess interface methods to «walk» passed data and convert embedded arrays to objects of some kind.
Illustration of the issue:
$a = array(
«test» => array(
«one» => «dunno»,
«two» => array(
«peekabo» => «do you see me?»,
«anyone» => array(«there»)
)
)
);
$oArray = new ArrayObject($a);
var_dump($oArray);
$oArray[«three»] = «No problems here.»;
// NEITHER of the two below will work!
$oArray[«test»][«one»] = «Yes I do!»;
$oArray[«test»][«yes»] = array(
«hello» => «Goodbye!»
);
—
Note from the extension author:
Actually there is RecursiveArrayObject and RecursiveArrayIterator to deal with recursive structures. However this does not always solve all multidimensional issues as expected.
This code is an example. By using classes like this, you gives a chance to create classes which extends another class but have most of the ability what a class extends ArrayObject (like multiple inheritance):
function __toString ()
<
return ‘String test’ ;
> // function
> // class
/* Generated output:
1
foo
4
0=>1
1=>2
2=>3
3=>4
array
0 => int 1
1 => int 2
2 => int 3
3 => int 4
String test
*/
?>
For proper use you must be define all these methods except getArray()
Browse SPL’s sources to be a very helpful think.
/dev/energy
Сайт о том, как стать программистом и как с этим жить потом
Лекция-дайджест по PHP SPL
Специально для своей команды разработки я решил проводить лекции, посвящённые технологиям и стандартам, которые очень здорово было бы применить в работе и которые почему-то недооценены.
Сегодня речь пойдёт о встроенной в 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), что является очень дешёвой операцией.
Направление итерации (одно из двух):
SplDoublyLinkedList::IT_MODE_LIFO (Стек)
SplDoublyLinkedList::IT_MODE_FIFO (Очередь)
Поведение итератора (одно из двух):
SplDoublyLinkedList::IT_MODE_DELETE (Элементы удаляются итератором)
SplDoublyLinkedList::IT_MODE_KEEP (Итератор обходит элементы, не удаляя их)
2.1.1. SplStack — это наследник DLL, реализующий структуру стэка.
Стэк — это абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO.
Вот пример реализации простого стэка
Наследует основные операции от DLL.
2.1.2. SplQueue – структура для создания очереди.
Очередь — абстрактный тип данных с дисциплиной доступа к элементам FIFO. Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.
По сути – то же самое, что стэк, только FIFO.
2.2. SplHeap — древовидная структура: каждый узел больше или равен своим потомкам, при этом для сравнения используется внедренный метод сравнения, который является общим для всей кучи. SplHeap реализует основную функциональность кучи и является абстрактным классом.
От SplHeap наследуются два класса: SplMaxHeap – для сортировки массива по убыванию его значений, SplMinHeap – для сортировки массива по возрастанию.
2.3. SplPriorityQueue — обеспечивает основные функциональные возможности приоритетной очереди, реализованный при помощи кучи (max-heap). Сортировка производится в зависимости от приоритета. Далее следует обычный алгоритм вытаскивания элекментов из структуры.
2.4. SplFixedArray — представляет собой массив с фиксированным количеством элементов. SplFixedArray хранит данные в непрерывном виде, доступные через индексы, а обычные массивы реализованы в виде упорядоченных хэш-таблиц. Данный вид массива работает быстрее, чем обычные массивы, но существуют некоторые ограничении:
Тут стоит уделить внимание тому, как же реализованы массивы в 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 — позволяет сбрасывать и модифицировать значения и ключи в процессе итерации по массивам и объектам. Конструктор принимает массив в качестве параметра и предоставляет набор методов для его обработки.
Обычно используется ArrayObject, класс для обработки объектов как массивов в определенном контексте, вместо непосредственного применения ArrayIterator. В данном случае автоматически создается ArrayIterator когда используется цикл foreach или можно вызвать метод ArrayIterator::getIterator().
Обратите внимание, что, хотя ArrayObject и ArrayIterator ведут себя как массивы в данном контексте, они являются объектами. Попытка использовать встроенные функции для массивов, например, sort() или array_keys(), для них приведет к ошибке.
Использование ArrayIterator ограничивается одномерными массивами. Тогда, когда можно обрабатывать многомерные массивы нужно использовать RecursiveArrayIterator.
3.2. DirectoryIterator – итератор для работы с директориями.
С помощью набора различных методов, таких как DirectoryIterator::isDot(), DirectoryIterator::getType() и DirectoryIterator::getSize(), можно получить практически любую информацию о директории. Также можно комбинировать DirectoryIterator с FilterIterator или RegexIterator для получения списка файлов по определенным критериям.
В SPL также имеется RecursiveDirectoryIterator, который можно использовать также, как и RecursiveArrayIterator. Есть одна особенность. RecursiveDirectoryIterator не возвращает пустых директорий: если директория содержит много поддиректорий, но без файлов, результат будет пустым.
4. SPL функции
Помимо прочего, SPL предоставляет набор очень удобных функций, которые позволяют строить мощную архитектуру каркасов приложений.
4.1. class_implements — Возвращает список интерфейсов, реализованных в заданном классе или интерфейсе
4.2. class_parents — Возвращает список родительских классов заданного класса
4.3. class_uses — Возвращает список трэйтов, используемых заданным классом
4.4. iterator_apply — Вызывает функцию для каждого элемента в итераторе
4.5. iterator_count — Подсчитывает количество элементов в итераторе
4.6. iterator_to_array — Копирует итератор в массив
4.7. spl_autoload_call — Попытка загрузить описание класса всеми зарегистрированными методами __autoload()
4.8. spl_autoload_extensions — Регистрация и вывод расширений файлов для spl_autoload
4.9. spl_autoload_functions — Получение списка всех зарегистрированных функций __autoload()
4.10. spl_autoload_register — Регистрирует заданную функцию в качестве реализации метода __autoload(). Является более предпочтительным вызовом автозагрузчиков. Активно используется во многих каркасах.
4.11. spl_autoload_unregister — Отмена регистрации функции в качестве реализации метода __autoload()
4.12. spl_autoload — Реализация по умолчанию метода __autoload()
4.13. spl_classes — Возвращает доступные классы SPL
4.14. spl_object_hash — Возвращает хеш-идентификатор для объекта
За сим лекция окончена. Буду рад ответить на возникшие вопросы.
Standard PHP Library: взгляд изнутри
Сегодня речь пойдёт о встроенной в PHP библиотеке SPL. В сети интернет достаточно много справочной информации по разным частям библиотеки. Я решил свести всё воедино. Получилась, этакая, лекция-дайджест.
1. Что такое SPL?
Стандартная библиотека PHP (SPL) — это набор интерфейсов и классов, предназначенных для решения стандартных задач. Не требуется никаких внешних библиотек для сборки этого расширения, и оно доступно по умолчанию в PHP 5.0.0 и выше.
2. Структуры данных в SPL
2.1. Двусвязный список ( DLL )
Вообще, связный список — это базовая динамическая структура данных, состоящая из узлов, каждый из которых содержит как данные, так и ссылки на следующий и/или предыдущий узел списка.
Зачем они нужны? Их преимущество перед массивом — это структурная гибкость: порядок элементов может не совпадать с порядком расположения данных в памяти, а обход всегда явно задаётся внутренними связями. Списки бывают трёх типов: одно-, дву- и XOR-связные.
Линейный однонаправленный список — это структура данных, состоящая из элементов одного типа, связанных между собой последовательно посредством указателей. Каждый элемент списка имеет указатель на следующий элемент. Последний элемент списка указывает на NULL. Элемент, на который нет указателя, является первым (головным) элементом списка. Здесь ссылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла, невозможно.
Двусвязный список — это список, ссылки в каждом узле которого указывают на предыдущий и на последующий узел. По двусвязному списку можно эффективно передвигаться в любом направлении — как к началу, так и к концу. В этом списке проще производить удаление и перестановку элементов, так как легко доступны адреса тех элементов списка, указатели которых направлены на изменяемый элемент.
XOR-связный список — структура данных, похожая на обычный двусвязный список, однако в каждом элементе хранящая только один адрес — результат выполнения операции XOR над адресами предыдущего и следующего элементов списка. Чтобы перемещаться по списку, необходимо взять два последовательных адреса и выполнить над ними операцию XOR, которая и даст реальный адрес следующего элемента.
Мы же рассмотрим встроенную в SPL структуру данных — двусвязный список. В SPL он является основой для двух крайне важных и интересных структур. Это стэк и очередь.
Сам класс обеспечивает основные возможности двусвязного списка. Не секрет, что есть два принципа работы с элементами списка — FIFO и LIFO. В DLL можно работать по любому из этих принципов. Это и позволяет реализовывать стэк и очередь.
Все операции итератора, удаления, добавления и т. п. имеют алгоритмическую сложность O(1), что является очень дешёвой операцией.
Направление итерации (одно из двух): — SplDoublyLinkedList::IT_MODE_LIFO (стэк); — SplDoublyLinkedList::IT_MODE_FIFO (очередь).
2.1.1. SplStack
SplStack — это наследник DLL, реализующий структуру стэка. Стэк — это абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO.
Вот пример реализации простого стэка:
Наследует основные операции от DLL.
2.1.2. SplQueue
SplQueue – структура для создания очереди. Очередь — абстрактный тип данных с дисциплиной доступа к элементам FIFO. Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.
По сути – то же самое, что стэк, только FIFO:
2.2. SplHeap
SplHeap — древовидная структура: каждый узел больше или равен своим потомкам, при этом для сравнения используется внедренный метод сравнения, который является общим для всей кучи. SplHeap реализует основную функциональность кучи и является абстрактным классом. От SplHeap наследуются два класса: SplMaxHeap – для сортировки массива по убыванию его значений, SplMinHeap – для сортировки массива по возрастанию.
2.3. SplPriorityQueue
Обеспечивает основные функциональные возможности приоритетной очереди, реализованный при помощи кучи (max-heap). Сортировка производится в зависимости от приоритета. Далее следует обычный алгоритм вытаскивания элементов из структуры.
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
Позволяет сбрасывать и модифицировать значения и ключи в процессе итерации по массивам и объектам. Конструктор принимает массив в качестве параметра и предоставляет набор методов для его обработки.
Обратите внимание, что, хотя ArrayObject и ArrayIterator ведут себя как массивы в данном контексте, они являются объектами. Попытка использовать встроенные функции для массивов, например, sort() или array_keys() для них приведет к ошибке.
Использование ArrayIterator ограничивается одномерными массивами. Тогда, когда можно обрабатывать многомерные массивы, нужно использовать RecursiveArrayIterator.
3.2. DirectoryIterator
Итератор для работы с директориями:
В SPL также имеется RecursiveDirectoryIterator, который можно использовать также, как и RecursiveArrayIterator. Есть одна особенность. RecursiveDirectoryIterator не возвращает пустых директорий: если директория содержит много поддиректорий, но без файлов, результат будет пустым.
4. SPL функции
Ну что ж, лекция окончена. Буду рад ответить на возникшие вопросы, пишите их в комментариях.