Непрерывные характеристики структур данных

Ответ 1

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

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

Если вы хотите узнать больше о том, как работают эти структуры, отличным источником является Чисто функциональные структуры данных Криса Окасаки.

Ответ 2

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

Ответ 3

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

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

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

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

Ответ 4

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

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

Ответ 5

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

Edit:

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

Ответ 6

См.

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

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

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

Ответ 7

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

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

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

Ответ 8

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

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