Описание тега finger-tree
A finger tree is a purely functional tree data structure that gives amortized constant time access to "finger" (leaves) of the tree. Primarily used in efficiently implementing other functional data structures.
1
ответ
Асимптотические среды выполнения InsertionSort и FingerTreeSort
Я искал в своей книге все выше и ниже, а также несколько сайтов в Интернете, но я не совсем уверен в своих ответах. Мне нужно дать асимптотическое время выполнения InsertionSort и FingerTreeSort (на основе RB-деревьев) в отношении количества имеющих…
21 май '12 в 21:50
2
ответа
Насколько быстро Data.Sequence.Seq по сравнению с []?
Очевидно Seq асимптотически выполняет то же или лучше, чем [] для всех возможных операций. Но поскольку его структура более сложна, чем списки, для небольших размеров его постоянные издержки, вероятно, сделают его медленнее. Я хотел бы знать, скольк…
10 фев '13 в 14:12
2
ответа
Есть ли простой способ реализовать очередь с быстрым приоритетом в Haskell?
Я немного погуглил и нашел статью о Finger Trees, которую можно использовать для реализации очереди приоритетов с надлежащей асимптотической сложностью, но они довольно сложные, но все же о самой простой вещи, которую я смог найти. Существует ли про…
25 ноя '14 в 21:08
3
ответа
Почему FingerTrees не используются достаточно для стабильной реализации?
Некоторое время назад я наткнулся на статью о FingerTrees (см. Также сопровождающий вопрос о переполнении стека) и отослал эту идею. Я наконец нашел причину использовать их. Моя проблема в том, что пакет Data.FingerTree, кажется, немного гниет по кр…
22 июн '12 в 07:16
1
ответ
Для чего мне использовать пальчиковые деревья Clojure?
В новой группе библиотек Contribute в Clojure есть библиотека дерева пальцев. Каковы случаи использования пальчиков в clojure? Когда следует использовать деревья пальцев вместо одной из других постоянных структур данных clojure: векторов, множеств, …
19 окт '10 в 21:30
1
ответ
Haskell: Где я могу найти другие операции на бумаге из пальца?
Документ "Дерево пальца": http://www.soi.city.ac.uk/~ross/papers/FingerTree.html является основой для библиотеки Data.Sequence: https://www.haskell.org/ghc/docs/7.6.1/html/libraries/containers-0.5.0.0/Data-Sequence.html Но библиотека, кажется, предо…
15 май '14 в 18:53
1
ответ
Clojure пальмовые деревья и flexvec
Я ищу постоянную последовательную структуру данных, которая позволяет эффективные случайные вставки и удаления. Я нашел следующие реализации: https://github.com/clojure/data.finger-tree (реализация со счетным двойным списком) wgjo.data.cljs flexvec …
21 мар '13 в 17:53
1
ответ
Q: Оптимизированная структура данных для разветвленных и версионных объектов
Для данной сущности (скажем, файла или библиотеки / пакета), которая может со временем развивать свои версии и ветви, ища оптимизированную структуру данных, которая позволяет мне переходить от версий к конкретному экземпляру сущности. Например (немн…
26 мар '16 в 21:33
1
ответ
Ошибка типа при реализации пальчиковых деревьев
Я хотел поиграть с 2-3 пальцами, как описано в статье (Haskell) Хинце (см. Также этот блог). type Node<'a> = | Node2 of 'a * 'a | Node3 of 'a * 'a * 'a static member OfList = function | [a; b] -> Node2(a, b) | [a; b; c] -> Node3(a, b, c)…
04 окт '16 в 13:55
2
ответа
Нахождение недостающего класса типов "Уменьшить" из статьи "Дерево пальца"
Вчерашний Wikibender, который начался с этого стекового потока на Comonads, закончился в статье MarkCC о Finger Trees. В статье он широко использует Reduce тип класс. Он пишет об этом классе типов, как если бы он был очень распространенной и часто и…
09 дек '11 в 19:08
1
ответ
Приоритетная очередь с O(1) delete-max, insert-min, find-min и O(log n) для вставки и удаления
Возможно ли, чтобы очередь с монотонным приоритетом имела: O (1) для поиска и удаления элемента с наивысшим приоритетом, O (1) для вставки элемента при условии, что данный приоритет ниже, чем у любого другого элемента, O (log n) для вставки и удален…
12 мар '16 в 16:13
2
ответа
Data.Sequence.Seq ленивый параллельный экземпляр Functor
Мне нужна параллельная (но ленивая) версия fmap за Seq от Data.Sequence пакет. Но пакет не экспортирует Seq конструкторы данных. Так что я не могу просто обернуть это newtype и реализовать Functor непосредственно для newtype, Могу ли я сделать это б…
24 сен '15 в 07:07
1
ответ
Строковые представления: улучшения по сравнению с веревками?
Я хочу представление для строк с быстрой конкатенацией и операциями редактирования. Я читал статью "Веревки: альтернатива струнам", но были ли какие-либо существенные улучшения в этой области с 1995 года? РЕДАКТИРОВАТЬ: Одна возможность, которую я р…
14 июн '10 в 18:25
3
ответа
Есть ли реализация бинарного дерева поиска, аннотированного размером поддерева
Я исследовал древовидную структуру данных, описанную по этой ссылке (внизу): http://sigpipe.macromates.com/2009/08/13/maintaining-a-layout/ Упоминается, что эта структура данных может быть пальцем. Тем не менее, после дополнительных исследований вок…
01 май '11 в 15:10
1
ответ
Сложность головы пальцем
Я только что прочитал превосходное введение Апфельма в Finger Trees во второй раз и начал задумываться о его реализации головы: import Prelude hiding (head) data Tree v a = Leaf v a | Branch v (Tree v a) (Tree v a) toList :: Tree v a -> [a] toLis…
09 май '19 в 14:00
0
ответов
Как можно оптимально реализовать (<*) для последовательностей?
В Applicative пример для Data.Sequenceв целом работает очень хорошо. Почти все методы являются асимптотически оптимальными по времени и пространству. То есть, учитывая полностью принудительные / реализованные входы, можно получить доступ к любой час…
10 мар '20 в 19:30