В стремлении расширить свое мастерство в программировании я так часто вникал в стандартную библиотеку PHP . Это привело к моему открытию класса SplDoublyLinkedList . Оттуда я прочитал описания Связанных списков и дважды связанных списков в Википедии.
Я понимаю, как они работают … Но я не могу представить себе причину, ПОЧЕМУ она нам нужна, или, еще лучше, практический пример SplDoublyLinkedList поскольку мы имеем индексированные и ассоциативные массивы в PHP.
Как связаны списки ссылок, обычно используемые внутри и вне PHP?
Структуры данных 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/
Прежде всего, 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, не требующие копирования в памяти всех данных и т. Д.),
Согласно Википедии ,
Основное преимущество связанного списка над обычным массивом состоит в том, что порядок связанных элементов может отличаться от порядка хранения элементов данных в памяти или на диске. По этой причине связанные списки позволяют вставлять и удалять узлы в любой точке списка с постоянным количеством операций.
С другой стороны, связанные списки сами по себе не позволяют осуществлять произвольный доступ к данным или любую форму эффективной индексации. Таким образом, многие основные операции, такие как получение последнего узла списка или поиск узла, содержащего заданную датуму, или определение места, где должен быть вставлен новый узел, могут потребовать сканирования большинства элементов списка.
Поэтому, чтобы ответить на ваш вопрос, я понятия не имею. 🙂
Они там, потому что для них используются многие программисты, работающие с другими языками, где массивы имеют фиксированные размеры, и вы должны заботиться о управлении памятью.
Поэтому для PHP это еще один инструмент. Они реализованы потому, что многие алгоритмы и ретрансляция шаблонов в списках и поэтому их не нужно менять на php-массивы.
Как отмечали другие, списки являются альтернативой фиксированным массивам, которые распространены на других языках. Но один важный аспект, который часто упускается из виду – вы можете очень эффективно вставлять или удалять элемент из любого места в списке.
Почему это важно? Допустим, у вас есть несколько элементов, которые вы хотите сохранить в массиве, возможно, поэтому вам не нужно сортировать их позже или просто для минимизации времени поиска. В этом случае List может быть очень мощным инструментом. Особенно для очень больших наборов данных.
Вы, вероятно, правы, и это просто не очень полезно.
Существует много видов использования связанных списков в теории (в частности, танцевальные ссылки). Но большинство из них связано с хранением и клонированием своих итераторов в другом месте, доступом к содержимому более чем в двух направлениях или разделением и объединением списков. У SplDoublyLinkedList, похоже, не было таких.
Если это не алгоритмы, одно из них – позволить объекту удалять ссылку на себя в каком-либо списке за постоянное время, освобождая свою память и не перетасовывая список (путем хэширования или замены с последним элементом) после вставки или удаления. Но для этого требуется хранить итератор списка в этих объектах.
Без этих функций они просто ведут себя как два уважения. Если вам нужен только доступ к элементам с помощью итератора, они похожи на два стека. Один из лучших способов в однопоточных простых случаях, запрещающий уже не завернутый в класс, – это просто использовать два стека (возможно, фиксированные массивы или оба конца одного и того же массива). Поп из одного стека и нажимайте его на другой, когда хотите, чтобы итератор перемещался, а верхняя часть одного стека – это текущий элемент. Если вам также нужно получить доступ к голове и хвосту, вам нужно будет заменить стеки на deques.
Но если вы хотите сами реализовать стеки или deques, не зная максимального размера или даже назначать узлы нормальных связанных списков (на языке без таких библиотек, как в PHP), хорошим способом является объединение некоторых фиксированных массивов вместе, используя вдвойне связанных списков без этих функций. Как-то вам все еще нужно.
Сама документация PHP, как и Java, предполагает, что они должны быть просто деком, поддерживающими некоторые дополнительные странные функции, даже не два двух (я думаю). Не используйте их, если вам действительно нужны дважды связанные списки.