Начальная загрузка древовидной структуры Finger

После небольшой работы с 2-3 пальцами я был впечатлен их скоростью в большинстве операций. Однако одна проблема, с которой я столкнулся, - это большие накладные расходы, связанные с первоначальным созданием большого дерева пальцев. Поскольку построение определяется как последовательность операций конкатенации, вы в конечном итоге создаете большое количество ненужных древовидных структур.

Из-за сложной природы деревьев 2-3 пальцев я не вижу интуитивно понятного метода их начальной загрузки, и все мои поиски оказались пустыми. Итак, вопрос в том, как вы могли бы начать загрузку дерева из 2-3 пальцев с минимальными накладными расходами?

Чтобы быть явным: с учетом последовательности известной длины n сгенерировать представление дерева S для пальца с минимальными операциями.$S$$n$$S$

Наивный способ выполнения - последовательные вызовы операции «против» (в литературе оператор « »). Тем не менее, это создаст n различных структур дерева пальца, представляющих все срезы S для [ 1 .. i ] .$\triangleleft$$n$$S$$[1..i]$

GHC - х Data.Sequence«s replicateфункция строит fingertree в пространство и время, но это разрешено, зная элементы , которые идут на праве ребра дерева пальца от начала. Эта библиотека была написана авторами оригинальной статьи на 2-3 пальца деревьев.$O(\lg n)$

Если вы хотите построить пальчиковое дерево путем многократной конкатенации, вы можете уменьшить временное использование пространства при построении, изменив представление шипов. Колючки на деревьях 2-3 пальцев искусно хранятся в виде синхронизированных списков с односвязными связями. Если вместо этого вы сохраняете шипы как запросы, может быть возможно сэкономить место при объединении деревьев. Идея состоит в том, что объединение двух деревьев одинаковой высоты занимает место путем повторного использования шипов деревьев. При объединении 2-3-х пальцевых деревьев, как первоначально описано, колючки, которые являются внутренними для нового дерева, больше не могут использоваться как есть.$O(1)$

Каплан и Тарьян в «Чисто функциональных представлениях отсортированных списков, которые можно было бы каталировать» описывают более сложную структуру пальца. В этой статье (в разделе 4) также обсуждается конструкция, аналогичная предложению deque, которое я сделал выше. Я полагаю, что структура, которую они описывают, может объединить два дерева одинаковой высоты в времени и пространстве. Для создания пальмовых деревьев достаточно места для вас?$O(1)$

NB: использование ими слова «начальная загрузка» означает что-то немного отличное от того, которое вы использовали выше. Они означают хранение части структуры данных с использованием более простой версии той же структуры.

Опираясь на превосходный ответ jbapple относительно replicate, но используя вместо этого replicateA(который replicateпостроен на), я придумал следующее:

--Unlike fromList, one needs the length explicitly. 
myFromList :: Int -> [b] -> Seq b
myFromList l xs = flip evalState xs $ Seq.replicateA l go
    where go = do
           (y:ys) <- get
            put ys
            return y

myFromList(в нескольких более эффективной версии) уже определен и используются внутри в Data.Sequenceпостроении пальцев дерев , которые являются результатами сортов.

В общем, интуиция для replicateAпроста. replicateAпостроен поверх функции ApplicativeTree . applicativeTreeзанимает кусок дерева размером mи создает хорошо сбалансированное дерево, содержащее его nкопии. Случаи nдо 8 (один Deepпалец) жестко закодированы. Что-нибудь выше этого, и это вызывает себя рекурсивно. «Аппликативный» элемент заключается просто в том, что он чередует конструкцию дерева с помощью потоковых эффектов, таких как, в случае приведенного выше кода, состояние.

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

Еще несколько конкретных заметок

main = print (length (show (Seq.fromList [1..10000000::Int])))

На некоторых простых тестах это привело к интересному компромиссу производительности. Основная функция выше с myFromList почти на 1/3 ниже, чем сfromList . С другой стороны, myFromListиспользуется постоянная куча 2 МБ, в то время как стандартная fromListиспользуется до 926 МБ. Это 926MB возникает из-за необходимости хранить весь список в памяти сразу. Между тем, решение с myFromListвозможностью использования структуры ленивым потоковым способом. Проблема со скоростью связана с тем, что myFromListнеобходимо выполнить примерно вдвое больше распределений (в результате построения пары / разрушения государственной монады), чемfromList, Мы можем устранить эти распределения, перейдя к монаде состояния, преобразованной в CPS, но это приводит к тому, что в любой момент времени удерживается гораздо больше памяти, потому что потеря лени требует обхода списка без использования потоковой передачи.

С другой стороны, если вместо того, чтобы форсировать всю последовательность шоу, я перехожу к простому извлечению головы или последнего элемента, myFromListнемедленно представляет больший выигрыш - извлечение элемента головы происходит практически мгновенно, а извлечение последнего элемента составляет 0,8 с. , Между тем, при использовании стандарта fromListизвлечение заголовка или последнего элемента стоит ~ 2,3 секунды.

Это все детали и является следствием чистоты и лени. В ситуации с мутацией и произвольным доступом, я думаю, что replicateрешение будет строго лучше.

Тем не менее, это поднимает вопрос о том, есть ли способ переписать applicativeTreeтакой, который myFromListявляется строго более эффективным. Проблема, я думаю, в том, что аппликативные действия выполняются не в том порядке, в котором обходится дерево, но я не до конца проработал, как это работает, или есть способ решить эту проблему.

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

Вы можете построить fingertree, используя Data.FingerTree.replicateи их используя FingerTree.fmapWithPosдля поиска ваших значений в массиве, который играет роль вашей конечной последовательности, или используяtraverseWithPos выделения их из списка или другого контейнера известного размера.

Это выделит $O(\log n)$ узлы для исходного реплицированного скелета, а затем заменить их на $O(n)$ узлы, необходимые для заполнения скелета, не более $O(\log n)$ памяти до тех пор, пока сборщик мусора не прояснит ситуацию, поэтому вместо оптимальных ~ 1000 узлов вам придется заплатить за ~ 1010, вместо ~ 2000 от создания минусов.

Наконец, вы можете избежать использования replicate at и создания этого промежуточного $O(\log n)$реплицированное в память дерево, используя replicateA, но, как заметил @sclv, кортеж для управления состоянием, присущимmapAccumL монаде состояния или обхода ее самим, на самом деле будет вводить пропорционально аналогичные издержки, просто платя за все дополнительные ячейки продукта.

TL; DR Если бы мне пришлось это сделать, я бы, вероятно, использовал:

rep :: (Int -> a) -> Int -> Seq a 
rep f n = mapWithIndex (const . f) $ replicate n () 

и индекс в массиве фиксированного размера , я бы просто поставить (arr !)на fвыше.