Структуры данных(на примере PHP SPL)

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

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

Чаще всего для представления данных в PHP используют массив. Однако в некоторых случаях массивы не подходят для решения задач. Где-то не хватает производительности, где-то слишком много памяти "кушает", и поэтому требуются более подходящие структуры данных.

Библиотека SPL - является частью ядра(начиная с пятой версии PHP) и содержит набор интерфейсов, классов структур данных, итераторов и функций, с помощью которых можно значительно упростить себе жизнь и повысить качество кода.

Какие же есть структуры данных в этой вашей SPL?

  • SplDoublyLinkedList
  • Двусвязные спискиSplStack
  • СтекSplQueue
  • ОчередьSplHeap
  • КучаSplMaxHeap - Сортировка кучи по убыванию
  • SplMinHeap - Сортировка кучи по возрастанию
  • SplPriorityQueue - Приоритетные очереди
  • SplFixedArray - Массив с ограниченной длиной
  • SplObjectStorage - Хранилище объектов

SplDoublyLinkedList

SplDoublyLinkedList – двусвязный список. Каждый узел такого списка хранит ссылку на предыдущий и на следующий за ним узел. Представьте, что вы находитесь в очереди и при этом можете видеть только человека перед вами и позади вас. Это аналогия отношения связи между элементами в SplDoublyLinkedList. Вставка элемента в список соответствует ситуации, когда кто-то влез в очередь, а вы вдруг забыли, кто стоял перед вами (и этот кто-то забыл о вас). Двусвязный список позволяет эффективно обходить и добавлять большие наборы данных без необходимости повторного хеширования.

SplQueue и SplStack

SplQueue и SplStack очень похожи на SplDoublyLinkedList. Обе эти структуры, по сути, представляют собой двусвязные списки с разными флагами итераторов(IT_MODE_LIFO – Last In First Out – последним пришёл, первым ушёл; и IT_MODE_FIFO – First In First Out – первым пришёл, первым ушёл), которые регулируют порядок обработки узлов и что делать с этими элементами после того, как они будут обработаны. Ещё одно отличие между этими структурами заключается в том, что интерфейс SplQueue содержит более интуитивно понятные методы enqueue() и dequeue() в отличие от методов push() и pop() у SplStack.

SplHeap

SplHeap – куча, представленная в виде бинарного дерева, каждый узел которого имеет не более двух дочерних узлов. Это абстрактный класс, требующий расширения с определением метода compare(), позволяющего выполнять сортировку в реальном времени при вставке новых узлов в дерево.

SplMaxHeap и SplMinHeap

SplMaxHeap и SplMinHeap — конкретные реализации абстрактного класса SplHeap. SplMaxHeapреализует метод compare() таким образом, чтобы дерево было отсортировано в порядке убывания значений узлов, а SplMinHeap – в порядке возрастания значений.

SplPriorityQueue

SplPriorityQueue – очередь, похожая на SplHeap, но в отличие от SplHeap сортировка осуществляется на основании значения свойства priority (приоритет), заданного для каждого узла.

SplFixedArray

SplFixedArray – массив фиксированной длины, индексами которого могут быть только целые числа. Эти ограничению обеспечивают более высокую скорость обработки массива, которая достигается, в том числе, благодаря тому, что в SplFixedArray нет хеширования ключей элементов при их добавлении (в отличие от обычных массивов).

SplObjectStorage

SplObjectStorage – хранилище объектов, предоставляет интерфейс для сопоставления объектов к данным, либо может быть использовано в качестве контейнера для множества объектов. Позволяет использовать объект в качестве ключа ассоциативного массива и связать его с некоторыми данными.

------

Официальная документация по SPL http://php.net/manual/ru/book.spl.php

Кстати, если претендуешь на вакансию уровня серьёзнее, чем junior, есть вероятность, что об этом спросят на собеседовании. А ты теперь это знаешь! Не благодари.

----

Много полезного на mynrg.ru

___________

Я - программист!

Шутеечки в Дневнике программиста

Чат Клуб программистов