на всякий случай повторю, что это за дерево такое. это у нас автобалансирующееся дерево (вариант Arne Andersson'а, хотя для реализации оно неважно). только вместо ключей каждая нода содержит два поля:
Код:
nodeSize: INTEGER;
sizeLeft: INTEGER;
соответственно, `nodeSize` — это размер спана, который покрывает данная нода, а `sizeLeft` — суммарный размер спанов в левом поддереве. знать размер правого поддерева нам не нужно, этого достаточно, чтобы эффективно найти ноду, соответствующую некоторой позиции (я называю её индексом), или имея ноду, вычислить её индекс.
то есть, у нас есть некий массив, состоящий из span'ов (или runs, это в данном случае синонимы). они же «кусочки» (pieces) — тоже синоним. у каждого кусочка есть некие атрибуты, и кусочки единичного размера с подходящими атрибутами могут быть объединены в один длинный кусочек размером sum(piece_length).
coincidentally, это очень удобная структура для текстовых документов (и в BBCB используется именно она). текст с одинаковыми атрибутами можно считать одним кусочком (если все его элементы идут в хранилище последовательно).
поскольку операции вставки и удаления в произвольные места такого массива — это основные операции редактирования, то использовать для хранения именно массив — неэффективно. да, поиск там O(1) (ну, всё тот же O(log N), если элементом массива может быть кусочек больше единичного размера), зато вставка и удаление — O(N) (worst time).
если мы будем хранить кусочки в двусвязном списке (как делает BBCB), то вставка и удаление станут O(1), зато поиск — O(N). это немного амортизируется кэшированием позиции последней найденой ноды, и перемещением при поиске от этой ноды, а не от начала/конца списка. в среднем ускорение при random access — около 1.8 (как демонтсрирует мой fuzzy test).
а вот если мы возьмём сбалансированое дерево для того же самого, то у нас и поиск, и вставка, и удаление будут O(log N). с учётом aa tree — O(2*log N) worst time. то есть, для текста в четыре гигабайта, который тщательно порубан на очень-очень маленькие кусочки, потребуется в среднем тридцать две операции (плюс-минус ещё пять-десять на ребалансировку). ни в какое сравнение со списками это не идёт. (разница во времени обработки достигает четырёх и более порядков: чем больше кусочков — тем больше разница.)
если к каждой ноде приделать ещё и указатель на родителя, это чуть-чуть усложнит балансировку (пара лишних присваиваний), но даст нам две полезные фичи.
во-первых, операции вставки и удаления больше не требуют дополнительной памяти (стека для рекурсии): мы можем нерекурсивно найти нужную ноду, а после изменений пойти вверх по дереву, чиня его по дороге. более-менее constant memory, стало быть. на самом деле это не то чтобы очень важно: рекурсия глубиной в 64 — это наихудший и невозможный случай — не проблема. но нерекурсивный метод ещё и чуть-чуть быстрее.
и во-вторых: наличие указателя на родителя позволяет организовать обход дерева в любом направлении за O(1), без дополнительной памяти и состояний: нужен только указатель на ноду, и от неё можно легко переместиться влево или вправо. это очень важно для итераторов (райдеров).
в общем, если заменить в TextModel списки на такие деревья, то мутации текстовой модели можно считать как constant cost, и даже почти zero cost — вне зависимости от того, последовательные ли они, или мутатор скачет по тексту как будто его оса в зад ужалила.
на практике эта структура данных работает в моём сишном редакторе текстов, и работает отлично: вне зависимости от сложности и размера текста, редактор реагирует на пользовательские (и скриптовые) мутации со скоростью примерно: «не успел ещё кнопку отпустить, а уже всё готово!»
также, при небольшой модификации такие деревья можно использовать для хранения, например, длин строк (в отдельном дереве, параллельно основному дереву кусочков). надо только добавить в ноду поля:
Код:
len: INTEGER;
lenLeft: INTEGER;
это длина строки, и сумма длин строк в левом поддереве. размер самой ноды в таком дереве всегда 1. `leftLen` надо не забывать чинить при балансировке, конечно.
такое «дерево длин» даёт нам возможность как быстро находить длину (и начальную позицию) строки по её номеру, так и номер строки по позиции внутри неё. в принципе, можно было бы считать строки обычными спанами, но при структуре с двумя размерами ускоряется операция «найти строку по её номеру».
точно так же никто не мешает хранить подобным образом не только длины строк, но и полноценную информацию о форматировании: высоту строки в юнитах, например. и делить текст не на строки по признаку 02X/0AX/0DX/0EX, а по ширине. тогда нам надо один раз при загрузке отформатировать текст, и при мутациях можно обходиться очень дешёвыми инкрементальными изменениями; заодно можно делать точный попиксельный скролл. единственная проблема — один и тот же TextView может быть показан в разных фрэймах одновременно. я ещё не придумал, как это красиво решить. (ideas are welcome!)
Вход
FAQ
Поиск
