информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Портрет посетителяАтака на InternetЗа кого нас держат?
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / beginners
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Господа, будьте снисходительны, не бросайтесь сразу штрафовать за, как вам кажется, глупые вопросы - beginners на то и beginners.
Хорошо, более наглядный пример такой организации дерева в файле 19.09.03 14:17  Число просмотров: 1266
Автор: amirul <Serge> Статус: The Elderman
Отредактировано 19.09.03 14:18  Количество правок: 1
<"чистая" ссылка>
Экспортированный файл реестра (хотя не совсем такой же, потому как там нет длины для быстрого пропуска ветки)

Хотя можно добавить возможность прохода по дереву и к приведенному whiletrue метода, если использовать в качестве ID ноды использовать смещение в файле, а для каждой ноды, имеющей детей сохранять офсеты всех детей (или офсет на список детей - кому как нравится), тогда и восстанавливать дерево будет легче. Насколько я помню, реестр физически хранится именно так (да и файловые системы тоже примерно так).

ЗЫ: Вот сейчас подумал, второй вариант мне нравится больше - легче добавлять удалять детей без перетаскивания больших кусков файла.
<beginners>
как сохраняют дерево на диске ? 19.09.03 11:24  
Автор: tdes <jin> Статус: Member
<"чистая" ссылка>
Предположим у меня есть (в памяти ) дерево ( в примитивном случае бинарное), полученное в результате работы некого алгоритма. Я хочу сохранить это дерево в файл, чтоб следующий раз не строить его, а просто загрузить в память с диска. Вопрос, как это сделать, при условии что “глубина” дерева не известна ?
10x
А что, XML плохо подходит? 19.09.03 15:09  
Автор: Ktirf <Æ Rusakov> Статус: Elderman
<"чистая" ссылка>
можно подробнее про связь с XML ? 19.09.03 19:54  
Автор: tdes <jin> Статус: Member
<"чистая" ссылка>
Даже не знаю. 19.09.03 20:06  
Автор: Ktirf <Æ Rusakov> Статус: Elderman
Отредактировано 19.09.03 20:08  Количество правок: 1
<"чистая" ссылка>
Что тут подробнее-то :) Алгоритм сохранения - как whiletrue описал. Конкретную форму выбираешь сам, можно, например, такой:
<node id="456">
  <node id="789">
    <![CDATA[здесь идут данные ребенка]]>
  </node>
  <![CDATA[здесь идут данные]]>
</node>

---

Когда нужно восстановить дерево, берешь первый попавшийся под руку XML-парсер, навешиваешь на него свои обработчики (их у тебя будет ровно два, если я не ошибаюсь) и разбираешь этот XML.
но если учесть что в ХМЛ 19.09.03 20:15  
Автор: tdes <jin> Статус: Member
<"чистая" ссылка>
не могут быть вложены однотипные ноды, то есть некоторые проблемы.
и, imho, лучше уже использовать SQL, так как не надо будет заботится о порядке сохранения нодов
Почему это в XML не могут быть сохранены однотипные ноды??? 19.09.03 20:39  
Автор: Ktirf <Æ Rusakov> Статус: Elderman
Отредактировано 19.09.03 20:41  Количество правок: 1
<"чистая" ссылка>
<root>
  <node id="1">
    <![CDATA[Вот один]]>
  </node>
  <node id="2">
    <![CDATA[Вот второй]]>
    <node id="3">
      <![CDATA[Или я чего-то не понимаю?]]>
    </node>
  </node>
</root>

---
А нужный порядок сохранения нетрудно обеспечить обходом вглубь.
да, погорячился я )) 20.09.03 10:29  
Автор: tdes <jin> Статус: Member
<"чистая" ссылка>
как сохраняют дерево на диске ? 19.09.03 11:28  
Автор: whiletrue <Роман> Статус: Elderman
<"чистая" ссылка>
> Предположим у меня есть (в памяти ) дерево ( в примитивном
> случае бинарное), полученное в результате работы некого
> алгоритма. Я хочу сохранить это дерево в файл, чтоб
> следующий раз не строить его, а просто загрузить в память с
> диска. Вопрос, как это сделать, при условии что “глубина”
> дерева не известна ?
> 10x

Пробегаешь рекурсией по дереву и сохраняешь следущее:
ID | Сами данные | ID_Родителя

При восстановлении:
Пробегаешь по этому списку. Смотришь на ID_Родителя - туда и пихаешь.
И еще 19.09.03 13:06  
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
> Пробегаешь рекурсией по дереву и сохраняешь следущее:
> ID | Сами данные | ID_Родителя
>
> При восстановлении:
> Пробегаешь по этому списку. Смотришь на ID_Родителя - туда
> и пихаешь.

Для удобства навигации чаще всего его организовывают в виде chunk-ов, в которых содержится вся ветка (вместе со всеми потомками) и длина.

Можешь посмотреть документацию по мультимедийным форматам RIFF и IFF. Причем последний используется для хранения чуть ли не любых документов (рисунки, музыка, 3d-сцены, документы текстового процессора и т.п.) на платформе Amiga. А RIFF в свою очередь в видне используется для wav и avi файлов.

Так вот в простейшем случае разбитый на chunk-и файл выглядит так:

{chunk_id_1, chunk_len_1, { {chunk_id_2, chunk_len_2, {data2}} {chunk_id_3, chunk_len_3, {data3}} } data1}

Длина данных в листьях может быть нулевой, если важно само его наличие. Причем длина показывает длину ВСЕГО чанка вместе с потомками. Поле ID используется например для различия между разными нодами (например, ветвится ли дальше или является листом).

Для того, чтобы понять, как ЭТО сохранить на диск (самое интересное это как сохранить длины) рекомендую посмотреть интерфейс для работы с RIFF-файлами (mmioXxx - функции). Но вкратце это выглядит как работа с файловой системой: зашел в каталог (chunk), создал подкаталог, вошел в него, создал еще чего то... И т.д. А длина записываются при выходе из каталога (chunk-а).

Такая организация дает преимущество в том, что возможно свободное хождение по дереву и поиск нужной ветки без считывания всего дерева в память.
Тяжеловаты они (форматы эти), имхо... 19.09.03 13:53  
Автор: HandleX <Александр М.> Статус: The Elderman
<"чистая" ссылка>
Хорошо, более наглядный пример такой организации дерева в файле 19.09.03 14:17  
Автор: amirul <Serge> Статус: The Elderman
Отредактировано 19.09.03 14:18  Количество правок: 1
<"чистая" ссылка>
Экспортированный файл реестра (хотя не совсем такой же, потому как там нет длины для быстрого пропуска ветки)

Хотя можно добавить возможность прохода по дереву и к приведенному whiletrue метода, если использовать в качестве ID ноды использовать смещение в файле, а для каждой ноды, имеющей детей сохранять офсеты всех детей (или офсет на список детей - кому как нравится), тогда и восстанавливать дерево будет легче. Насколько я помню, реестр физически хранится именно так (да и файловые системы тоже примерно так).

ЗЫ: Вот сейчас подумал, второй вариант мне нравится больше - легче добавлять удалять детей без перетаскивания больших кусков файла.
угу, логично, наверное надо бросать пить ))) 19.09.03 11:40  
Автор: tdes <jin> Статус: Member
<"чистая" ссылка>
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 1 s   Design: Vadim Derkach