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

Question

Я не понимаю, как что-то в качестве набора может быть неизменным и при этом иметь приемлемую производительность.

Из того, что я прочитал в F # Наборы, внутренне используют Red Black Trees в качестве своей реализации.Если каждый раз, когда мы хотим добавить что-то новое в Красное Черное Дерево, мы должны в основном воссоздавать его, как оно может иметь хорошую производительность?Что мне здесь не хватает?

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

Спасибо

Answer 1

Почти все неизменные коллекции представляют собой некие формы сбалансированного дерева. Чтобы создать новое дерево, вы должны перераспределить узлы на пути от изменения (вставить, удалить, «обновить») к корню. Пока дерево сбалансировано, это занимает логарифмическое время. Если у вас есть что-то вроде дерева 2-3-4 (аналогично красно-черным деревьям) с ожидаемой степенью три, вы можете обработать миллион элементов, используя только 10 выделений.

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

Если вы хотите узнать больше о том, как работают эти структуры, отличный источник - Чисто функциональные структуры данных . Автор Chris Okasaki.

Answer 2

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

Answer 3

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

В частности, для сбалансированных деревьев (таких как красно-черные деревья) это дает:

• O (log N) время добавления / удаления элементов из набора (аналогично изменяемой реализации)
• O (log N) пробел (новые выделения) при добавлении / удалении элементов (изменяемый будет иметь O (1))

Это может быть - конечно - слишком много накладных расходов для некоторых приложений, но на самом деле это не так уж и плохо. Более того, распределение в сборщике мусора в .NET происходит очень быстро (я думаю, что по сути O (1) ), так что это на самом деле не проблема. Большее распределение означает, что GC должен запускаться чаще, но это также не так критично, как может показаться - в наши дни у компьютеров достаточно много памяти. .NET 4.0 действительно помогает во многих случаях (см. Также ответ Джона Харропа здесь )

Answer 4

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

У меня есть реальный пример неизменной производительности.Я провел некоторое тестирование с неизменным красно-черным деревом , которое я сделал в F #, и оно работает только в 3 раза медленнее, чем std :: sort в c ++.Что, на мой взгляд, действительно быстро, учитывая, что оно не было разработано специально для сортировки.

Answer 5

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

Edit:

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

Answer 6

См.

функциональное программирование: эффективность неизменной структуры данных

(особенно мой ответ, который указывает на выступление Рича Хики) за "общее" убедительное доказательство того, что да, неизменные структуры также могут быть очень эффективными.

Что касается того, насколько хорошо это верно в конкретном случае F # Set, ну, может быть, только умеренно, сегодня. Было бы здорово использовать более эффективную базовую структуру (в прагматических терминах; в теоретических терминах, конечно, все является O (logN) (что в практических терминах O (1)) ).

Answer 7

Проще говоря, Set - это объект хранения на основе узла. В случае набора вы можете реализовать его в виде дерева, в котором вы не воссоздаете все ребра и узлы, когда «добавляете» элемент в следующую версию набора, вместо этого вы просто создаете новый набор ребер , Вы можете сделать это, потому что сами узлы никогда не изменятся, равно как и объекты, содержащиеся в них.

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

Answer 8

не знаю, как это реализовано в языке, но структуры данных могут восприниматься программистом как неизменяемые, но их можно оптимизировать за кулисами.1,2,3,4,5].Я добавляю 6. b = [a [6]], и они оба могут быть неизменными.Делая это, вы не теряете производительности, и это быстрее, чем копирование значений.

Итак, позвольте мне спросить вас, потому что я не знаю, почему было бы медленнее делать вещи неизменными?В случае с деревом я как бы понимаю твою точку зрения.Я думаю, вам придется воссоздавать узлы выше текущего узла, но не ниже (при условии, что у нас есть дочерние указатели, а не родительские указатели).