Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Конструкции данных, PHP

Anna | 31.05.2014 | нет комментариев

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

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

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

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

Стек

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

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

  • init – сделать стек.
  • push – добавить элемент в предисловие (верх) стека, сдвинув остальные на 1 позицию вниз.
  • pop – извлечь (и удалить) элемент из стека (из вершины).
  • top – получить значение на 1-й элемент стека (не удаляя).
  • 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 {
            // Извлекаем 1-й элемент массива
            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(), следственно у нас 1-й элемент стека неизменно будет сверху, напротив у нас вершиной был бы 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, то стек не изменится, от того что наш стек работает на основе «1-й зашел, 1-й вышел». Если продолжать вытягивать элементы из стека, то рано либо поздно мы получим исключение с сообщением о том, что стек пуст.

SPLStack

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

<?php
class ReadingList extends SplStack
{
}

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

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

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

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

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

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

Очередь


Вот мы и подошли к «1-й вошел, 1-й вышел» либо же 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, скажем). Впрочем у последовательной записи есть минус — она дрянна для вставок и удаления данных, в то время как связанная разрешает динамически выделять место под новые данные. Также, последовательная запись с фиксированной длиной менее результативна, чем связанная. Следственно для бинарного дерева поиска отменнее предпочесть связанную запись.

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

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

Как видно из этой картинки — деревья это иерархическая конструкция, где между узлами есть связь родитель mk!br/>

<?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();
    }
}

Завершение

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

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

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

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

взглянуть

imageimage

imageimage

imageimage

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

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

Продолжать перевод оригинала?

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

Проголосовало 49 человек. Воздержалось 6 человек.

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB