Вопрос по – Эффективная реализация неизменяемого (двойного) LinkedList

6

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

Предположительно у нас есть общий класс Node:

<code>class Node{
    private Object value;
    private Node next;
}
</code>

И класс LinkedList, основанный на вышеупомянутом, позволяющий пользователю добавлять, удалять и т. Д. Теперь, как бы мы обеспечили неизменность? Должны ли мы рекурсивно копировать все ссылки на список при вставке элемента?

Мне также интересно узнать ответыНеизменный или не неизменный? это упоминание оптимизации cerain приводит к log (n) времени и пространства с помощью бинарного дерева. Также я где-то читал, что добавление элемента в начало равно 0 (1). Это меня очень озадачивает, так как если бы мы не предоставили копию ссылок, то в действительности мы модифицируем одни и те же структуры данных в двух разных источниках, что нарушает неизменность ...

Будет ли какой-либо из ваших ответов работать в двухсвязных списках? Я с нетерпением жду любых ответов / указателей на любые другие вопросы / решения. Заранее спасибо за помощь.

Ваш Ответ

3   ответа
0

использование неизменяемых карт

Для связанного списка строк (в псевдокоде в стиле Scala):

case class ListItem(s:String, id:UUID, nextID: UUID)

тогдаListItems может храниться на карте, где ключUUID: type MyList = Map[UUID, ListItem]

Если я хочу вставить новыйListItem вval list : MyList :

def insertAfter(l:MyList, e:ListItem)={ 
     val beforeE=l.getElementBefore(e)
     val afterE=l.getElementAfter(e)
     val eToInsert=e.copy(nextID=afterE.nextID)
     val beforeE_new=beforeE.copy(nextID=e.nextID)
     val l_tmp=l.update(beforeE.id,beforeE_new)
     return l_tmp.add(eToInsert)
}

кудаadd, update, get занимает постоянное время, используяMap: http://docs.scala-lang.org/overviews/collections/performance-characteristics

Реализация двойного связанного списка происходит аналогично.

18

on the above allowing the user to add, remove etc. Now, how would we ensure immutability?

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

Should we recursively copy all the references to the list when we insert an element?

Вы могли бы. Различие, которое вы получаете здесь, это разница междуimmutable а такжеpersistent, Неизменная структура данных не может быть изменена.persistent структура данных использует тот факт, что структура данных является неизменной для повторного использования ее частей.

Постоянный неизменяемый связанный список особенно прост:

abstract class ImmutableList
{
    public static readonly ImmutableList Empty = new EmptyList();
    private ImmutableList() {}
    public abstract int Head { get; }
    public abstract ImmutableList Tail { get; }
    public abstract bool IsEmpty { get; }
    public abstract ImmutableList Add(int head);
    private sealed class EmptyList : ImmutableList
    {
        public override int Head { get {  throw new Exception(); } }
        public override ImmutableList Tail { get { throw new Exception(); } }
        public override bool IsEmpty { get { return true; } }
        public override ImmutableList Add(int head)
        {
            return new List(head, this);
        }
    }

    private sealed class List : ImmutableList
    {
        private readonly int head;
        private readonly ImmutableList tail;
        public override int Head { get { return head; } }
        public override ImmutableList Tail { get { return tail; } }
        public override bool IsEmpty { get { return false; } }
        public override ImmutableList Add(int head)
        {
            return new List(head, this);
        }
    }
}
...
ImmutableList list1 = ImmutableList.Empty;
ImmutableList list2 = list1.Add(100);
ImmutableList list3 = list2.Add(400);

И вот, пожалуйста. Конечно, вы хотели бы добавить лучшую обработку исключений и больше методов, таких какIEnumerable<int> методы. Но есть постоянный неизменный список. Каждый раз, когда вы создаете новый список, вы повторно используете содержимое существующего неизменяемого списка; list3 повторно использует содержимое list2, что он может сделать безопасно, потому что list2 никогда не изменится.

Would any of your answers also work on doubly-linked lists?

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

Делаяpersistent Список с двумя связями довольно сложен, но есть способы сделать это. То, что я хотел бы сделать, это подойти к проблеме с другой стороны. Вместо того чтобы сказать "могу ли я создать постоянный список с двумя связями?" спросите себя: "Каковы свойства списка с двумя связями, который я нахожу привлекательным?" Перечислите эти свойства и посмотрите, сможете ли вы придумать постоянную структуру данных с этими свойствами.

Например, если вам нравится свойство, состоящее в том, что двусвязные списки можно дешево расширять с любого конца, дешево разбивать пополам на два списка, и два списка можно дешево объединять вместе, тогда необходимая постоянная структураimmutable catenable deque, а не двусвязный список. Я привожу пример неизменяемой некатенабельной декы здесь:

http://blogs.msdn.com/b/ericlippert/archive/2008/02/12/immutability-in-c-part-eleven-a-working-double-ended-queue.aspx

Расширение его до дееспособного deque оставлено в качестве упражнения; документ, на который я ссылаюсь на пальцах, хорош для чтения.

ОБНОВИТЬ:

according to the above we need to copy prefix up to the insertion point. By logic of immutability, if w delete anything from the prefix, we get a new list as well as in the suffix... Why to copy only prefix then, and not suffix?

Хорошо рассмотрим пример. Что если у нас есть список (10, 20, 30, 40), и мы хотим вставить 25 в позицию 2? Итак, мы хотим (10, 20, 25, 30, 40).

Какие части мы можем использовать повторно? Хвосты, которые мы имеем в руках (20, 30, 40), (30, 40) и (40). Очевидно, что мы можем использовать повторно (30, 40).

Рисование диаграммы может помочь. У нас есть:

10 ----> 20 ----> 30 -----> 40 -----> Empty

и мы хотим

10 ----> 20 ----> 25 -----> 30 -----> 40 -----> Empty

так что давайте сделаем

| 10 ----> 20 --------------> 30 -----> 40 -----> Empty
|                        /
| 10 ----> 20 ----> 25 -/ 

Мы можем повторно использовать (30, 40), потому что эта часть является общей для обоих списков.

ОБНОВИТЬ:

Would it be possible to provide the code for random insertion and deletion as well?

Вот этоrecursive решение:

ImmutableList InsertAt(int value, int position)
{
    if (position < 0) 
        throw new Exception();
    else if (position == 0) 
         return this.Add(value);
    else 
        return tail.InsertAt(value, position - 1).Add(head);
}

Do you see why this works?

Теперь в качестве упражнения напишем рекурсивный DeleteAt.

Теперь, в качестве упражнения, напишитеnon-recursive Вставить и удалить. Помните,you have an immutable linked list at your disposal, так что вы можете использовать один в своем итеративном решении!

Можно ли будет предоставить код для случайной вставки и удаления? Btw. Есть ли какие-либо статьи / вопросы о подобных структурах данных, таких как очереди, карты, деревья и т. д. Bober02
Большое спасибо за это. Кстати, в соответствии с вышеизложенным нам нужно скопировать префикс до точки вставки. По логике неизменности, если мы удалим что-либо из префикса, мы получим новый список, а также суффикс ... Зачем тогда копировать только префикс, а не суффикс? Bober02
@ Bober02: я добавил рекурсивное решение. Мой совет - изучить его, а затем написать нерекурсивное решение, которое делает то же самое. Вы должны прочитать мою серию блогов о неизменных структурах данных; один, у которого есть основы, возьмите книгу Окасаки; это отлично, но очень глубоко.
Еще раз спасибо, Эрик, очень ценю ваше время. Надеюсь, у вас будет еще одна минута на эти два простых вопроса: вы говорите «постоянный список с двумя связями»; трудно. Что вы подразумеваете под настойчивым? Я также прокомментировал ваш другой вопрос, в котором вы написали, что вставка может быть уменьшена до log (n) с использованием деревьев с открытыми границами. Это потому, что нам не нужно копировать левую / правую часть дерева, если мы вставляем в правое / левое поддерево? еще раз спасибо Bober02
@ Bober02: я сказал в своем ответе, что я имею в виду под "постоянным". Постоянная структура данных - это та, в которой вы можете повторно использовать большую ее часть. Относительно вставки двоичного дерева: да, но лучший способ охарактеризовать, почему вставка в сбалансированное дерево - это log n, потому что вставка в деревоrewrites the spine of the tree, Позвоночник имеет длину log n в сбалансированном по высоте дереве.
0

rt an element?

Вы должны рекурсивно копировать префикс списка до точки вставки, да.

Это означает, что вставка в неизменный связанный списокO(n), (Как вставить (не перезаписать) элемент в массиве).

По этой причине вставка обычно не одобряется (наряду с добавлением и объединением).

Обычной операцией над неизменяемыми связанными списками является «cons», то есть добавление элемента в начале, чтоO(1).

Вы можете ясно видеть сложность, например, в реализация Haskell. Учитывая связанный список, определенный как рекурсивный тип:

data List a = Empty | Node a (List a)

мы можем определить «минусы» (вставка элемента спереди) непосредственно как:

cons a xs = Node a xs

ЯвноO(1) операция. При этом вставка должна быть определена рекурсивно - путем нахождения точки вставки. Разбить список на префикс (скопированный) и поделиться им с новым узлом и ссылкой на (неизменяемый) хвост.

Важно помнить о связанных списках:

linear access

Для неизменяемых списков это означает:

copying the prefix of a list sharing the tail.

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

Хорошо, тогда зачем копировать префикс? По этой логике, если мы удалим что-либо из префикса, мы также получим новый список ... Зачем тогда его копировать? Bober02
Вы должны скопировать префикс, иначе вставка не является чистой, но имеет побочный эффект изменения списка для всех списков, которые указывают на префикс.
Извините, но все еще не понимаю. Что вы подразумеваете под "чистым"? И снова, почему префикс отличается от суффикса? Еще раз спасибо за ваши комментарии BTW, так как вставка - это O (n) в пространстве и времени, и, как я уже упоминал, вы, очевидно, можете использовать деревья, чтобы уменьшить его до Long (n), не могли бы вы предоставить некоторые комментарии по этому поводу? Bober02
Спасибо за Ваш ответ. Вы упоминаете & quot; Вы должны рекурсивно копировать префикс списка до точки вставки & quot; Поэтому, если у меня есть список 1-> 2-> 3 и я вставляю ноль в начале, согласно вашему утверждению, мне не нужно ничего копировать. Теперь, если я удаляю 2, то я изменил две отдельные копии, так как они обе имеют ТОЧНО одинаковые хвостовые узлы ... Я предполагаю, что здесь отсутствует sth ... Я просто не могу понять, почему мы должны копировать префикс, но не суффикс, потому что если мы удалим элемент в суффиксе, оба списка будут затронуты Bober02
@ Bober02: Вы все еще думаете, что структуры данных изменчивы. Если вы удалите элемент в суффиксе, тоyou have an entirely new list, Вы не мутировали какой-либо объект, от которого зависят другие объекты.

Похожие вопросы