ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / огромное дерево - как хранить?
25 сообщений из 26, страница 1 из 2
  1  все
огромное дерево - как хранить?
    #36295433
vinger4
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
vinger4
Гость
Подскажите ещё пожалуйста такой вопрос: как хранить огромное дерево? в базе данных? или есть специальные структуры для этого (именно для больших деревьев)?
...
Рейтинг: 0 / 0
06.11.2009, 17:06:23
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36295646
*
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
*
Гость
Вопрос задан неточно ИМХО.
В чем собственно задача?
Дерево - средство или цель?
...
Рейтинг: 0 / 0
06.11.2009, 18:11:20
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36295908
vinger4
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
vinger4
Гость
Средство конечно. Для метода ветвей и границ.
...
Рейтинг: 0 / 0
06.11.2009, 22:40:50
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36295948
spywares
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
spywares
Участник
vinger4Средство конечно. Для метода ветвей и границ.

Ветвйе чего? дерева? границ каких? -- государственных? так вроде они и так охраняются
Модератор:
умничают в другом месте
...
Рейтинг: 0 / 0
06.11.2009, 23:22:22
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36295956
vinger4
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
vinger4
Гость
очень смешно...
...
Рейтинг: 0 / 0
06.11.2009, 23:33:21
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36295967
_Йа_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
_Йа_
Гость
Распилить и в сарай.
...
Рейтинг: 0 / 0
06.11.2009, 23:46:44
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36295995
Фотография optimizer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
optimizer
Участник
vinger4,

может быть не стоит хранить все дерево? (я касательно данного метода говорю)
...
Рейтинг: 0 / 0
07.11.2009, 00:24:33
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36296004
vinger4
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
vinger4
Гость
optimizer , скорее всего Вы правы. Однако всё равно придётся хранить самые последние узлы у каждой ветви. Размеры, конечно, будут значительно меньше. Благодарю за подсказку!
...
Рейтинг: 0 / 0
07.11.2009, 00:31:47
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36296118
Фотография optimizer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
optimizer
Участник
я так понял хотите использовать обход в ширину (breadth-first search). Не рассматривали обход в глубину (depth‑first search) (опять касательно МВГ)? В обходе в глубину потребуется стек. Можно воспользоваться готовым стеком - стеком вызовов :)
...
Рейтинг: 0 / 0
07.11.2009, 02:32:31
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36296498
Gatman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gatman
Участник
B+
...
Рейтинг: 0 / 0
07.11.2009, 15:35:40
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36296553
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
> огромное дерево - как хранить?


Точно так же как и крохотное:
в виде массива векторов vector<int> a[50000000] ,
где в векторе a[i] все дети вершины i.
+
int b[50000000], где в b[i] родитель вершины i
...
Рейтинг: 0 / 0
07.11.2009, 16:54:28
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36296635
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
В базах данных обычно деревья хранят так:
idparent_idcomment0nullКорневая вершина10Дочерняя20Дочерняя31Дочерняя 2 уровня
id, и parent_id должны быть проиндексированы.

Такая форма чрезвычайно простая, компактная. У неё один недостаток. Движение от корня к самому дальнему потомку, и выборка всех потомков узла обычно не такое быстрое, как в файловой системе например. Расход памяти не берём в расчёт т.к. для БД это не особо принципиально.

По моему, это называется "инверсный список". Хотя и могу ошибаться в определении.

Если дерево укладывается в оперативную память - то обычно создают структуру "узел" (node), где перечислены все атрибуты узла, со списком указателей на дочерние узлы. У неё почти нет недостатков кроме расхода памяти (особенно если используются 64bit указатели). И нужно быть внимательным при удалении узлов. Т.е. не забывать вызвать деструкторы для всех потомков чтобы не создавать memory leaks.

Еще один интересный вариант реализации узла - вместо списка указателей создают всего два указателя. Указатель "вниз". И указатель "вправо". Получаем дерево, которое концептуально похоже на память Lisp машины. С такми деревом можно делать много интересных алгоритмических штуковин. Хотя среднее количество узлов будет чуть больше чем в предыдущем варианте.
...
Рейтинг: 0 / 0
07.11.2009, 19:19:05
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36297253
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
vinger4Подскажите ещё пожалуйста такой вопрос: как хранить огромное дерево? в базе данных? или есть специальные структуры для этого (именно для больших деревьев)?Хранить в базе данных, одна из функций БД именно хранение. Потом если очень надо, можно во время работы копировать в структуру которая вся в памяти. А каков размер огромного дерева?
...
Рейтинг: 0 / 0
08.11.2009, 15:19:02
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36297746
DPH3
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DPH3
Участник
А для чего хранить? Что с ним потом делать?
Какой объем данных, какие операции, какие требования к производительности и скорости отклика?
...
Рейтинг: 0 / 0
09.11.2009, 01:24:43
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36302267
Фотография VladConn
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VladConn
Участник
Вообще-то разве XML файлы не приспособлены для хранения деревьев?
...
Рейтинг: 0 / 0
10.11.2009, 19:46:42
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36304670
Серж
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Серж
Участник
VladConnXML файлы
и
vinger4огромное дерево

вещи несовместимые.
...
Рейтинг: 0 / 0
11.11.2009, 17:40:35
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36305146
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Сержвещи несовместимые.
Хранить можно. Но работать с XML-файлом в режиме online-транзакций не представляется возможным. Практически все имплементации XMLDocument пересоздают документ заново при корректировке всего-лишь одного атрибута. Вывод - XML-технология - это НЕ АЛЬТЕРНАТИВА БД. Это просто формат ХРАНЕНИЯ данных.
...
Рейтинг: 0 / 0
11.11.2009, 20:27:54
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36331214
Ahilles
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Ahilles
Гость
MUMPS (например cache', MSM, MiniM) специально предназначены для хранения деревьев.
...
Рейтинг: 0 / 0
25.11.2009, 15:44:36
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36331313
vinger4
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
vinger4
Гость
AhillesMUMPS (например cache', MSM, MiniM) специально предназначены для хранения деревьев.

Благодарю за подсказку! Будем смотреть!
...
Рейтинг: 0 / 0
25.11.2009, 16:09:24
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36331684
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
vinger4AhillesMUMPS (например cache', MSM, MiniM) специально предназначены для хранения деревьев.
Благодарю за подсказку! Будем смотреть!
Смотри, сильно не углубляйся. Это целая отрасль. Кст. было несколько интересных обсуждений здесь на тему MUMPS.
...
Рейтинг: 0 / 0
25.11.2009, 17:33:51
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36333087
ntr123
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ntr123
Гость
Посмотри в сторону HierarchyID (mssql2008)

http://msdn.microsoft.com/en-us/library/bb677290.aspx
...
Рейтинг: 0 / 0
26.11.2009, 12:00:23
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36336739
Фотография nu89
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nu89
Участник
А на каком языке надо написать процедуру сохранения? (-;

Для C++ мы сделали так:

1. Открыть файл для записи.
2. Отступить 4 байта - сюда запишем кол-во блоков в файле.
3. Выделяем буффер, мегабайт на 10 - это будет один блок данных.
4. Отступаем 4 байта - сюда запишем кол-во записей (узлов дерева) в этом блоке.
5. Начинаем перебирать все узлы дерева, откладывать в буффер в виде последовательности байт в нашем формате каком-то.
6. Как буффер забился - скинуть счётчик лёгших в этот буффер записей в начало буффера (смещение 0), скинуть весь буффер в файл одним вызовом write. Это будет блок. Увеличить число скинутых блоков.
7. Как только кончились все узлы в дереве, скинуть последний недоделанный блок по всем правилам и в начало файла записать 4 байта = кол-во скинутых в файл блоков.
...
Рейтинг: 0 / 0
28.11.2009, 00:46:31
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36337019
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
nu89....
7. Как только кончились все узлы в дереве, скинуть последний недоделанный блок по всем правилам и в начало файла записать 4 байта = кол-во скинутых в файл блоков.
Ну и зачем такая конкретика? Лучше объясните топик-стартеру в чём будет преимущество вашего способа по сравнению с XML. А-то очевидно только усложнение...
...
Рейтинг: 0 / 0
28.11.2009, 16:31:57
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36337370
Фотография nu89
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nu89
Участник
Ну преймущество в скорости только)
Нам нужно было периодически скидывать всё это дерево в файл (резервирование). Раз в 10 минут. Кол-во узлов в дереве было - от 1 до 200 млн, хранились только числа и счётчики всякие, занимало до 32 гигов RAM...
...
Рейтинг: 0 / 0
29.11.2009, 08:08:46
| Ответить | Цитировать | Написать  
огромное дерево - как хранить?
    #36337744
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
И вы поступили так-же как и печально известный создатель драйвера TJ7 ? Написали своё ПО для хранения и бэкапирования дерева?
...
Рейтинг: 0 / 0
29.11.2009, 18:08:47
| Ответить | Цитировать | Написать  
25 сообщений из 26, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / огромное дерево - как хранить?
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&fpage=113&tid=1344066]:
 0ms
get settings:
 5ms
get forum list:
 8ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 60ms
get topic data:
 8ms
get forum data:
 3ms
get page messages:
 33ms
get tp. blocked users:
 2ms
others: 186ms
total:  309ms
созд. / загр.: 309ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]