Неизменная производительность структур данных
Я не добираюсь, как может что-то как Набор быть неизменным и все еще иметь приемлемую производительность.
Из того, что я читал в Наборах F#, внутренне используют Красные Черные Деревья в качестве их реализации. Если каждый раз мы хотим добавить что-то новое для Красного Черного Дерева, мы должны в основном воссоздать его, как оно может иметь когда-нибудь хорошую производительность? Что я пропускаю здесь?
Хотя я прошу у этого Наборы F#, я думаю, что это столь же релевантно на любом другом языке, который имеет или использует неизменные структуры данных.
Спасибо
8 ответов
Почти все неизменяемые коллекции представляют собой некую форму сбалансированного дерева. Чтобы создать новое дерево, нужно перераспределить узлы на пути от изменения (вставки, удаления, "обновления") до корня. Пока дерево сбалансировано, это занимает логарифмическое время. Если у вас есть что-то вроде дерева 2-3-4 (похожее на красно-черные деревья) с ожидаемой степенью убывания три, вы можете обработать миллион элементов, используя всего 10 распределений.
А в языках, где ожидается, что структуры данных будут чистыми, они заботятся о том, чтобы распределение было быстрым. Выделение четырехэлементного узла обойдется в сравнение, инкремент и четыре сохранения. И во многих случаях вы можете амортизировать стоимость сравнения в течение нескольких выделений.
Если вы хотите узнать больше о том, как работают эти структуры, отличным источником является Purely Functional Data Structures Криса Окасаки.
Нет необходимости воссоздавать дерево целиком. Многие ветки останутся прежними и их можно будет «использовать повторно». В качестве простого примера, если новый узел нужно добавить к листу в текущем дереве, тогда нужно клонировать только родителей этого узла и дать им новые ветви.
не уверен, как это реализовано на языке, но структуры данных могут восприниматься программистом как неизменные, но оптимизированные за кулисами.
например, у меня есть список a = [1,2,3,4,5]. Я добавляю 6. b = [a [6]], и оба они могут быть неизменяемыми. Вы не теряете производительность, делая это, и это быстрее, чем копирование значений.
Итак, позвольте мне спросить вас, потому что я не знаю, почему было бы медленнее делать вещи как неизменные? В случае с деревом я как бы понимаю вашу точку зрения. Я думаю, вам придется воссоздавать узлы над текущим узлом, но не ниже (при условии, что у нас есть дочерние указатели, а не родительские указатели).
Как указывали другие, вам не нужно заново создавать всю структуру данных. Вам просто нужно воссоздать части, которые изменились, и ссылаться на существующие поддеревья, которые остались прежними. Благодаря неизменности структуры данных вы можете повторно использовать поддеревья, поэтому копирование всего практически никогда не требуется. Фактически, если вам нужно редко клонировать изменяемую структуру данных, это может иметь гораздо большее влияние.
В частности, для сбалансированных деревьев (таких как красно-черные деревья) это дает вам:
- O (log N) время добавления / удаления элементов из набора (так же, как изменяемая реализация)
- O (log N) пространство (новые выделения) при добавлении / удалении элементов (изменяемые будут иметь O (1))
Это может - конечно - слишком много накладных расходов для некоторых приложений, но на самом деле это не так. все так плохо. Более того, распределение в сборщике мусора .NET происходит очень быстро (я думаю, по существу O (1) ), так что это не проблема. Большее выделение означает, что сборщик мусора должен запускаться чаще, но это также не так критично, как может показаться - в наши дни у компьютеров довольно много памяти. .NET 4.0 действительно помогает во многих случаях (см. Также ответ Джона Харропа здесь )
Как утверждали другие, неизменяемую структуру данных не нужно полностью воссоздавать, поскольку она может повторно использовать старые части самой себя. Вы можете сделать это, потому что старые части неизменяемы, и данные гарантированно не изменятся.
У меня есть реальный пример неизменной производительности. Я провел небольшое тестирование с неизменяемым деревом Red Black , созданным на F #, и оно работает только в 3 раза медленнее, чем std :: sort в C ++. Я думаю, это очень быстро, учитывая, что он не был разработан специально для сортировки.
См.
функциональное программирование: эффективность неизменяемых структур данных
(особенно мой ответ, который указывает на доклад Рича Хики) для "общего" убедительного доказательства того, что да, неизменяемые структуры также могут быть очень эффективными.
Что касается того, насколько это верно в конкретном случае F# Set, ну, возможно, сегодня это лишь умеренно. Было бы здорово использовать более эффективную базовую структуру (в прагматических терминах; в теоретических терминах, конечно, все O(logN) (что в практических терминах O(1))).
Проще говоря, Set - это объект хранения на основе узла. В случае набора вы можете реализовать его как дерево, в котором вы не воссоздаете все ребра и узлы, когда вы «добавляете» элемент в следующую версию набора, вместо этого вы просто создаете новый набор ребер. . Вы можете сделать это, потому что сами узлы никогда не изменятся, равно как и удерживаемые в них объекты.
Реальная выгода, которую он дает в однопоточных приложениях, а скорее в многопоточных. Неизменяемые структуры данных устраняют необходимость в механизмах блокировки. Если они никогда не изменятся, вам не нужно беспокоиться о состоянии.
Ограничения семантики языка относятся только к исходному коду на этом языке. Реализация (компилятор, интерпретатор, среда выполнения и т.д.) вольна делать все, что ей заблагорассудится для достижения наилучшей производительности, пока она сохраняет то же самое поведение. Это верно для большинства языков.
Редактировать:
Можно сделать несколько оптимизаций, включая совместное использование данных (именно потому, что данные неизменяемы), использование изменяемости за кулисами, оптимизацию хвостовых вызовов (поскольку FP использует много рекурсии) и другие.