-=368I1HLZ=-
Осилил extension-кодирование произвольного дерева в бинарное. Запилил по этому поводу гист gist.github.com
Достоинства:
1. Бинарное дерево. А значит, целый арсенал отработаных методов (хранение, сравнение и т.п.).
2. Узлы в исходном и закодированном дереве при обходе слева-направо обходятся в том же порядке.
3. У внутренних узлов всегда два потомка (в отличие от FCNS).
4. Каждому поддереву исходного дерева соответствует поддерево закодированного. В случае FCNS, например, это не так, там поддереву закодированного соответствует хедж исходного.
5. Можно разбирать как снизу-вверх с помощью stepwise automata (аццкая штука, обладающая магическими свойствами), так и сверху-вниз с помощью обычного рекурсивного спуска (ака монадический комбинаторный парсер). В любом случае из за свойства (4) разборщик будет хорошо комбинироваться.
6. Зиппер для бинарного дерева прост и понятен.
Недостатки:
1. Это совершенно неинтуитивно. Первая мысль при взгляде на закодированное дерево — «что за хуйня». Гист пытается немного помочь в освоении.
2. Дерево будет несбалансированным. Совсем. Справдливости ради стоит заметить что в случае FCNS оно ещё более несбалансировано.
3. Увы, но исходное дерево нельзя кодировать сверху-вниз.
4. Более того, кодировать можно только имея уже существующее дерево в другой форме. Например, ХМЛ напрямую закодировать нельзя, в отличие от FCNS.
5. Обходить дерево имеет смысл только слева-направо.
6. Для исходного дерева требуется использовать структуру, поддерживающую эффективную операцию взятия последнего элемента.
ЗЫ: Кому бы в голову это не пришло... Но автора, однозначно, конкретно припёрло.
Достоинства:
1. Бинарное дерево. А значит, целый арсенал отработаных методов (хранение, сравнение и т.п.).
2. Узлы в исходном и закодированном дереве при обходе слева-направо обходятся в том же порядке.
3. У внутренних узлов всегда два потомка (в отличие от FCNS).
4. Каждому поддереву исходного дерева соответствует поддерево закодированного. В случае FCNS, например, это не так, там поддереву закодированного соответствует хедж исходного.
5. Можно разбирать как снизу-вверх с помощью stepwise automata (аццкая штука, обладающая магическими свойствами), так и сверху-вниз с помощью обычного рекурсивного спуска (ака монадический комбинаторный парсер). В любом случае из за свойства (4) разборщик будет хорошо комбинироваться.
6. Зиппер для бинарного дерева прост и понятен.
Недостатки:
1. Это совершенно неинтуитивно. Первая мысль при взгляде на закодированное дерево — «что за хуйня». Гист пытается немного помочь в освоении.
2. Дерево будет несбалансированным. Совсем. Справдливости ради стоит заметить что в случае FCNS оно ещё более несбалансировано.
3. Увы, но исходное дерево нельзя кодировать сверху-вниз.
4. Более того, кодировать можно только имея уже существующее дерево в другой форме. Например, ХМЛ напрямую закодировать нельзя, в отличие от FCNS.
5. Обходить дерево имеет смысл только слева-направо.
6. Для исходного дерева требуется использовать структуру, поддерживающую эффективную операцию взятия последнего элемента.
ЗЫ: Кому бы в голову это не пришло... Но автора, однозначно, конкретно припёрло.
Камрады, а почему все повсеместно используют реализацию хедж-деревьев в виде
data Tree a = Node a | Tree a [Tree a]
Если уж и юзать хедж-деревья, то тогда уж вместо списка юзать finger tree (сиречь Data.Seq). Тут вам и вставка и слева и справа за константное время и разбивка/склейка за логарифмическое... И ещё какие-то плюшки... Странно всё это...
data Tree a = Node a | Tree a [Tree a]
Если уж и юзать хедж-деревья, то тогда уж вместо списка юзать finger tree (сиречь Data.Seq). Тут вам и вставка и слева и справа за константное время и разбивка/склейка за логарифмическое... И ещё какие-то плюшки... Странно всё это...
16da — 9c4
В копилку статеек про деревья homepages.cwi.nl
Жуйк, подскажи! Есть дерево, для определенности полученное из XML, но это не важно. Задача — проверить что нужные узлы и листья присутствуют и находятся по правильным путям, ненужные не присутствуют. Но, как?
Вариант №1 — ползать по дереву аналогом монады State. Кроме того, я легко смогу его линеаризировать, и юзать какой-нибудь парсер. Нафиг, мне такое счастье, я тогда лучше вариант 2 заюзаю.
Вариант №2 — изнасиловать дерево стотыщщпиццот запросами типа XPath. Можно обернуть в какую-нибудь монаду, например в IO (гы-гы-гы). Но, зачем тогда сдался хаскель?
Вариант №3 — зиппер и прочие комонады.
Вариант №4 — F-алгебры и прочие (ко???)алгебраические интерпретаторы.
Так все-таки как, чтобы было с одной стороны по фен-шую, а с другой стороны приносило много фана. Вопросы производительности и расхода памяти интересуют в последнюю очередь.
Вариант №1 — ползать по дереву аналогом монады State. Кроме того, я легко смогу его линеаризировать, и юзать какой-нибудь парсер. Нафиг, мне такое счастье, я тогда лучше вариант 2 заюзаю.
Вариант №2 — изнасиловать дерево стотыщщпиццот запросами типа XPath. Можно обернуть в какую-нибудь монаду, например в IO (гы-гы-гы). Но, зачем тогда сдался хаскель?
Вариант №3 — зиппер и прочие комонады.
Вариант №4 — F-алгебры и прочие (ко???)алгебраические интерпретаторы.
Так все-таки как, чтобы было с одной стороны по фен-шую, а с другой стороны приносило много фана. Вопросы производительности и расхода памяти интересуют в последнюю очередь.
отобразить структуру директории в консоли теперь проще простого благодоря tree =)
Небольшое сравнение производительности выборок из древовидных структур Parent и Nested Sets в Oracle xpoint.ru
мммм... походу накрывается винт на 500 гигов с фильмами
бэкапить сиюсекундно некуда такой объем, поэтому решил сбэкапить то, что 100% нужно, остальное скачать по мере необходимости (по списку).
какую прогу посоветуете для того, чтобы было можно прошерстить диск/папку, чтобы был создан файлик со структурой, в идеале — визуальной, в каком-нибудь xml, если может еще и в виде скришота — тоже очень неплохо :)
бэкапить сиюсекундно некуда такой объем, поэтому решил сбэкапить то, что 100% нужно, остальное скачать по мере необходимости (по списку).
какую прогу посоветуете для того, чтобы было можно прошерстить диск/папку, чтобы был создан файлик со структурой, в идеале — визуальной, в каком-нибудь xml, если может еще и в виде скришота — тоже очень неплохо :)
Утилита tree доставляет, хорошая! И почему я раньше её не встретил?! Красота.
@gansik написал интересный скрипт, как то я пропустил это. в его блоге не нашел об этом, чтобы порекомендовать. По этому выложу у себя. @gansik респект. Сылка на скрипт gansik.tagv.com
