В чем смысл PHP класса SplDoublyLinkedList и, что более важно, связанных списков в целом?

Question

В стремлении расширить свое мастерство программирования я чуть-чуть углубился в Стандартную библиотеку PHP . Это привело к моему открытию класса SplDoublyLinkedList. Оттуда я читаю описания Связанных списков и Вдвойне связанных списков в Википедии.

Я понимаю, как они работают ... Но я не могу понять причину, ПОЧЕМУ нам это нужно - или, что еще лучше, практический пример SplDoublyLinkedList, поскольку в PHP есть индексированные и ассоциативные массивы.

Как связанные списки обычно используются в PHP и вне его?

Answer 1

Структуры данных SPL снижают потребление памяти и повышают производительность.Хорошие объяснения:

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

Например, если вам не нужны возможности хэш-карты ассоциативного массива - то есть, если вы не используете ключ массива дляконкретной цели и нуждается только в перечисляемом массиве - SplFixedArray (ранее SplFastArray, в настоящее время недокументированный) может быть подходящей заменой.Единственное предостережение в том, что размер массива фиксирован, это означает, что вы должны указать размер при создании экземпляра класса, и произойдет ошибка, если вы попытаетесь сохранить больше, чем это количество элементов.Это причина того, что в среднем он работает лучше, чем стандартные массивы PHP.

http://web.archive.org/web/20130805120049/http://blueparabola.com/blog/spl-deserves-some-reiteration

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

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

В области компьютерных наук список определяется как упорядоченный набор значений.Связанный список - это структура данных, в которой каждый элемент списка содержит ссылку на один или оба элемента по обе стороны от него в списке.Термин «двусвязный список» используется для обозначения последнего случая.В SPL это принимает форму класса SplDoublyLinkedList .... Имеет смысл использовать списки, когда количество сохраняемых элементов заранее неизвестно и доступ к элементам требуется только по последовательной позиции.

http://matthewturland.com/2010/05/20/new-spl-features-in-php-5-3/

Answer 2

Согласно Википедии ,

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

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

Итак, чтобы ответить на ваш вопрос, я понятия не имею.:)

Answer 3

Прежде всего, SplDoublyLinkedList являются объектами, поэтому

• могут быть расширены, поэтому вы можете переопределить их методы (например, вы можете вернуть все строки в верхнем регистре и т. Д.))
• интерфейсы, которые они реализуют, можно проверить, как в myfunc( SplDoublyLinkedList $var ) ...
• они по умолчанию передаются в качестве ссылки
• и т. Д.

Во-вторых, SplDoublyLinkedList принимает итерационные режимы, поэтому вы можете удалять свои элементы на ходу и переключать направление, не переупорядочивая массив и не усложняя свой код:

SplDoublyLinkedList :: IT_MODE_LIFO (стиль стека)

SplDoublyLinkedList :: IT_MODE_FIFO (стиль очереди) Поведение итератора (одного или другого)

SplDoublyLinkedList :: IT_MODE_DELETE (элементы удаляются итератором)

SplDoublyLinkedList :: IT_MODE_KEEP (элементы просматриваются итератором)

цитата вышеявляетсяиз http://simpletechinfo.com/SplDoublyLinkedList, который содержит некоторые примеры кода.

Существуют и другие привилегии (например, foreach не нужно делать копию в памяти всех данных и т. д.)

Answer 4

Вы, вероятно, правы, и это просто не очень полезно.

В теории существует много применений связанных списков (особенно танцующих ссылок).Но большинство из них включает в себя либо сохранение и клонирование своих итераторов в другом месте, доступ к контенту более чем в двух направлениях, либо разделение и объединение списков.SplDoublyLinkedList, по-видимому, не имеет их.

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

Без этих функций они ведут себя как два запроса.Если вам нужен только доступ к элементам с помощью итератора, они похожи на два стека.Один лучший способ в однопоточных простых случаях, за исключением того, что класс еще не заключен в класс, - это просто использовать два стека (возможно, фиксированные массивы или оба конца одного и того же массива).Выдвигайтесь из одного стека и перемещайте его в другой всякий раз, когда вы хотите, чтобы итератор перемещался, а верхняя часть одного стека является текущим элементом.Если вам также нужен доступ к голове и хвосту, вам нужно заменить стеки на deques.

Но если вы хотите реализовать стеки или сами deques, не зная максимального размера, или даже выделить узлыобычные связанные списки (на языке без этих библиотек, как в PHP), хороший способ - объединить несколько фиксированных массивов вместе, используя двусвязные списки без этих функций.Каким-то образом вам все еще это понадобится.

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

Answer 5

Как уже упоминалось, списки являются альтернативой фиксированным массивам, которые распространены в других языках. Но один важный аспект, который часто упускается из виду, - вы можете очень эффективно вставить или удалить элемент из любого места в списке.

Почему это важно? Допустим, у вас есть несколько элементов, которые вы хотите сохранить отсортированными в массиве, возможно, чтобы вам не пришлось сортировать их позже или просто сократить время поиска. В этом случае список может быть очень мощным инструментом. Особенно для очень больших наборов данных.

Answer 6

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