Почему FingerTrees не используются достаточно для стабильной реализации?

Question

Некоторое время назад я наткнулся на статью о FingerTrees (см. Также сопровождающий вопрос о переполнении стека) и отослал эту идею. Я наконец нашел причину использовать их.

Моя проблема в том, что пакет Data.FingerTree, кажется, немного гниет по краям. Более того, Data.Sequence в пакете Containers, который использует структуру данных, повторно реализует (возможно, лучшую) версию, но не экспортирует ее.

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

---

дальнейшее объяснение:

Я заинтересован в создании структуры данных, содержащей текст, который имеет хорошие свойства конкатенации. Подумайте о создании документа HTML из разных фрагментов. Большинство готовых решений используют строки байтов, но я действительно хочу что-то, что правильно работает с текстом Unicode. В настоящий момент я планирую наложить фрагменты Data.Text на FingerTree.

Я также хотел бы позаимствовать уловку из Data.Vector получения срезов без копирования с использованием манипуляции (смещение, длина). Data.Text.Text имеет это встроенное в тип данных, но использует его только для эффективных операций типа "без" и "без операции". В FingerTree эта информация может очень легко стать v или аннотация дерева.

Answer 1

Чтобы ответить на ваш вопрос о пальчиковых деревьях, в частности, я думаю, что проблема заключается в том, что они имеют относительно высокие постоянные затраты по сравнению с массивами и являются более сложными, чем другие способы достижения эффективной конкатенации. Builder имеет более эффективный интерфейс для добавления кусков, и они обычно легко доступны (см. Ссылки в ответе @informatikr). Предположим, что Data.Text.Lazy реализуется с помощью связанного списка чанков, и вы создаете Data.Text.Lazy от застройщика. Если у вас не много кусков (вероятно, больше 50) или вы неоднократно обращаетесь к данным в конце списка, высокая постоянная стоимость дерева пальца, вероятно, не стоит этого.

Data.Sequence реализация специализируется по соображениям производительности и не является такой же общей, как полный интерфейс, предоставляемый fingertree пакет. Вот почему он не экспортируется; на самом деле не возможно использовать его для чего-либо, кроме Sequence,

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

Я действительно не получил это, пока я не прочитал серию блога Chung-chieh Shan о числах слов ( часть 2, часть 3, часть 4). Это доказательство того, что идея определенно может быть использована в практическом коде.

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

Возможно, вас заинтересует мой пакет splaytree, который предоставляет деревья сплайнов с моноидальными аннотациями, и на них строится несколько различных структур. Кроме самого дерева, Set а также RangeSet модули имеют более или менее полные API, Sequence Модуль в основном скелет, который я использовал для тестирования. Это не решение "с батарейками" для того, что вы ищете (опять же, ответ @informatikr дает их), но если вы хотите поэкспериментировать с моноидальными аннотациями, это может быть более полезным, чем Data.FingerTree, Имейте в виду, что дерево сплайнов может выйти из равновесия, если вы пересекаете все элементы в последовательности (или непрерывно переходите к концу, или подобному), но если добавление и поиск чередуются, производительность может быть превосходной.

Answer 2

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

Общее резюме:

• Data.Sequence имеет большие постоянные факторы и асимптотику: это почти так же быстро, как [] при доступе к началу списка (где обе структуры данных имеют O(1) асимптотику), и намного быстрее в других местах списка (где Data.Sequence логарифмическая асимптотика [] линейная асимптотика).

• Data.FingerTree имеет ту же асимптотику, что и Data.Sequence, но примерно на порядок медленнее.

Как и списки, у деревьев пальца большие накладные расходы на элемент, поэтому их следует комбинировать с разбиением на фрагменты для лучшего использования памяти и кэша. Действительно, несколько пакетов делают это ( Yi, Trifecta, веревка). Если Data.FingerTree может быть приближен к Data.Sequence в исполнении, я бы хотел увидеть Data.Text.Sequence тип, в котором реализовано пальчиковое дерево Data.Text ценности. Такой тип потерял бы потоковое поведение Data.Text.Lazy, но выиграть от улучшенного произвольного доступа и производительности конкатенации. (Точно так же хотелось бы посмотреть Data.ByteString.Sequence а также Data.Vector.Sequence.)

Препятствием для их реализации в настоящее время является то, что не существует эффективной и общей реализации деревьев пальцев (см. Ниже, где я буду обсуждать это далее). Производить эффективные реализации Data.Text.Sequence нужно было бы полностью переопределить пальчики, специализирующиеся на Text - как только Data.Text.Lazy полностью переписывает списки, специализированные на Text, К сожалению, деревья пальца намного сложнее, чем списки (особенно объединение!), Так что это значительный объем работы.

Итак, как я понимаю, ответ:

• специализированные пальчики это здорово, но много работы для реализации
• пальчиковые деревья (например, Data.Text.Sequence) было бы здорово, но в настоящее время плохая производительность Data.FingerTree означает, что они не являются жизнеспособной альтернативой группированным спискам в общем случае
• строители и чанкованные списки достигают многих преимуществ чанкованных пальчиков, поэтому их достаточно для общего случая
• в редком случае, когда не хватает строителей и списков фрагментов, мы стискиваем зубы и смиряемся с плохими постоянными факторами деревьев фрагментированных пальцев (например, в yi и trifecta).

Препятствия на пути к эффективному и общему пальчиковому дереву

Большая часть разрыва в производительности между Data.Sequence а также Data.FingerTree из-за двух оптимизаций в Data.Sequence:

• Тип меры специализируется на Int Таким образом, мера манипуляций скомпилируется в эффективную целочисленную арифметику

• Тип меры распаковывается в Deep конструктор, который сохраняет разыменования указателя во внутренних циклах операций с деревом.

Можно применить эти оптимизации в общем случае Data.FingerTree используя семейства данных для универсальной распаковки и используя inliner и специалиста GHC - посмотрите мой пакет без отпечатков пальцев, который доводит общую производительность дерева пальцев практически до уровня Data.Sequence, К сожалению, у этих методов есть некоторые существенные проблемы:

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

• деревья пальца используют полиморфную рекурсию, с которой специалист GHC плохо справляется ( 1, 2). Это означает, что, чтобы получить достаточную специализацию для типа меры, нам нужно много INLINE прагмы, которая заставляет GHC генерировать огромное количество кода.

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

Answer 3

Не обращая внимания на ваш вопрос о Finger Tree и отвечая только на ваше дальнейшее объяснение: вы изучили Data.Text.Lazy.Builder или, особенно для создания HTML, blaze-html?

Оба позволяют быстрое объединение. Для нарезки, если это важно для решения вашей проблемы, они могут не иметь идеальной производительности.