Структуры данных, PHP

в 11:00, , рубрики: php, php 5.3, деревья, переводы, стек, структуры данных

Данный пост является переводом и предназначен для новичков. Ну или для тех, кто забыл лекции с начальных курсов своих вузов. Скорее всего, данный материал уже попадался на хабре в той или иной модификации, но здесь упор на PHP и его особенности.

Структуры данных или Абстрактный Тип Данных (ADT) — это модель, определенная как некий набор операций, которые могут быть применены к самой себе и ограничена тем, какой результат дают эти операции.
Большинство из нас сталкиваются со стеком и очередью в повседневной жизни, но что общего между очередью в супермакете и структурой данных? В этом мы и попробуем разобраться в данной статье, где также будут описаны деревья.

http://www.thisiscolossal.com/2013/01/a-wooden-domino-tree-by-qiu-zhijie/

  1. Стек
  2. Очередь
  3. Дерево

Стек

Стек, обычно, описывают как некий набор объектов, который сгруппирован вместе, где каждый элемент общего набора идет друг за другом — стопка книг или же подносы, сложенные между собой. В информатике же, стек — это набор объектов, имеющий общее правило образования: последний объект, помещенный в стек, извлекается первым из общего списка. Такое правило еще называют «Последний вошел, первый вышел» или LIFO. Есть и обратное правило — первый вошел, первый вышел (FIFO), но об этом чуть позже.
Данное правило, LIFO, используется, например, в автоматах по продаже сигарет, конфет — последний загруженный туда объект будет выдан первым.

Абстрактное определение стека — список, все операции для которого определены относительно одного конца, т.е. вершина стека.
Базовые операции, определяющие стек:

  • init – создать стек.
  • push – добавить элемент в начало (верх) стека, сдвинув остальные на 1 позицию вниз.
  • pop – извлечь (и удалить) элемент из стека (из вершины).
  • top – получить значение на первый элемент стека (не удаляя).
  • isEmpty – проверка стека на пустоту.

Также можно определить стек с максимально возможным количеством элементов, но это уже мелочи. Однако когда стек больше не может принимать элементы, то стек является переполненным и он возвращает сообщение об этом (stack overflow). Ну и обратная ситуация — изъятие элемента из пустого стека (stack underflow).

Зная то, что наш стек определен как LIFO и его базовые операции, мы можем написать наш стек через массив, тем более что мы уже имеем для это базовые операции push и pop. Наш пример будет таким:

<?php
class ReadingList
{
    protected $stack;
    protected $limit;
    
    public function __construct($limit = 10) {
        // инициализация стека
        $this->stack = array();
        // устанавливаем ограничение на количество элементов в стеке
        $this->limit = $limit;
    }

    public function push($item) {
        // проверяем, не полон ли наш стек
        if (count($this->stack) < $this->limit) {
            // добавляем новый элемент в начало массива
            array_unshift($this->stack, $item);
        } else {
            throw new RunTimeException('Стек переполнен!'); 
        }
    }

    public function pop() {
        if ($this->isEmpty()) {
            // проверка на пустоту стека
	      throw new RunTimeException('Стек пуст!');
	  } else {
            // Извлекаем первый элемент массива
            return array_shift($this->stack);
        }
    }

    public function top() {
        return current($this->stack);
    }

    public function isEmpty() {
        return empty($this->stack);
    }
}

В этом примере мы использовали функции PHP array_unshift() и array_shift() вместо array_push() and array_pop(), поэтому у нас первый элемент стека всегда будет сверху, иначе у нас вершиной был бы n-ый элемент стека. Особой разницы нет. Теперь добавим несколько элементов в наш стек:

<?php
$myBooks = new ReadingList();

$myBooks->push('A Dream of Spring');
$myBooks->push('The Winds of Winter');
$myBooks->push('A Dance with Dragons');
$myBooks->push('A Feast for Crows');
$myBooks->push('A Storm of Swords'); 
$myBooks->push('A Clash of Kings');
$myBooks->push('A Game of Thrones');

А теперь извлечем несколько элементов из него:

<?php
echo $myBooks->pop(); // Получили и удалили 'A Game of Thrones'
echo $myBooks->pop(); // Получили и удалили 'A Clash of Kings'
echo $myBooks->pop(); // Получили и удалили 'A Storm of Swords'

Что у нас теперь является вершиной стека?

<?php
echo $myBooks->top(); // Получили 'A Feast for Crows'

Если снова вызвать метод pop(), то «A Feast for Crows» будет удален из стека. Если же сделать push, а затем сразу pop, то стек не изменится, поскольку наш стек работает на основе «первый зашел, первый вышел». Если продолжать вытаскивать элементы из стека, то рано или поздно мы получим исключение с сообщением о том, что стек пуст.

SPLStack

PHP (Расширение SPL) предоставляет нам реализации разных структур данных, включая SplStack, начиная с версии 5.3. Мы можем создать наш ReadingList просто унаследовав его:

<?php
class ReadingList extends SplStack
{
}

SplStack дает нам чуть больше методов, чем мы определили ранее, потому как SplStack реализует двусвязный список, у которого есть емкость (количество элементов в стеке) для реализации перебора.

Связанный список, являющийся по сути другой абстрактной структурой, это список из узлов, каждый из которых имеет указатель на следующий объект. Данную структуру можно представить таким образом, с однонаправленным перебором:

Это изображение, К.О.

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

Это изображение, К.О.

Перебирая элементы, мы должны знать где у нас заканчивается весь список — для этого служат те самые элементы, перечеркнутые внутри.

Очередь

Вот мы и подошли к «первый вошел, первый вышел» или же FIFO. Любой, кто стоял в реальной очереди — знает, что тот, кто занял место первым, первым из нее и уйдет. Исключение — объекты, которым только подписать, спросить, etc.

Базовые операции для очередей такие:

  • init – создать очередь.
  • enqueue – добавить элемент в конец (хвост) очереди.
  • dequeue – удалить элемент из начала очереди (голова).
  • isEmpty – проверка очереди на пустоту.

P.S Для тех кто знаком с Прологом — в данном случае хвост не содержит в себе все элементы списка, за исключением головы.

PHP также предоставляет нам класс SplQueue (двусвязный список), только в данном случае голова списка — последний элемент. Определим наш ReadingList как очередь:

<?php
class ReadingList extends SplQueue
{
}

$myBooks = new ReadingList();

// добавим несколько элементов в нашу очередь
$myBooks->enqueue('A Game of Thrones');
$myBooks->enqueue('A Clash of Kings');
$myBooks->enqueue('A Storm of Swords');

SplQueue наследуется от SplDoublyLinkedList и реализует интерфейс доступа как к массиву, таким образом позволяя обращаться к нашим очередям и стекам через массивы:

<?php
$myBooks[] = 'A Feast of Crows';
$myBooks[] = 'A Dance with Dragons';

Удалим пару элементов из очереди:

<?php
echo $myBooks->dequeue() . "n"; // Выводит и удаляет 'A Game of Thrones'
echo $myBooks->dequeue() . "n"; // Выводит и удаляет 'A Clash of Kings'

enqueue() это альяс для push(), однако dequeue() не является альясом для pop()! У pop() другое поведение в контексте очереди, так как если мы воспользуемся pop(), то это удалит элемент из хвоста очереди (A Dance with Dragons), поскольку в очереди главным является правило FIFO.

Посмотреть (не удаляя) какой элемент является головой списка можно через метод bottom():

<?php
echo $myBooks->bottom() . "n"; // Выводит 'A Storm of Swords'

Деревья

Управление ADT обычно сводится к 3 операциям: вставка элементов с структуру, удаление и получение значения элемента из структуры. В отношении стека и очередей, данные операции зависимы от позиции (xIFO). Но что если нам нужно получить информацию по значению?

Представим, что у нас есть такая табличка (порядок элементов значения не имеет):

Это изображение, К.О.

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

Абстрактный пример данной структуры — таблица со следующими операциями:

  • create – создать пустую таблицу.
  • insert – добавить элемент в таблицу.
  • delete – удалить элемент из таблицы.
  • retrieve – найти элемент в таблице.

Да, это похоже на всем известный CRUD (Создание чтение обновление удаление) из баз данных, потому что деревья и базы данных тесно связаны между собой.

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

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

Это изображение, К.О.

Как видно из этой картинки — деревья это иерархическая структура, где между узлами есть связь родитель → потомок. Узел без потомка — корень дерева, потомок без родителя — вершина, связи между узлами — ребра. Узел и двумя потомками — простейшее дерево и основываясь на этом, мы можем представить дерево в виде рекурсивного списка таких узлов. Стоит отметить, что дерево по своей структуре напоминает двусвязный список.

Поэтому наше дерево можно описать следующим образом:

<?php
class BinaryNode
{
    public $value;    // значение узла
    public $left;     // левый потомок типа BinaryNode
    public $right;     // правый потомок типа BinaryNode

    public function __construct($item) {
        $this->value = $item;
        // новые потомки - вершина
        $this->left = null;
        $this->right = null;
    }
}

class BinaryTree
{
    protected $root; // корень дерева

    public function __construct() {
        $this->root = null;
    }

    public function isEmpty() {
        return $this->root === null;
    }
}
Вставка новых значений

Вставка новых значений уже куда более интересная тема. Есть несколько решений данной проблемы, основанных на вращении и балансировки дерева, и для разных задач можно использовать разные реализации деревьев, такие как красное-черное, АВЛ или Б деревья, имеющие разные показатели производительности в операциях вставки, удаления и обхода дерева.

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

  1. Если дерево пустое — вставим [новый_узел] как корень дерева (очевидно же!)
  2. пока (дерево не пустое):
    • 2a. Если ([текущий узел] пуст) — вставить сюда и остановиться;
    • 2b. Если ([новый_узел] > [текущий узел]) — пробуем вставить [новый_узел] справа и повторим шаг 2
    • 2c. Если ([новый_узел] < [текущий узел]) — пробуем вставить [новый_узел] слева и повторим шаг 2
    • 2d. Иначе значение уже в дереве

<?php
class BinaryTree
{
...
    public function insert($item) {
        $node = new BinaryNode($item);
        if ($this->isEmpty()) {
            // правило 1
            $this->root = $node;
        }
        else {
            // правило 1
            $this->insertNode($node, $this->root);
        }
    }
  
    protected function insertNode($node, &$subtree) {
        if ($subtree === null) {
            // правило 2
            $subtree = $node;
        }
        else {
            if ($node->value > $subtree->value) {
                // правило 2b
                $this->insertNode($node, $subtree->right);
            }
            else if ($node->value < $subtree->value) {
                // правило 2c
                $this->insertNode($node, $subtree->left);
            }
            else {
                // исключаем повторы, правило 2d
            }
        }
    }
}

Удаление узлов — совсем другая история и затрагиваться не будет. Возможно, как-нибудь в другой раз.

Обход дерева

Вспомним как мы начинали с корня и проходили дерево, узел за узлом, чтобы найти пустой узел. Есть 4 главных стратегии обхода дерева:

  • pre-order (прямой порядок)– обработка текущего узла, а затем переход к левому и правому.
  • in-order (симметричная) – сначала проход левой стороны, обработка текущего узла и обход правой стороны.
  • post-order (обратный порядок) – обход левой и правой стороны, затем обработка текущего значения.
  • level-order (в ширину) – обработка текущего значения, затем обработка потомков и переход на следующий уровень.

Первые три стратегии известны как обход в глубину, который начинается с корня дерева (ну или узла, обозначенного как узел) и проход максимально глубоко по дереву, как это возможно, перед тем как вернуться обратно. Каждая из этих стратегий используется в разных целях. Прямой порядок, например, используется при вставке новых узлов (наш случай) или копировании поддерева, обратный — наоборот, при удалении узлов из дерева.

Чтобы понять как работает симметричный проход нужно немного изменить наш пример:

<?php
class BinaryNode
{
...
    // сделаем симметричный проход текущего узла
    public function dump() {
        if ($this->left !== null) {
            $this->left->dump();
        }
        var_dump($this->value);
        if ($this->right !== null) {
            $this->right->dump();
        }
    }
}

class BinaryTree
{
...
    public function traverse() {
        // отображение дерева в возрастающем порядке от корня
        $this->root->dump();
    }
}

Заключение

Благодарю всех дочитавших до заключения, еще немного текста и картинки :)

Стоит отметить, что реализации SplStack, SplQueue и двусвязного списка не освещены полностью. В документации PHP по ним спрятано довольно много методов, в том числе подсчет количества элементов или использование структуры в качестве итератора.

Также стоит обратить внимание на данную статью от kpuzuc
Визуализацию этих структур, ссылки на которые можно найти в посте от tangro

Бенчмарки производительности реализаций данных структур скопипастил отсюда

image image

image image

image image

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

P.S. Как всегда в личку принимаются ошибки в тексте и переводе оригинала.

Автор: yTko

Источник

Поделиться

* - обязательные к заполнению поля