OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Четверг, 19 Октябрь, 2017 02:45

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 7 ] 
Автор Сообщение
 Заголовок сообщения: Персистентное дерево
СообщениеДобавлено: Понедельник, 02 Октябрь, 2017 17:10 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 584
Откуда: Казань
В докладе на Оберон День 2017 я рассказывал про библиотеку контейнеров
Вложение:
AntiAdHocPresentation.zip [229.91 КБ]
Скачиваний: 17
.
И про то, что можно на её основе сделать персистентные контейнеры, то есть контейнеры, которые запоминают каждую свою модификацию и при желании можно вернуться к предыдущей версии и посмотреть что там было.
В итоге реализовал такое дерево. Для того, чтобы лучше понимать, что именно оно делает, вот тест:
Код:
Inserted 5
Inserted 4
Inserted 6
Inserted 1
Inserted 2
Removed 4
Inserted 9
Inserted 4
Removed 4
Inserted 8
Removed 8
Inserted 3
Inserted 0
Inserted 4
Removed 0
Removed 6
Inserted 7
Inserted 0
Inserted 8
Removed 2
Removed 0
Version 0:
Version 1: 5
Version 2: 4 5
Version 3: 4 5 6
Version 4: 1 4 5 6
Version 5: 1 2 4 5 6
Version 6: 1 2 5 6
Version 7: 1 2 5 6 9
Version 8: 1 2 4 5 6 9
Version 9: 1 2 5 6 9
Version 10: 1 2 5 6 8 9
Version 11: 1 2 5 6 9
Version 12: 1 2 3 5 6 9
Version 13: 0 1 2 3 5 6 9
Version 14: 0 1 2 3 4 5 6 9
Version 15: 1 2 3 4 5 6 9
Version 16: 1 2 3 4 5 9
Version 17: 1 2 3 4 5 7 9
Version 18: 0 1 2 3 4 5 7 9
Version 19: 0 1 2 3 4 5 7 8 9
Version 20: 0 1 3 4 5 7 8 9
Version 21: 1 3 4 5 7 8 9

Единственное, остался один неясный момент. При добавлении в обычное дерево, я сначала вызываю функцию Allocate и только затем Insert, то есть Insert не может провалиться из-за нехватки памяти. Сейчас же при модификации основного дерева, для запоминания предыдущего состояния, выделяется память для хранения новой модификации указателя (по сути вместо обычного указателя в памяти, я реализовал дерево указателей, у которых ключ - это номер версии). И на каком-то этапе может так произойти, что не хватит памяти для сохранения этой истории. И из-за этого основной алгоритм тоже может провалиться. По идее надо бы расчитать точно, сколько вращений может быть в AVL дереве в худшем случае при удалении или добавлении и сколько при этом указателей может измениться. А затем до попытки добавления в дерево или удаления из него необходимо разом выделить максимальное количество памяти под указатели, которые могут измениться, чтобы алгоритм ни при каких обстоятельствах не столкнулся с нехваткой памяти.
Как вам данный подход? Может быть у вас есть идеи по лучше?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Персистентное дерево
СообщениеДобавлено: Вторник, 03 Октябрь, 2017 09:19 

Зарегистрирован: Вторник, 01 Март, 2011 09:34
Сообщения: 116
Откуда: Москва
Вы в докладе говорили, что рассматривали и деревья в виде массивов (видимо, однородных структур). Такие структуры можно восстанавливать из персистентных файлов за одно аллокирование. Дерево-массив -> Externalize -> Передача по сети -> Internalize (за 1 NEW) -> дерево-массив.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Персистентное дерево
СообщениеДобавлено: Вторник, 03 Октябрь, 2017 17:43 

Зарегистрирован: Понедельник, 25 Июнь, 2012 17:26
Сообщения: 169
Rifat писал(а):
И про то, что можно на её основе сделать персистентные контейнеры, то есть контейнеры, которые запоминают каждую свою модификацию и при желании можно вернуться к предыдущей версии и посмотреть что там было.
...
Единственное, остался один неясный момент.
...
И на каком-то этапе может так произойти, что не хватит памяти для сохранения этой истории

А зачем нужна эта история? Если предполагается нечто вроде мини-СУБД, то обычно в подобных случаях функционал шире со спецификой предметки (к примеру, версии нужны в контексте транзакций, журналов операций, существует возможность сброса/загрузки на диск и т.д.). Но исходя из презентации речь, вроде как, об универсальных контейнерах и алгоритмах, аля STL. Однако типовая сфера применения "персистентных" универсальных контейнеров -- immutable-коллекции как в функциональных языках, или по их мотивам -- на примере facebook-фреймворка для JavaScript:
http://facebook.github.io/immutable-js/

, где версии, как таковы, используются для внутренней реализации "виртуального копирования" структур, в стиле:
A = [1,2,3,4,5,6];
B = A;
B[1] = 12234;

Здесь при присваивании "B = A" не выполняется копирования контейнера (массива), лишь используется указатель. При изменении данных вида "B[1] = 12234" создаются "версии" только необходимых элементов, части исходной структуры. В последующем "история" освобождается при уничтожении объектов (т.е. при выходе из области определения переменных и т.п.). В дополнение, практика обычно требует и транзитных преобразований, т.е. "по месту", временный перевод структур из immutable в mutable (плюс "ленивые" вычисления по вкусу, как тип Seq по ссылке выше -- для избегания по возможности создания промежуточных структур при различных вычислениях).
Для таких техник необходимы:
- реализация политики каких-то smart-pointer, для разруливания владения, освобождения и т.д.;
- предположение, что в виртуальных копиях обычно выполняется лишь частичная модификация данных (т.е. не передел всего и вся, иначе нет никакой эффективности).

Такова типовая необходимость в "версиях" в стандартных контейнерах, и нет концептуальных непоняток с их "накоплением".
Однако, в дополнение возникает сомнение, зачем подобные техники и "STL" в целом в языке, который целенаправленно не приспособлен к обобщённым алгоритмам. И Ваша презентация тому кричащий пример, как и некоторые темы здесь на форуме. Согласно презентации, необходимость реализации "типов-ключей" и соответствующих операций вида "AssignAddrToAddr", "CompareKeyAddr" и т.д., фактически, для каждого случая применения, а особенно при использовании стандартных же базовых типов -- чисел, строк и т.д., в том числе и как составных данных, со стандартными же операциями -- мягко говоря, не юзабельно.

Вот здесь был пример реализации "STL" для Pascal при отсутствии generic-ов:
viewtopic.php?f=26&t=2036&start=100#p101400

, где, в некотором смысле, имеется схожий подход в архитектуре. Не в курсе, насколько подобные выкрутасы целесообразны в Оберонах (не использую, имею лишь поверхностные знания), но взглянуть есть смысл. Там также применялись "типы-ключи", но по-иному -- как "типы-поля" для структур данных, в которых "перехватываются" ключевые операции от контейнеров (был интерфейс и для деревьев).
Правда, для удобства в том же Pascal-е были (и есть) некоторые базовые языковые конструкции. К примеру, определение операций "индексации" для произвольных "свойств" в структурах аля:
n.Map[3.14] := 'Pi'

Или применение встроенных типов вида "variant" или "TVarRec" (или как там тип-запись назывался для аргументов функций, определяемых как "array of const") для передачи "открытых" массивов как variadic-параметров.
Не знаю, как подобные удобняшки стандартно реализуются в Обероне, но есть подозрение, что окольными путями (вряд ли тогда в них есть смысл).

P.S. Документация от проекта AntiDot:
Вложение:
Guide.pdf [143.87 КБ]
Скачиваний: 9


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Персистентное дерево
СообщениеДобавлено: Четверг, 05 Октябрь, 2017 16:46 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 584
Откуда: Казань
Дмитрий Дагаев писал(а):
Вы в докладе говорили, что рассматривали и деревья в виде массивов (видимо, однородных структур). Такие структуры можно восстанавливать из персистентных файлов за одно аллокирование. Дерево-массив -> Externalize -> Передача по сети -> Internalize (за 1 NEW) -> дерево-массив.

Слово персистентный имеет несколько значений. Иногда, да говорят о данных, которые переживают время запуска программы, то есть выгружаются и загружаются из какой-то формы (сериализация).
В википедии по поводу персистентных структур данных немного другое определение:
https://en.wikipedia.org/wiki/Persistent_data_structure
Цитата:
In computing, a persistent data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure.

Я придерживаюсь этого определения.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Персистентное дерево
СообщениеДобавлено: Четверг, 05 Октябрь, 2017 16:51 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 584
Откуда: Казань
PSV100 писал(а):
А зачем нужна эта история? Если предполагается нечто вроде мини-СУБД, то обычно в подобных случаях функционал шире со спецификой предметки (к примеру, версии нужны в контексте транзакций, журналов операций, существует возможность сброса/загрузки на диск и т.д.).

Персистентные структуры данных можно использовать, например, для текстового редактора с поддержкой undo. Можно редактировать текст и откатываться к предыдущим версиям при необходимости.

Или же можно использовать, для запоминания, каких-нибудь преобразований.
Допустим, есть предикат:
0) х + х + х = 3*x
1) 3*x = 3*x
2) TRUE
Будет возможность видеть всю цепочку преобразований, а не только конечный результат TRUE.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Персистентное дерево
СообщениеДобавлено: Пятница, 06 Октябрь, 2017 14:40 
Аватара пользователя

Зарегистрирован: Воскресенье, 12 Апрель, 2015 18:12
Сообщения: 1043
Откуда: СССР v2.0 rc 1
Когда начинается втягивание новых терминов с непонятной на слух семантикой, лично я всегда напрягаюсь.
Персистентность -- способность сохранять правильную структуру и значения в ходе каких-либо процессов из которых базовых три: хранение, передача, обработка.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Персистентное дерево
СообщениеДобавлено: Пятница, 06 Октябрь, 2017 20:14 

Зарегистрирован: Понедельник, 25 Июнь, 2012 17:26
Сообщения: 169
Rifat писал(а):
Персистентные структуры данных можно использовать, например, для текстового редактора с поддержкой undo. Можно редактировать текст и откатываться к предыдущим версиям при необходимости.

В статейке ниже пара слов насчёт undo:
Вложение:

Я всего лишь хочу сказать, что подобные задачи, как правило, гораздо шире, чем версии данных в стандартном контейнере (кстати, в данном случае immutable-коллекции могут оказаться полезными -- множество "клиентов" к одной структуре данных, а у каждого клиента свой поднабор, может даже со своим аля multi_index из C++ Boost).
В общем, контейнеры всякие разные нужны.

Но проблема в таком языке как Оберон -- как строить универсальный интерфейс аля STL, даже для Ваших деревьев (генерировать требуемые реализации операций, к примеру). Здесь могу предложить варианты:
- макросы в стиле С, например как:
https://gcc.gnu.org/viewcvs/gcc/trunk/g ... rev=165314
, что вряд ли приемлемо общественностью;

- велосипед-кодогенератор. У каждого свой, или какой-то универсальный, к примеру:
https://nedbatchelder.com/code/cog/

- макросы как в Rust -- ограниченные, в виде функций:
https://doc.rust-lang.org/1.7.0/book/macros.html

- макросы как в Scala, прежде всего -- квазицитаты в виде спецстрок q"..." (по мотивам Лиспа):
http://docs.scala-lang.org/overviews/qu ... intro.html

Мне кажется, что практично -- макросы как Rust-функции вида "search!(cont, [val1, val2])", но с реализацией на квазицитатах. Однако, впечатление, что "meta-фишки" не приветствуются в Оберон-сообществе (но я могу ошибаться). Но я воспользуюсь след. предложением технологии:
Zero-Overhead Exeption Handling Using Metaprogramming

Т.е. runtime-метатехнологии предлагаются. Причём в подобных техниках нет compiletime деклараций, в том смысле, что, к примеру, какие-то процедуры являются обработчиками ошибок -- лишь какое-то "устное соглашение", мол если надо, то реализуй такие-то процедуры, с такими-то параметрами, с такими-то именами и т.п.
Когда те же макросы-функции могут явно, целенаправленно (с контролем типов, безопасности вводимых имён и пр.) хоть тип, к примеру, удобно задавать, со всеми "мета-атрибутами" (аля "make_mytype!(type_name, [<матрица_данных>])" в секции интерфейса модуля).

В общем, я не критикую язык, но уж как-то неоднозначно воспринимается декларируемая надёжность.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2017, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB