Есть ли практический способ для неизменной структуры связанных узлов?

26

Я решил написать односвязный список, и у меня был план сделать внутреннюю структуру узлов неизменной.

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

1 -> 2 -> 3 -> 4

и сказать, что я хочу добавить 5.

Чтобы сделать это, так как узел 4является неизменным, мне нужно создать новую копию 4, но заменить его nextполе новым узлом, содержащим 5. Проблема сейчас в том, чтобы 3ссылаться на старое 4; тот, без добавления 5. Теперь мне нужно скопировать 3и заменить его nextполе для ссылки на 4копию, но теперь 2ссылается на старый 3...

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

Мои вопросы:

  • Правильно ли мое мышление? Есть ли способ сделать дополнение, не копируя всю структуру?

  • Видимо "Эффективная Java" содержит рекомендацию:

    Классы должны быть неизменяемыми, если только нет веской причины сделать их изменяемыми ...

    Это хороший случай для изменчивости?

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

Carcigenicate
источник
Я бы сказал, да - редкие неизменяемые коллекции в Java - это либо мутационные методы, переопределенные для выброса, либо невероятно дорогие CopyOnWritexxxклассы, используемые для многопоточности. Никто не ожидает, что коллекции действительно будут неизменными (хотя это создает некоторые причуды)
Ordous
9
(Прокомментируйте цитату.) Это, великая цитата, часто очень неправильно понимают. Неизменяемость должна применяться к ValueObject из-за его преимуществ , но если вы разрабатываете на Java, нецелесообразно использовать неизменяемость там, где ожидается изменчивость. В большинстве случаев у класса есть определенные аспекты, которые должны быть неизменяемыми, и определенные аспекты, которые должны изменяться в зависимости от требований.
Руонг
2
related (возможно, дубликат): объект коллекции лучше быть неизменным? «Можно ли представить эту коллекцию (класс LinkedList) как неизменную коллекцию без накладных расходов?»
Комнат
Зачем вам составлять неизменный связанный список? Самым большим преимуществом связанного списка является изменчивость, не лучше ли использовать массив?
Питер Б
3
Не могли бы вы помочь мне понять ваши требования? Вы хотите иметь неизменный список, который вы хотите изменить? Разве это не противоречие? Что вы имеете в виду под «внутренностями» списка? Вы имеете в виду, что ранее добавленные узлы не должны быть модифицируемыми позже, а разрешать добавление только к последнему узлу в списке?
ноль

Ответы:

46

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

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

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

2 -> 3 -> 4

Предъявление 1дает вам:

1 -> 2 -> 3 -> 4

Но обратите внимание, что это не имеет значения, если кто-то еще все еще держит ссылку в 2качестве главы своего списка, потому что список неизменен, и ссылки идут только в одну сторону. Там нет никакого способа сказать, что 1даже там, если у вас есть только ссылка на 2. Теперь, если вы добавили a 5в любой из списков, вам нужно будет сделать копию всего списка, потому что в противном случае он появится и в другом списке.

Карл Билефельдт
источник
Ааа, хороший вопрос о том, почему предварительное добавление не требует копии; Я не думал об этом.
Carcigenicate
17

Вы правы, добавление требует копирования всего списка, если вы не хотите изменять какие-либо узлы на месте. Поскольку нам нужно установить nextуказатель (теперь) второго до последнего узла, который в неизменяемом параметре создает новый узел, а затем нам нужно установить nextуказатель третьего до последнего узла и так далее.

Я думаю, что основная проблема здесь не в неизменности, и при этом appendоперация не опрометчива. Оба прекрасно в своих доменах. Смешивать их плохо: естественный (эффективный) интерфейс для неизменяемого списка подчеркивает манипуляцию в начале списка, но для изменяемых списков часто более естественно построить список путем последовательного добавления элементов от первого к последнему.

Поэтому я предлагаю вам принять решение: вы хотите эфемерный интерфейс или постоянный? Создают ли большинство операций новый список и оставляют ли неизмененную версию доступной (постоянной), или вы пишете такой код (эфемерный):

list.append(x);
list.prepend(y);

Оба варианта хороши, но реализация должна отражать интерфейс: постоянная структура данных выигрывает от неизменных узлов, в то время как эфемерная требует внутренней изменчивости, чтобы фактически выполнить обещания производительности, которые она неявно дает. java.util.Listи другие интерфейсы эфемерны: внедрение их в неизменяемый список неуместно и фактически представляет угрозу для производительности. Хорошие алгоритмы на изменяемых структурах данных часто сильно отличаются от хороших алгоритмов на неизменяемых структурах данных, поэтому преобразование неизменяемой структуры данных в изменчивую (или наоборот) требует плохих алгоритмов.

Хотя постоянный список имеет некоторые недостатки (нет эффективного добавления), это не должно быть серьезной проблемой при функциональном программировании: многие алгоритмы могут быть эффективно сформулированы путем изменения мышления и использования функций более высокого порядка, таких как mapили fold(чтобы назвать две относительно примитивные ), или добавив несколько раз. Более того, никто не заставляет вас использовать только эту структуру данных: когда другие (эфемерные или постоянные, но более сложные) более уместны, используйте их. Следует также отметить, что постоянные списки имеют некоторые преимущества для других рабочих нагрузок: они разделяют свои хвосты, что может экономить память.


источник
4

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

Функциональные языки, такие как prolog и haskel, предоставляют простые способы получить передний элемент и остальную часть массива. Присоединение к задней части - операция O (n) с копированием каждого узла.

чокнутый урод
источник
1
Я использовал Haskell. Afaik, это также обходит часть проблемы, используя лень. Я делаю добавления, потому что я думал, что это то, что ожидал Listинтерфейс (хотя я мог ошибаться там). Я не думаю, что этот бит действительно отвечает и на вопрос. Весь список все еще должен быть скопирован; это только сделало бы доступ к последнему добавленному элементу быстрее, так как полный обход не требовался.
Carcigenicate
Создание класса в соответствии с интерфейсом, который не соответствует базовой структуре данных / алгоритму, - это вызов боли и неэффективности.
фрик с трещоткой
JavaDocs явно использует слово «append». Вы говорите, что лучше игнорировать это ради реализации?
Carcigenicate
2
@Carcigenicate нет Я говорю, что это ошибка - пытаться вписать односвязный список с неизменяемыми узлами в формуjava.util.List
трещотка
1
С ленью больше не было бы связанного списка; нет списка, следовательно, нет мутации (приложение). Вместо этого есть некоторый код, который генерирует следующий элемент по запросу. Но его нельзя использовать везде, где используется список. А именно, если вы напишите в Java метод, который ожидает изменить список, который передается в качестве аргумента, этот список должен быть изменяемым в первую очередь. Генераторный подход требует полной реструктуризации (реорганизации) кода, чтобы он работал и чтобы физически можно было покончить со списком.
Rwong
4

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

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

Списки различий (см., Например, здесь ) являются интересной альтернативой. Список различий оборачивает список и обеспечивает операцию добавления в постоянное время. В основном вы работаете с оберткой столько времени, сколько вам нужно добавить, а затем по окончании конвертировать обратно в список. Это как-то похоже на то, что вы делаете, когда вы используете a StringBuilderдля создания строки и в конце получаете результат как String(неизменяемый!), Вызывая toString. Одно из отличий состоит в том, что StringBuilderпеременная переменная, но список различий неизменен Кроме того, когда вы преобразуете список различий обратно в список, вам все равно нужно создать весь новый список, но, опять же, вам нужно сделать это только один раз.

Должно быть довольно легко реализовать неизменный DListкласс, который предоставляет интерфейс, аналогичный интерфейсу Haskell Data.DList.

Джорджио
источник
4

Вы должны посмотреть это отличное видео из 2015 React conf создателя Immutable.js Ли Байрона. Это даст вам указатели и структуры, чтобы понять, как реализовать эффективный неизменяемый список, который не дублирует контент. Основные идеи заключаются в следующем: - пока два списка используют одинаковые узлы (одно и то же значение, один и тот же следующий узел), используется один и тот же узел - когда списки начинают различаться, в узле расхождения создается структура, которая содержит указатели на следующий конкретный узел каждого списка

Это изображение из учебника по реакции может быть более ясным, чем мой ломаный английский:введите описание изображения здесь

feydaykyn
источник
2

Это не строго Java, но я предлагаю вам прочитать эту статью о неизменной, но производительной индексируемой постоянной структуре данных, написанной на Scala:

http://www.codecommit.com/blog/scala/implementing-persistent-vectors-in-scala

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

Также обратите внимание на конструирование неизменяемых структур данных: вам обычно нужен своего рода «конструктор», который позволяет вам «мутировать» структуру данных «в стадии разработки», добавляя к ней элементы (в пределах одного потока); После того, как вы закончите добавление, вы вызываете метод объекта «в стадии разработки», такой как .build()или .result(), который «строит» объект, давая вам неизменную структуру данных, которую вы затем можете безопасно разделить.

Сандро Гржичич
источник
1
Есть вопрос о портах Java PersistentVector на stackoverflow.com/questions/15997996/…
James_pic
1

Подход, который иногда может быть полезен, состоит в том, чтобы иметь два класса объектов, содержащих список: объект прямого списка со finalссылкой на первый узел в списке с прямой связью и изначально нулевой не- finalссылку, которая (когда не -null) идентифицирует объект обратного списка, содержащий те же элементы в обратном порядке, и объект обратного списка со finalссылкой на последний элемент списка с обратной связью и изначально нулевой неконечной ссылкой, которая (если не -null) идентифицирует объект форвард-листа, содержащий те же элементы в обратном порядке.

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

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

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

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

Supercat
источник