Структура бинарного дерева
Пользователи, просматривающие топик: none
|
Зашли как: Guest
|
Имя  |
| Сообщение |
<< Старые топики Новые топики >> |
|
|
Структура бинарного дерева - 2008-09-20 08:56:21.496666
|
|
|
AchtungPartizanen
Сообщений: 38
Оценки: 0
Присоединился: 2007-10-25 20:54:58.030000
|
Короче, дана курсовая по структурам и алгоритмам. Тема следующая: сборник кулинарных рецептов. То бишь есть какая-то база рецептов, нужно динамически создать структуру бинарного дерева и заполнить ее данными из базы.
Надо: поиск по ингредиентам (допустим, каждый рецепт разделяется на состав и собственно приготовление). Плюс все рецепты должны быть разбиты по смысловым группам (супы отдельно, компоты отдельно). Ну и желательно бы еще прямой алфавитный поиск по названию.
Вопрос прост: какую структуру лучше всего использовать? Понятно, что бинарное дерево, но деревья тоже разные бывают.
PS. Язык - планируется ++ (хотя еще можно передумать и делать на шарпее или делфе)
|
|
|
|
|
RE: Структура бинарного дерева - 2008-09-20 15:04:22.776666
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
Так, во-первых, бинарные деревья разными не бывают. Разве что только по составу узлов, но это уже от тебя зависит, что будет включать каждый узел. А так всегда один предок, два потомка (кроме корня и листьев, конечно же). Но как использовать такое бинарное дерево в твоей задаче, ума не приложу. Максимум, что приходит в голову, это сделать просто дерево (то есть не с двумя, а с большим количеством потомков у каждого узла) с мутабельными узлами, в которых ты сам указываешь, является этот узел рецептом, ингридиентом, или всей кулинарной книгой. А для ускорения поиска прошить граф узлов несколько раз, чтобы получилось несколько деревьев с несколькими корнями, но с общими узлами. Но, честно говоря, страдать таким извращением для организации работы с БД - это очень изощрённый способ заколупать себе мозги:)
Насчёт языка, конечно, твоё дело, но мне кажется плюсы с их адресной арифметикой и небезопасными указателями - это не лучший вариант для такой задачи. Я бы скорее писал для шарпе - там и защита памяти хорошая, и сборщик мусора, и много готовых классов. Но, ещё раз повторюсь, это зависит от уровня знания языка, в первую очередь.
|
|
|
|
|
RE: Структура бинарного дерева - 2008-09-20 15:51:19.060000
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
А что мешает тупо заюзать несколько индектисоранных таблиц? Ручками там не сложно писать, ели не критично быстродействие ))
|
|
|
|
|
RE: Структура бинарного дерева - 2008-09-20 20:22:46.320000
|
|
|
AchtungPartizanen
Сообщений: 38
Оценки: 0
Присоединился: 2007-10-25 20:54:58.030000
|
quote:
ORIGINAL: _SaZ_
А что мешает тупо заюзать несколько индектисоранных таблиц? Ручками там не сложно писать, ели не критично быстродействие ))
Вот быстродействие как раз и мешает
|
|
|
|
|
RE: Структура бинарного дерева - 2008-09-20 20:25:34.023333
|
|
|
AchtungPartizanen
Сообщений: 38
Оценки: 0
Присоединился: 2007-10-25 20:54:58.030000
|
quote:
ORIGINAL: kreol
Так, во-первых, бинарные деревья разными не бывают.
АВЛ, суффиксное, красно-черное, Фибоначчи… ?
Структур как раз много. Вопрос в том, что нужно здесь
|
|
|
|
|
RE: Структура бинарного дерева - 2008-09-21 05:14:13.650000
|
|
|
keys
Сообщений: 137
Оценки: 0
Присоединился: 2008-08-06 08:48:50.340000
|
я бы попробовал сложить рецепты по алфавиту в дерево
при создании узла он отмечается в списке ингридиентов (в каждый ингридиент добавляет ссылку на себя)
и ещё список групп (супы компоты) то же самое делает
списки втыкаются в корень
минусы:
при поиске супов получатся индексы всех супов в порядке добавления (а не по алфавиту)
при поиске морковки и капусты будут выводится дубликаты
|
|
|
|
|
RE: Структура бинарного дерева - 2008-09-21 06:10:21.410000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: AchtungPartizanen
АВЛ, суффиксное, красно-черное, Фибоначчи… ?
Структур как раз много. Вопрос в том, что нужно здесь
То, что ты назвал, это в первую очередь алгоритмы работы с деревом, а не новые структуры, даже дополнительные поля в узлах служат только для ускорения алгоритма. Бинарное дерево от этого бинарным деревом быть не перестаёт. У тебя же граф должен быть сделан хитрее, чем обычное бинарное дерево (КЧ, АВЛ и т.п. деревья в том числе). Как я и сказал, если хочешь сделать быстрый поиск - прошивай своё дерево в нескольких направлениях. Активно используй списки, например, при добавлении нового блюда вставляй ссылку на него в список блюд каждого ингридиента. Тогда ты сможешь очень быстро вытянуть все блюда по индгридиенту, но расход памяти будет колосальным (как вариант, можешь использовать динамические массивы, но тогда будет потеря скорости при добавлении).
Для групп тупо делаешь двойной список: список самих групп, в каждом элементе которого есть ссылка на список блюд, которые входят в группу.
Для поиска по названию блюда я бы использовал хеш-таблицы.
|
|
|
|
|
RE: Структура бинарного дерева - 2008-10-10 15:53:06.403333
|
|
|
AchtungPartizanen
Сообщений: 38
Оценки: 0
Присоединился: 2007-10-25 20:54:58.030000
|
В общем, принял идею с отдельными списками по каждому ингредиенту (ну т.е. список содержит указатели на все рецепты, где есть этот ингредиент). Преподше озвучил, оно одобрила.
Теперь дальше. Как это все сделать? Есть мысль организовать это не списками, а множествами - множества уже изначально не надо упорядочивать, и гораздо проще находить их пересечение и объединение. Может, так лучше, чем просто список?
Ну и основная база - преподша хочет, чтобы была возможность просмотра всех блюд в отдельных категориях (типа супы, салаты и т.д.) - лично я предложил просто создать общий алфавитный список, на который пользователь может накладывать фильтры (как в энциклопедии КМ). Ну тут самый главный вопрос - опять же, что за структуру использовать? Первым на ум приходит простое бинарное дерево (с обычным упорядоченным бинарным поиском)
И посоветуйте: в какой среде лучше реальзовывать?
|
|
|
|
|
RE: Структура бинарного дерева - 2008-10-10 19:06:36.480000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
Ну, во-первых, о каких множествах ты говоришь? Из всех языковых средств на ум приходят только паскалевский "set of", но как бы такие множества могут содержать только целые числа.
А во-вторых, если нужен просмотр по категориям, то что мешает создать ещё один список для категорий? А если тебе нужен фильтр, то я вообще слабо представляю, как ты будешь использовать бинарное дерево. Тебе нужно пробегаться по списку и отображать те его элементы, которые проходят фильтр, а не искать конкретную запись.
|
|
|
|
|
RE: Структура бинарного дерева - 2008-10-11 03:48:16.590000
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
Ну с твоими запросами… Как раз таки у индексируемых таблиц с необходимым функционалом быстродействие окажется выше… А вообще я сомневаюсь, что в "кулинарной книге" так уж необходимо сверхкритичное быстродействие.
На личном опыте… Я давно писал на курсач похожую тему на голом C + WinAPI. Так вот со структурами данных я так извращался, что до сих пор пугаюсь, когда свой тот код открываю. Просто тебе будет очень сложно отслеживать все ссылки при работе с базой, если ты замутишь то, что хочешь.
Для начала посоветую определиться, что важнее - скорость добавления записей или скорость поиска? Может есть смысл заюзать хэш-таблицы?
А так же насколько большая будет база… может есть смысл всё хранить в массивах? ^^
Если я тебя отговорил от "быстродействия" в пользу простоты разработки - то юзай C# и класс DataSet (который ADO.NET). Только вот сериализуется он медленно, так что сохранять придётся либо при помощи какой-нить СУБД, либо писать своё сохранение, либо пользоваться медленным. Про это видел статью на rsdn.ru. Ещё в .NET (3.5 и старше) есть такая хрень как Linq. Не видел, но говорят для быстрой и простой разработки - очень удобная вещь.
|
|
|
|
|
RE: Структура бинарного дерева - 2008-10-11 04:23:49.870000
|
|
|
keys
Сообщений: 137
Оценки: 0
Присоединился: 2008-08-06 08:48:50.340000
|
quote:
множества уже изначально не надо упорядочивать, и гораздо проще находить их пересечение и объединение.
список можно по алфавиту упорядочить (не так мало видов блюд и видов ингредиентов), но при поиске можно рассмотреть его как множество (чтобы решить проблему с дубликатами), т.к. поиск картошка+морковка два раза выдаст один и тот же рецепт (чего бы не произошло при выводе сначала пересечения множеств заданных ингредиентов, а затем разности их объединения и пересечения)
|
|
|
|
|
RE: Структура бинарного дерева - 2008-10-11 15:27:01.953333
|
|
|
AchtungPartizanen
Сообщений: 38
Оценки: 0
Присоединился: 2007-10-25 20:54:58.030000
|
quote:
ORIGINAL: kreol
Ну, во-первых, о каких множествах ты говоришь? Из всех языковых средств на ум приходят только паскалевский "set of", но как бы такие множества могут содержать только целые числа.
А во-вторых, если нужен просмотр по категориям, то что мешает создать ещё один список для категорий? А если тебе нужен фильтр, то я вообще слабо представляю, как ты будешь использовать бинарное дерево. Тебе нужно пробегаться по списку и отображать те его элементы, которые проходят фильтр, а не искать конкретную запись.
Ну да, эта фигня первой на ум и пришла. Т.е. если в ней хранить либо прямые ссылки, либо некие индексы - то достать рецепт можно
Ну фильтр - определяет, что именно мы выводим на экран. Среди этого и производится поиск того, что вбил юзер. Юзер вбил в строку букву "п" - список прокручивается и в его центре мы видим первый же рецепт, начинающийся на п. Типа как в энцциклопедии КМ.
В любом случае нужен поиск в общем списке и поиск в конкретной категории.
Есть другой способ это все покрасивше организовать? (преподша окошки любит)
|
|
|
|
|
RE: Структура бинарного дерева - 2008-10-11 15:28:47.563333
|
|
|
AchtungPartizanen
Сообщений: 38
Оценки: 0
Присоединился: 2007-10-25 20:54:58.030000
|
quote:
ORIGINAL: keys
quote:
множества уже изначально не надо упорядочивать, и гораздо проще находить их пересечение и объединение.
список можно по алфавиту упорядочить (не так мало видов блюд и видов ингредиентов), но при поиске можно рассмотреть его как множество (чтобы решить проблему с дубликатами), т.к. поиск картошка+морковка два раза выдаст один и тот же рецепт (чего бы не произошло при выводе сначала пересечения множеств заданных ингредиентов, а затем разности их объединения и пересечения)
Ну вообще я думал, что если ищем рецепт по двум ингредиентам, то надо выводить рецепты, которые содержат только _оба_ ингредиента - т.е. пересечение. Ну это уже второстепенный вопрос
|
|
|
|
|
RE: Структура бинарного дерева - 2008-10-11 15:34:15.626666
|
|
|
AchtungPartizanen
Сообщений: 38
Оценки: 0
Присоединился: 2007-10-25 20:54:58.030000
|
quote:
ORIGINAL: _SaZ_
Ну с твоими запросами… Как раз таки у индексируемых таблиц с необходимым функционалом быстродействие окажется выше… А вообще я сомневаюсь, что в "кулинарной книге" так уж необходимо сверхкритичное быстродействие.
На личном опыте… Я давно писал на курсач похожую тему на голом C + WinAPI. Так вот со структурами данных я так извращался, что до сих пор пугаюсь, когда свой тот код открываю. Просто тебе будет очень сложно отслеживать все ссылки при работе с базой, если ты замутишь то, что хочешь.
Для начала посоветую определиться, что важнее - скорость добавления записей или скорость поиска? Может есть смысл заюзать хэш-таблицы?
А так же насколько большая будет база… может есть смысл всё хранить в массивах? ^^
Если я тебя отговорил от "быстродействия" в пользу простоты разработки - то юзай C# и класс DataSet (который ADO.NET). Только вот сериализуется он медленно, так что сохранять придётся либо при помощи какой-нить СУБД, либо писать своё сохранение, либо пользоваться медленным. Про это видел статью на rsdn.ru. Ещё в .NET (3.5 и старше) есть такая хрень как Linq. Не видел, но говорят для быстрой и простой разработки - очень удобная вещь.
Да ну не вижу особого смысла в таблицах. Создать структуру (или несколько структур), которые работают с названиями (поиск по рецептам), ингредиентами и категориями. А уже потом по названию рецепта вытягивать сам текст. Хотя…
Размер базы? Сам не знаю… Преподша сказала - "не слишком много". Ну, допустим, 50 - меньше уже несерьезно.
Критичней наверно все же скорость поиска. Но преподша поставила условие - чтобы пользователь мог добавлять рецепты (зачем это вообще нужно простому пользователю? но отговорить я ее не сумел)
Датасет… Кажется, работал с ним весной… Страх и ужас)))
|
|
|
|
|
RE: Структура бинарного дерева - 2008-10-12 02:41:48.136666
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
Итого… Если не хочешь сильно заморачиваться -> индексируемые таблицы для тебя. Если хочется поизвращаться - делай как хэш таблицы, если быстро, на не очень большой объём - массивы, как ни примитивно это звучит.
А если хочется сделать красиво - SQL… или C# + class DataSet, как я уже говорил. Хотя если будешь сам писать на шарпе - то всё равно не напишешь "ручную" выборку быстрее, чем это делает сам датасет.
Просто если будешь придумывать велосипед (свою структуру данных) - то замучаешься с удалением чего-нибудь из базы (удалением всех сылок на "это"). А так вперёд - дерзай…
|
|
|
|
|
RE: Структура бинарного дерева - 2008-10-12 02:51:13.666666
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
З.Ы. почитай про реляционные БД. Сначал будет непонятно - нафиг оно надо, но потом въедешь и поймёшь, насколько это шустрое, мощное и универсальное средство.
|
|
|
|
|
RE: Структура бинарного дерева - 2008-10-12 05:43:29.636666
|
|
|
keys
Сообщений: 137
Оценки: 0
Присоединился: 2008-08-06 08:48:50.340000
|
quote:
то надо выводить рецепты, которые содержат только _оба_ ингредиента - т.е. пересечение.
я за редакцию выборки (функция поиска отсеивает дубликаты, т.к. они никогда не будут нужны) а вывод, чем он проще тем лучше, если у тебя стандартный формат вывода то его можно прикручивать к любым программам а если он у тебя привязан только к одной тебе придётся его редактировать (короче не его это задача дубликаты выключать)
|
|
|
|
|
RE: Структура бинарного дерева - 2008-10-15 19:10:35.063333
|
|
|
AchtungPartizanen
Сообщений: 38
Оценки: 0
Присоединился: 2007-10-25 20:54:58.030000
|
Ну логичная же мысль, верно? :) БД - это не структуры и не алгоритмы. И преподша слово БД уже, мягко говоря, и слышать не хочет.
В общем, структура нужна однозначно, а БД - уже опционально.
Функции те же: добавление, удаление, поиск. Ну какой поиск, я уже говорил :) Главное - структура, структура и еще раз структура
|
|
|
|
|
RE: Структура бинарного дерева - 2008-10-15 19:13:37.910000
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
quote:
ORIGINAL: AchtungPartizanen
Короче, дана курсовая по структурам и алгоритмам…
Я как-то упустил из вида, что курсач по СИОД-у.
В общем делай, как задумал. Но очень внимательно пиши процедуры добавления / редактирования / удаления. Чтобы все все связи были учтены.
Смысла в деревьях не вижу, для начала лупи всё списками. Если быстродействия будет мало - перепишешь на деревья.
|
|
|
|
|
RE: Структура бинарного дерева - 2008-10-18 13:25:36.433333
|
|
|
AchtungPartizanen
Сообщений: 38
Оценки: 0
Присоединился: 2007-10-25 20:54:58.030000
|
quote:
ORIGINAL: _SaZ_
В общем делай, как задумал. Но очень внимательно пиши процедуры добавления / редактирования / удаления. Чтобы все все связи были учтены.
Смысла в деревьях не вижу, для начала лупи всё списками. Если быстродействия будет мало - перепишешь на деревья.
Какой смысл списки делать? Я лабы по поиску сам делал - видел, что бинарный поиск на порядки быстрее последовательного. Хотя и то и другое упорядочивать придется…
|
|
|
|
|
RE: Структура бинарного дерева - 2008-10-18 15:58:11.773333
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
Поиск по бинарному дереву - далеко не самый быстрый. Как-то я делал индексный поиск файлов на компьютере, так там дополнительно к таблицам самих данных было ещё несколько индексных таблиц, которые хранили номера того или иного символа (например, слова начинающиеся с 'A' идут с 345 номера). Примерно то же самое для второго символа. Получалось действительно быстро, но добавлять туда новые записи было очень трудно и долго (но индексный поиск файлов это и не требует). Бинарные же деревья - это что-то вроде компромиса в скорости добавления и поиска. Если делать так, как я сказал, то списки для тебя будут просто готовыми выборками. То есть добавляя элемент в список ты сразу готовишь его для извлечения. Понадобилось вытянуть все блюда по определённому признаку - берёшь готовый список и вуа-ля.
В любом случае я бы советовал создать два класса - List и BinaryTree (ну или взять готовые) - и сделать для них все необходимые методы. Тогда твоя главная структура получится не такой уж страшной, а обращение с ней не таким запарным.
|
|
|
|
|
RE: Структура бинарного дерева - 2008-10-21 18:14:32
|
|
|
AchtungPartizanen
Сообщений: 38
Оценки: 0
Присоединился: 2007-10-25 20:54:58.030000
|
Короче, пара предложений
Первое. Каждый рецепт делать как структуру, у которой задать поле под заголовок, поле под собственно текст (ну или же индекс, по которому вынимаем текст из базы в файле), поле под группу (суп, гарнир или десерт) и ряд булевских полей под ингредиенты. Если блюдо содержит ингредиент ing2 - значит, Блюдо.ing2=true.
Плюсы очевидны. Можно быстро выудить блюда по ингредиенту, не создавая дополнительных списков по каждому блюду. Легко выудить все блюда из группы супов, содержащих в списке ингредиентов ing1 и ing 2 (или же наоборот, не содержащих ничего кроме ing1 и ing2). Для проверки того, что блюдо содержит ing15, требуется проверить всего одно условие if(ing15).
Минусы, к сожалению, тоже очевидны. При самом лучшем раскладе минимальное число ингредиентов будет не меньше двух десятков - структура с 20 булевскими полями будет довольно громоздкой, хотя память занимать не так и много. К тому же программа сможет работать только с заранее определенным списком ингредиентов - когда пользователь задумает написать новый рецепт, он сможет указать только те ингредиенты, которые известны программе
Второе, более принципиальное. Использовать параллельно две структуры: список и дерево. Список содержит всю информацию о рецептах. В нем рецепты лежат в порядке добавления - здесь упорядочивание и не нужно. Со списком пользователь работает напрямую только при добавлении и удалении рецептов. На основе списка уже формируется упорядоченное дерево, с которым пользователь работает при поиске. То есть интерфейс - а-ля КМ: есть окошко, в котором списком выводятся все заголовки рецептов (из дерева), такой список можно прокручивать; если пользователь вводит что-то в строку поиска - список прокручивается так, что в центре видимой части списка тот заголовок, который начинается с того, что ввел пользователь. Допустим, юзер ищет котлеты по-киевски. Он вводит в строку "Котлеты по-к" - и в центре оказывается то, что начинается с введенной строки. Ну и клик по какому-либо заголовку в списке приводит к тому, что в соседнем текстбоксе открывается соответствующая статья. Можно грабить корованы:D
Поиск в любом случае осуществляется по дереву, которое упорядочено по алфавиту. В дереве содержится только инфа для поиска: заголовок, группа (?), инфа о ингредиентах (?), указатель (или индекс) на элемент списка, который уже содержит полную инфу о блюде, включая текст рецепта. Далее, у юзера под рукой - набор фильтров: отображать только блюда конкретной группы (или групп) и/или содержащие конкретные ингредиенты. И при изменении фильтров дерево пересобирается заново. Допустим, изначально у нас отображены все блюда. Юзер ставит флажок напротив "включить фильтр", выбирает группу супов, жмет на кнопку - и теперь в списке перед ним только супы. Соответственно, поиск идет только среди супов. Потому что дерево было уничтожено и создано заново.
Плюсы. Поиск заметно ускоряется за счет того, что в нем вообще не нужны проверки на группу и ингредиенты - только бинарный поиск по названию, потому что область поиска уже ограничена так, как надо.
Минусы. Дерево пересобирается при каждом изменении фильтра - пока вообще неизвестно, сколько это будет занимать времени, а тем более если юзер будет играться с фильтрами постоянно. Кроме того, дерево будет гарантированно несбалансированным, если же его балансировать - то это увеличивает время создания дерева.
В общем, жду ваших комментариев по поводу этих гениальных идей
|
|
|
|
|
RE: Структура бинарного дерева - 2008-10-21 19:42:06.750000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
пока вообще неизвестно, сколько это будет занимать времени
Много.
quote:
если юзер будет играться с фильтрами постоянно
Будет. По крайней мере преподователь точно поиграется.
Дерево слишком долго пересобирать, так что сразу забей на эту идею. У тебя должны быть готовые структуры данных, по которым ты будешь искать. Эти структуры должны формироваться при добавлении рецептов, но ни в коем случае не при самом поиске.
Насчёт буленовских полей. Минусы ты сам понял, решить можно очень просто: вместо буленовских полей использовать набор битов. Делаешь одно поле на 8-10 байт (массив, лучше всего) и получаешь 64-80 возможных ингридиентов. В отдельной таблице хранишь соответсвия названий ингридиентов и номера бита, который шифрует наличие такового. Проверка на наличие нужного ингридиента делается очень просто: полне "ингридиент" ксорится с маской, где все биты равны нулю, кроме бита проверямого ингридиента. Если получился ноль, то такого ингридиента нет, если что-то другое - есть. Для добавления новых ингридиентов достаточно внести их в таблицу соответствия. Но учти, сколько бы байт не занимало твоё поле с ингридиентами, их число всё равно будет ограничено, а если ингридиентов наоборот будет слишком мало, то будет беспечно расходоваться память. Но скорость и простота проверки будут, это да.
|
|
|
|
|
RE: Структура бинарного дерева - 2008-10-22 12:30:26.646666
|
|
|
AchtungPartizanen
Сообщений: 38
Оценки: 0
Присоединился: 2007-10-25 20:54:58.030000
|
quote:
ORIGINAL: kreol
Дерево слишком долго пересобирать, так что сразу забей на эту идею. У тебя должны быть готовые структуры данных, по которым ты будешь искать. Эти структуры должны формироваться при добавлении рецептов, но ни в коем случае не при самом поиске.
Хм… Интересно, как описанные мной выше действа реализуются в самом КМе…
quote:
ORIGINAL: kreol
Насчёт буленовских полей. Минусы ты сам понял, решить можно очень просто: вместо буленовских полей использовать набор битов. Делаешь одно поле на 8-10 байт (массив, лучше всего) и получаешь 64-80 возможных ингридиентов.
Не совсем понял с организацией…
А почему xor? Может, побитовая конъюнкция?
|
|
|
|
|
RE: Структура бинарного дерева - 2008-10-22 14:00:01.760000
|
|
|
AchtungPartizanen
Сообщений: 38
Оценки: 0
Присоединился: 2007-10-25 20:54:58.030000
|
Так все-таки как сама организация битовых полей будет выглядеть, можно поподробнее?
|
|
|
|
|
RE: Структура бинарного дерева - 2008-10-22 18:19:40.250000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
char ingredients[10]; // фактически, набор битовых флагов для указания на наличие или отсутствие ингридиентов
char* ingNames[80]; // массив названий ингридиентов, каждый элемент соответствует одному биту в предыдущем масиве
// заполнение масства
ingNames[0] = "Salt";
ingNames[1] = "Sugar";
ingNames[2] = "Soda";
// проверка на наличие ингридиента под номером n
int n = 12;
// сначала вычисляем номер байта, с которым будем сравнивать
int byteNumber = n / 8;
// затем узнаём номер бита в байте, который соответствует нужному ингридиенту
int bitNumber = n % 8;
// создаём маску для проверки, для этого присваиваем переменной mask значени 2 в степени номера бита,
// который мы нашли раньше. Таким образом получится, что всегда будет установлен только бит номер bitNumber,
// а остальные сброшены
char mask = pow(2.0, bitNumber);
// проверяем, есть ли такой ингридиент
if ((ingredients[byteNumber] & mask) != 0) {
// такой ингридиент есть
} else {
// такого ингридиента нет
}
|
|
|
|
|
RE: Структура бинарного дерева - 2008-10-23 02:04:32.730000
|
|
|
keys
Сообщений: 137
Оценки: 0
Присоединился: 2008-08-06 08:48:50.340000
|
quote:
Легко выудить все блюда из группы супов, содержащих в списке ингредиентов ing1 и ing 2 (или же наоборот, не содержащих ничего кроме ing1 и ing2)
твоя задача, если хочешь быстродействие, не делать поиска вот такого, т.к. при миллионе рецептов, тебе нужно будет проводить тысячи проходов по дереву чтобы отыскать у кого есть там индикатор а у кого нету, выцеплять их надо из уже готовой таблицы (ингредиент-индекс_в_большом_дереве (каждая запись такой таблицы))
по второму: если у тебя есть список, содержащий индексы из большого дерева, то и фильтрацию можно делать с его помощью (туда куда не надо выходить можно просто закрыть от отображения на экран, туда куда надо разрешить отображаться) (в этом плане, тебе не нужно будет его динамически перезагружать всё время)
|
|
|
|
|
RE: Структура бинарного дерева - 2008-10-23 11:36:25.693333
|
|
|
AchtungPartizanen
Сообщений: 38
Оценки: 0
Присоединился: 2007-10-25 20:54:58.030000
|
quote:
ORIGINAL: keys
quote:
Легко выудить все блюда из группы супов, содержащих в списке ингредиентов ing1 и ing 2 (или же наоборот, не содержащих ничего кроме ing1 и ing2)
твоя задача, если хочешь быстродействие, не делать поиска вот такого, т.к. при миллионе рецептов, тебе нужно будет проводить тысячи проходов по дереву чтобы отыскать у кого есть там индикатор а у кого нету, выцеплять их надо из уже готовой таблицы (ингредиент-индекс_в_большом_дереве (каждая запись такой таблицы))
Вообще-то моя идея - с точностью до наоборот. Проверка, у кого есть индикатор, у кого нет, делается на этапе создания дерева. Собственно, дерево на момент поиска уже содержит только то, что надо - и здесь будет уже простой бинарный поиск по заголовку. Такую вещь (бинарный поиск по текстовому полю) я уже как-то делал, правда по массиву, а не по списку/дереву.
А дерево пересобирается не при каждом поиске (зачем?), а когда юзер меняет фильтры и жмет на кнопочку. Долго это или нет - но я все равно хочу это опробовать…
quote:
ORIGINAL: keys
по второму: если у тебя есть список, содержащий индексы из большого дерева, то и фильтрацию можно делать с его помощью (туда куда не надо выходить можно просто закрыть от отображения на экран, туда куда надо разрешить отображаться) (в этом плане, тебе не нужно будет его динамически перезагружать всё время)
Хм… А вот насчет закрыть от отображения - можно подумать…
|
|
|
|
|
RE: Структура бинарного дерева - 2008-11-28 21:16:10.140000
|
|
|
AchtungPartizanen
Сообщений: 38
Оценки: 0
Присоединился: 2007-10-25 20:54:58.030000
|
Структуру все же дописал (были кое-какие внешние отвлекающие факторы)
Два вопроса. Первый: как лучше организовать интерфейс с поиском? Т.е. предполагаемый вывод списка заголовков и открытие соответствующего блюда на форме при двойном клике на одном из заголовков?
И второй, глобальнее. Как сохранять всю структуру в файл? Какой формат, какие алгоритмы и т.д. Ну и чтение соответственно тоже
|
|
|
|
|
RE: Структура бинарного дерева - 2008-11-29 03:08:24.316666
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
В файл нельзя записать списко или дерево, зато можно записать массив. Как сохранить список в массив, я думаю, понятно. Для бинарного дерева необходим массив структур, практически таких же, как и узлы дерева, только в полях-ссылках на потомков вместо указателей в память использовать номера массива, где хранятся эти потомки. Потом банальным обходом сверху вниз записываешь все элементы дерева в массив, а массив спокойной запихиваешь в файл.
|
|
|
|
|
RE: Структура бинарного дерева - 2008-11-29 18:56:45.980000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: kreol
В файл нельзя записать списко или дерево
почему?
|
|
|
|
|
RE: Структура бинарного дерева - 2008-11-29 22:50:49.833333
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: Denaturat
quote:
ORIGINAL: kreol
В файл нельзя записать списко или дерево
почему?
Ну стандартное дерево или стандартный список, который оперирует ссылками по всей памяти, как ты запишешь в файл? Всё равно придётся сохранять его последовательно. Конечно, можно сериализовать его по ходу сохранения, но идея останется той же.
|
|
|
|
|
RE: Структура бинарного дерева - 2008-11-30 12:50:55.043333
|
|
|
AchtungPartizanen
Сообщений: 38
Оценки: 0
Присоединился: 2007-10-25 20:54:58.030000
|
Да вообще в принципе можно и список/дерево (дерево также прошито простым списком) - ссылки тут не принципиальны, все равно дерево будет собираться при запуске проги. А в сам файл как сохранить? Какой формат лучше?
|
|
|
|
|
RE: Структура бинарного дерева - 2008-12-02 02:11:46.003333
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: AchtungPartizanen
Да вообще в принципе можно и список/дерево (дерево также прошито простым списком) - ссылки тут не принципиальны, все равно дерево будет собираться при запуске проги. А в сам файл как сохранить? Какой формат лучше?
Блин, я ему говорю, что нельзя так просто дерево записать в файл, он всё равно говорит, что можно, но при этом спрашивает у меня как. В каком формате захочешь, в таком и сохраняй. Самое банальное - обычный бинарный файл, а чтобы можно было писать потоком, лучше сохранить всю структуру во что-нибудь последовательное, массив, например. Список или дерево - это куча маленьких объектов, разбросанных по всей памяти (упрощённо, но суть всё равно такая).
Если очень хочется выпендриться, можешь дерево в XML-файл записать. Но нафига это делать в твоей задаче я без понятия.
|
|
|
|
|
RE: Структура бинарного дерева - 2008-12-04 13:25:33.306666
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
ORIGINAL: kreol
Самое банальное - обычный бинарный файл, а чтобы можно было писать потоком, лучше сохранить всю структуру во что-нибудь последовательное, массив, например. Список или дерево - это куча маленьких объектов, разбросанных по всей памяти (упрощённо, но суть всё равно такая).
Если очень хочется выпендриться, можешь дерево в XML-файл записать. Но нафига это делать в твоей задаче я без понятия.
Самый простой способ записать дерево в файл – это записать его туда в текстовом виде. В бинарном придётся иметь горы дополнительных полей которые будут сообщать длины других полей.
Я бы не изобретая велосипедов, взял бы lisp'овский формат. То есть вот такое дерево:
1 корень
1.1 первая ветвь
1.1.1 лист
1.1.2 лист
1.2 вторая ветвь
1.2.1 продолжение ветви
1.2.1.1 лист
1.2.2 ещё одно продолжение Выглядело бы примерно так:
("1 корень" ("1.1 первая ветвь" ("1.1.1 лист" "1.1.2 лист")
("1.2 вторая ветвь" ("1.2.1 продолжение ветви" "1.2.1.1 лист")
("1.2.2 ещё одно продолжение"))))
Идея в том, что чем глубже мы забираемся в скобочке, тем дальше мы от корня. Первый токен после открывающей скобочки – это имя ветви. Их я проставлял для удобства, понятно дело его можно не ставить вообще, если он не нужен для данных которые хранятся. Писать и читать такие структуры – одно удовольствие. Правда делать это лучше рекурсивно, чтобы каждый вызов читающей функциии читал бы то, что от открывающей скобочки и до соответствующей закрывающей, и возвращал бы это в виде указателя на готовую структуру.
С тем же успехом можно было бы использовать xml, но парсить xml резко сложнее. Там уже без конечного автомата будет сложно.
Ещё один огроменный плюс текстового формата – тестовые данные можно подготовить в любом текстовом редакторе. ;)
|
|
|
|
|
RE: Структура бинарного дерева - 2008-12-04 21:39:40.100000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: rgo
Самый простой способ записать дерево в файл – это записать его туда в текстовом виде. В бинарном придётся иметь горы дополнительных полей которые будут сообщать длины других полей.
Ну здесь речь идёт бинарном дереве, значит детей у каждого поля будет всего два. Максимальный размер строк тоже можно ограничить. К тому же, как я понимаю, структура получилась более сложной, чем просто дерево, со множеством перекрёстных ссылок. Не уверен, что такую структуру можно красиво записать в текстовый файл. Ну и в конце концов, в файл нужно записывать бинарные данные (например, битовые флаги). Конвертировать их туда-обратно - допольнительная головная боль.
Но идея с лисповским форматом хороша) Возьму на заметку.
А XML хорош тем, что для него есть куча готовых парсеров, бери и используй)
|
|
|
|
|
RE: Структура бинарного дерева - 2008-12-04 23:14:00.056666
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: kreol
Но идея с лисповским форматом хороша) Возьму на заметку.
А XML хорош тем, что для него есть куча готовых парсеров, бери и используй)
для S-выражений их тоже хватает. да и написать самому если что куда как проще
в данном случае это несущественно, но для бинарных данных есть хороший стандартный формат ASN.1, рекомендую ознакомиться
|
|
|
|
|
RE: Структура бинарного дерева - 2008-12-04 23:44:21.323333
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
ORIGINAL: kreol
quote:
ORIGINAL: rgo
Самый простой способ записать дерево в файл – это записать его туда в текстовом виде. В бинарном придётся иметь горы дополнительных полей которые будут сообщать длины других полей.
Ну здесь речь идёт бинарном дереве, значит детей у каждого поля будет всего два. Максимальный размер строк тоже можно ограничить. К тому же, как я понимаю, структура получилась более сложной, чем просто дерево, со множеством перекрёстных ссылок. Не уверен, что такую структуру можно красиво записать в текстовый файл. Ну и в конце концов, в файл нужно записывать бинарные данные (например, битовые флаги). Конвертировать их туда-обратно - допольнительная головная боль.
Да хоть это будет граф произвольный. Его можно просто в несколько деревьев.
Ограничивать что-то в размерах я ненавижу с того момента, когда меня в школе познакомили с массивами. Я тогда ещё четвёрку схлопотал из-за того, что при написании программы на бейсике при объявлении массива использовал некую N – ни разу не объявленную переменную. Я, при этом, чётко знал что программа работать не будет, но я определённо не знал, какое значение подставить вместо N: 5? 100? 93? При этом я мальчик был скромный и спорить с учителем информатики, которого считал Величайшим Гуру На Свете не осмелился: четыре, значит четыре.
Если лень битовые флаги пихать в виде отдельных записей, то можно поступить так: printf ("%x", flags); ;)
Кстати мне в голову пришла мысль, что всё это ещё можно упростить, если описание самих рецептов закинуть в файл просто линейным списком (в csv-формате: по строке файла на рецепт, разделитель полей запятая), а загоняя в файл дерево вместо самих рецептов писать номера этих рецептов. Так просто написание парсера превратится в задачку для начальной школы.
Мне известно лишь два недостатка текстовых форматов хранения/передачи инфы:
1. сложно изменить только один рецепт. Надо перезаписывать весь файл для этого.
2. больше места занимает, чем тоже самое в бинарном формате. С этим можно бороться каким-нибудь gzip'м, и вероятно получить объём даже меньший, но это уже процессорное время начинает расходоваться.
В подавляющем большинстве ситуаций эти недостатки незаметны. А главный плюс текстового формата сложно переоценить: его можно редактировать текстовым редактором, перехватывая трафик можно читать общение http-клиента с http-сервером без специального софта, который будет декодировать именно http, и, наконец, текстовый формат можно сканировать grep'ом, awk'ом или perl'ом.
ps. кстати есть совсем дебильный способ хранения в текстовом формате. И несмотря на всю дебильность я его использовал как-то раз =)
Можно выводя в файл, выводить в виде C'шного кода, объявляющего и инициализирующего глобальные переменные. А для ввода обратно в программу, компилировать и подгружать как динамическую библиотеку. Правда до динамической библиотеки я не добрался – статически объектный файл с программой скомпоновывал, – но, каюсь, было дело.
|
|
|
|
|
|
