Оптимальные структуры данных в PHP

Как известно, родных типов данных в php немного. На самом деле в программировании, типов данных конечно же неограниченное множество, особенно когда дело касается деревьев (AA, M, k-d и прочая)

Стандартная библиотека php кроме интерфейсов итераторов и автоподгрузки классов предоставляет и более оптимальные типы данных.

Массивы

Что случается когда вы пытаетесь сделать универсальное и «простое» решение? Overhead с памятью. Дело в том что массивы в php на самом деле не массивы. Это сбивает немного с толку, но настоящий массив должен быть таким:

 

В php же массивы могут расти и итерироваться. Это реализуется списком с двойными ссылками (на следующий и предыдущий элементы). И конечно же массивы ассоциативные — ключи не обязаны быть упорядоченными int’ами — может и строка быть. А это всё усложняет — нужна хэш-таблица, хэш функция, система коллизий. И как следствие дополнительная инфраструктура…

Именно поэтому такой код выдаст не упорядоченный по индексу текст..

$bar = array();
for ($i = 7; $i >= 0; --$i) {
$bar[$i] = $i;
}
echo implode(' ', $bar);

… а то как данные инициализировались: 7 6 5 4 3 2 1 0

Из-за того что новичка не заставляют думать о структуре данных, как то делают в Java, выходит неоптимальное использование памяти. Для поддержки таких низкоуровневых массивов есть SplFixedArrayкоторый на 25-40% быстрей массивов, а также SplStack с SplQueue.

Структуры

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

Но я в своём движке использую объекты. Начиная с 5.4, объекты легче чем массивы. Из-за фиксации параметров классов и большей строгости, возможны подсказки при работе в IDE. Я умолчу об ООП — дополнительный методы у контейнеров могут добавить больше сложности чем решить.

Множества

Когда порядок не имеет особого значения, можно использовать множества. Конечно с массивами можно проводить такие же операции сложения (array_merge), вычитания (array_diff), пересечения (array_intersect) и проверки на присутствие (in_array), но как вы уже поняли, поиск по значению довольно медленный и вместо этого следует использовать поиск по ключу. Особенно если вы храните объекты:

$mySet = array();
$mySet(spl_object_hash($obj1)) = $obj1;
$mySet(spl_object_hash($obj2)) = $obj2;
isset($mySet(spl_object_hash($obj1))); //проверка вместо in_array
$mySet + $yourSet; //сложение работает потому что нет коллизий ключей
array_intersect_key($mySet, $yourSet); // пересечение по ключу
array_diff_key($mySet, $yourSet); // вычитание

Куча

Heap это просто такое дерево, ключи элементов которого распределяются по старшинству. Кучи часто используются в алгоритмах с графами. В php для этого есть SplHeap, SplMaxHeap и SplMinHeap, которые в сотни раз быстрей массивов.

Обобщение кучи это очередь с приоритетом — SplPriorityQueue, где порядок не FIFO/LIFO, а как вы догадались, согласно заданной важности

$priorityQueue = new SplPriorityQueue();
$priorityQueue->insert("Putin", 60);
$priorityQueue->insert("Zjuganov", 15);