Выбор типа дерева (структура данных) для хранения данных в БД , БД "Гараж из автомобилей"

Всем хай! Сходу к делу!

Столкнулся с такой задачей.
Есть сущность "Автомобиль", описываемый следующими полями:

• Марка
• Страна-производитель
• Год выпуска
• Максимальная скорость
• Стоимость
• Краткое описание

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

В БД может быть миллиарды автомобилей (можно принимать, что даже триллионы, т е есть оторванность от реального мира).

Минимальный перечень допустимых операций над данными:

• Добавление нового авто
• Удаление авто
• Редактирование данных выбранного авто (всех полей или выборочно)
• Поиск авто в БД по любому из его полей (вообще по любому!)
• Сортировка по любому из полей (кроме краткого описания)
• Импорт и экспорт в файл/из файла

Есть жесткое требование: нужно использовать структуру данных дерево (допустимо использовать МНОГО деревьев, а не только одно) для выполнения всех операций. И нужно выбрать ОПТИМАЛЬНОЕ дерево из всех ныне известных деревьев, дающих максимальную эффективность работы.

Что понимать под эффективностью. Сходу 3 фактора напрашивается:

• Скорость выполнения всех вышеуказанных операций
• Сложность кодирования
• Занимаемая память

Как понимаю, считаем, что занимаемая память примерно везде одинаковая, поэтому этот фактор исключаем.
Принимаем, что квалификация разработчика высокая и он в состоянии закодировать любое дерево за примерное одинаковое время.
Остается лишь требование ПО СКОРОСТИ выполняемых операций.

В мире существует 10ки, если не 100ни различных деревьев (бинарка, бинарное дерева поиска, АВЛ, префиксное, постфиксное, сильноветвящееся, splay, красно-черное, фибоначчи и т.д. и т.д., можно продолжать оооооооочень долго).

У меня есть мысль такая: нужно создать семейство деревьев (какого типа, пока не знаю), где у каждого ключом выступает отдельное поле автомобиля. Например, в 1ом дереве все заточено на "Марку", во 2ом дереве на "Производителя" и т.д.

Подскажите, какую бы вы использовали древовидную структуру данных, для решения подобной задачи (создание БД из автомобилей)??
В идеале 2 варианта ответа: 1. оптимальное дерево (любой сложности кодирования). 2. не самое оптимальное дерево (но кодируется гораздо проще, чем дерево из варианта ответа №1).

спс. за внимание

Сообщение отредактировано: FasterHarder - 23.06.20, 08:11

Цитата FasterHarder @ 23.06.20, 08:05

Есть жесткое требование: нужно использовать структуру данных дерево

Список автомобилей в виде дерева? Это как пониматьвашу?

JoeUser, ну, да, что тут такого!)
Нужно в программе задействовать древовидную структуру данных, благодаря которой происходит обработка данных (БД из авто)

Вроде реализация хранения, поиска и пр. в MS SQL Server реализована через сильноветвящиеся деревья, но это вроде...

Добавлено 23.06.20, 08:34

Скрытый текст

Цитата JoeUser @ 23.06.20, 08:27

Список автомобилей в виде дерева?

или речь про слово "список"?)
ну, возьми синонимы: набор, перечень, множество (хотя перечень и множество тоже могут вызывать вопросы)

FasterHarder, если ты реально хочешь пользоваться всеми плюшками SQL реляционной базы данных - проектируй наборы и отношения согласно стандарту SQL. А это - плоские таблицы и их отношения. И "дерево" из них можешь построить. Ну а если nosql движки - тогда обозначь, что собираешься юзать.

Хрень какая-то. Ну заведи таблицу со всеми индексами, в чём проблема? Конкретный тип индекса выбирай такой, который строит деревья. Зачем что-то самому для этого писать?

OpenGL, плюсую.

Добавлено 23.06.20, 10:39

Цитата OpenGL @ 23.06.20, 10:33

Конкретный тип индекса выбирай такой, который строит деревья.

Нет такого типа индекса Индексы существуют для быстрого упорядочивания по полю (или группе полей). А вот "построение дерева" - это уже прерогатива запросов. Как "запросишь"- то и получишь.

Цитата OpenGL @ 23.06.20, 10:33

Хрень какая-то. Ну заведи таблицу со всеми индексами, в чём проблема? Конкретный тип индекса выбирай такой, который строит деревья. Зачем что-то самому для этого писать?

ничего не понял, хрень какая-то!

Еще раз поясню, хотя тут, господи, абсолютно элементарная постановка!!
Есть массив авто.
Есть на выбор любая древовидная структура данных.

Нужно выбрать из множества предлагаемых древовидных структур такую, которую обеспечит максимальную эффективность по скорости обработки авто (перечень операций приведен в посте №1).

Т е нужно взять либо АВЛ, либо фибоначчи, либо что-то еще.
НЕПОНЯТНО ЭТО ЧТО ЛИ ДАЖЕ????? жесть!

Я не спорю, может с индексами что-то и здравое, но ничего непонятно, что имелось в виду.

Какая на хрен nosql, зачем мне ANSI-стандарт, есть массив авто и его нужно запихнуть в древовидную структуру. ВСЕ!! ни грамма больше.

Вы вообще читаете постановку задания??? Лень даже внимательно прочитать, ясно))

Добавлено 23.06.20, 11:07
и еще это: я не смогу провести эксперименты на разных типах деревьях, чтобы апробацией выяснить, какое же дерево дает лучшую производительность, т к:
1. я слаб в деревьях как таковых
2. их слишком много + они сложны в понимании

Если бы я узнал, какое дерево наиболее эффективно в данном случае, то смог бы с ним поразбираться)

Цитата FasterHarder @ 23.06.20, 11:00

Есть на выбор любая древовидная структура данных.

Не бывает такого в постановке задачи.
У тебя либо задача "узнать, как как устроены деревья", и тогда просто напиши rb-tree (самый популярный способ реализации сортированных контейнеров в стандартных библиотеках языков программирования, так что наверняка и самый быстрый в среднем) и без привязки к автомобилям и прочим сущностям.
Либо у тебя задача "хранить данные по автомобилям", и тогда оптимальное решение - воспользоваться любой СУБД, т.к. авторы движка БД деревья уже написали, и совершенно точно они сделали это лучше, чем сможешь написать ты за приемлемое время.

Добавлено 23.06.20, 13:51

Цитата JoeUser @ 23.06.20, 10:34

Нет такого типа индекса

А это что?

Цитата

PostgreSQL поддерживает несколько типов индексов: B-дерево, хеш, GiST, SP-GiST, GIN и BRIN.

Даже если в другой СУБД у тебя явно не будет сказано, что индекс под капотом строит дерево, я на 146% уверен, что в индексах, которые будут использовать операции сравнения значения поля, СУБД построит какое-нибудь самобалансирующееся дерево, т.к. это достаточно естественно.

Сообщение отредактировано: OpenGL - 23.06.20, 13:52

Цитата OpenGL @ 23.06.20, 13:46

Не бывает такого в постановке задачи.

точно могу сказать, что не бывает достаточно хороших ответов на форуме вот это стопудняк!!!
а запретить такое требование никто не может!

взяли и сказали: юзать ТОЛЬКО деревья и ничто иное. Кто запретит? ты, трамп, путин, кто??? Логика?? так эта задача академическая.

единственное, что добавлю, под БД в данном контексте я понимаю массив данных, тупо массив данных.
речь не идет ни о СУБД ни о СУРБД и вообще привязки к языку SQL 0.0. ЕЩЕ РАЗ! нет тут SQL. ЕЩЕ РАЗ: нет тут SQL. нет, не поймут...


Сколько всего древовидных структур в компьютере сайнсе? сотни...наверное...вот какая тут вписывается лучше всего...а вот хрен его знает...
ЧТОБЫ ДАТЬ ответ на этот вопрос, нужно знать характеристики всех деревьев (ну или большинства самых используемых) иначе сопоставить их не получится. Я вот не знаю (да, представь себе, бывает такое, что челик что-то не знает, не знал об этом, да, ну вот доношу).

И не надо мне рассказывать про скорость поиска в отсоритрованности и пр. пр. Это все будет не по теме!
У меня оч.маленький вопрос: какое дерево лучше взять. Все. Можно ответить 3 словами)) ...если знать...только деревья на фундаментальном уровне знают единицы

и не надо мне рассказывать о том, что можно взять другую структуру данных, более оптимальную. Хочешь, бери, а мне не нужна. Речь ПРО ДЕРЕВЬЯ...

ДЕРЕВЬЯ!!! есть такая динамическая структура данных мощнейшая...

Цитата FasterHarder @ 23.06.20, 11:00

Вы вообще читаете постановку задания??? Лень даже внимательно прочитать, ясно))

А давайте прихерачим сваркой паровоз к пароходу! Пацаны, какие лучше электроды для сварки выбрать???
(FasterHarder, вот примерно так твой вопрос звучит для психически здоровых людей!)

Не злись и не обижайся,но ты путаешь термины. "Хранение данных" и "Отображение данных" - это связанные, но абсолютно перпендикулярные абстракции!!! Для представления списка узлов дерева - нужен просто список. Для отображения списка в виде иерархии - нужна вторая таблица, назовем ее relation (отношения). Как найти корень, откуда начать строить "дерево"? В таблице "отношений" найти узел, у которого нет "родителей". А как строить дальше? В таблице "отношений" искать узлы и их потомки.

Заметь - это реализация "одна из". Тк. вторая таблица может содержать не отношения "чел-потомок", а, допустим "чел-родитель". И тогда пересчет будет совсем иным.

JoeUser вот чего ты мне затираешь? умным хочешь показаться? так лучше ответь на поставленный вопрос!)
есть четко формализованная задача! куда вам еще больше разжевывать? ну, куда? машинку нарисовать в пэинте только остается для визуализации...так все равно и это НЕ поможет)

должен был прозвучать такой вопрос, от вас экспертов (пока не видно, что эксперты): а какая частота выполнения той или иной операции. Непонятно о чем речь? Ок, поясню!! Например, чаще всего выполняется операция добавления или чаще всего происходит операция доступа к последним данным и пр. Это важнейший момент в выборе структуру данных. Так хрен кто спросил!! Всем бы поумничать на хрен знает какую чешую ни имеющую ни толики смысла в данном контексте))

Отвечаю: вероятность любой операции над деревом одинаковая. Нет тут перегибов. Думаю, что не поняли, что я имею в виду, ну ладно...

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

ЗЫ: вангую, ответ я НЕ получу, как и много раз раньше...все это проходилось и повторяется многократно...хотя если знать, можно за минуту ответить...если знать...

И что характерно, данный мной вполне чёткий ответ с указанием типа дерева ТС проигнорировал

Цитата OpenGL @ 23.06.20, 14:26

данный мной вполне чёткий ответ с указанием типа дерева ТС проигнорировал

про индексы мне также подсказали еще на другом форуме!
я же написал, что до конца не понимаю эту чешую в таком пояснении. ну, да, типа моя проблема)

я так понимаю, что предлагают хранить индексы в узлах дерева, а где сами данные-то хранить! в наличии ТОЛЬКО дерево и все, ну или совопкупность деревьев.

короче: я думаю, что все сведется к построению семейства бинарных деревьев в соот-вии с полями сущности авто. Непонятно? да плевать))

Цитата FasterHarder @ 23.06.20, 14:28

я так понимаю, что предлагают хранить индексы в узлах дерева, а где сами данные-то хранить! в наличии ТОЛЬКО дерево и все, ну или совопкупность деревьев.

В узле дерева у тебя будет в этом случае пара (значение поля, идентификатор записи об автомобиле). Идентификатором записи может быть что угодно, по чему ты сможешь однозначно получить саму запись (хоть банальный указатель на запись в памяти). Для каждого поля строишь своё такое дерево. Если ты меняешь поле, то ты удаляешь его из дерева (старое значение поля, идентификатор), и добавляешь (новое значение поля, идентификатор).

Цитата FasterHarder @ 23.06.20, 14:28

короче: я думаю, что все сведется к построению семейства бинарных деревьев в соот-вии с полями сущности авто.

Да, как-то так.

FasterHarder, постановка задачи такова, что БД – это первое, что приходит в голову и альтернатив как-то не особо не видно. Так что я бы не обижался на советы типа "используй СУБД". Другое дело, если целью является написать нечто подобное СУБД самому... но это уже не Алгоритмы, это уже технология, которую следует обсуждать в других разделах. И по-любому начало будет как-то типа "накачать книжек по теории проектирования СУБД и их реализации".

Цитата Qraizer @ 23.06.20, 15:20

постановка задачи такова, что БД – это первое, что приходит в голову и альтернатив как-то не особо не видно. Так что я бы не обижался на советы типа "используй СУБД".

так дело в том, что требуется на деревьях все реализовать, БД - типа набор связанных таблиц и все такое.
или имеется в виду, что нужно БД построить на основании деревьев? хм...ну, может быть, кстати, так и нужно) С другой стороны де-факто любое дерево с данными можно рассматривать, как БД по умолчанию...но это все равно все как бы не совсем по теме...

и с чего вы взяли, что я обижаюсь? я что, радоваться должен, когда мне какую-ту фигню пишут и читают какие-то морали...
меня бы обидело, если бы ответов было 0 в теме)) это да, обидно, что никто помочь даже не пытается...

Данные подаются из текстового файла. записей может быть много (да хоть миллиард)
Если строить бинарные деревья поиска, то нужно дать идентификатор каждой машине, но так, чтобы при формировании бинарок дерево как бы заполнялось равномерно (стремилось к полному). Если пронумеровать машины с 1 шаг +1, то деревья тупо вырождаются в список, лол, тупо будет очень...
Пока непонятно, что делать с идентификатором. Ну есть какие то мысли, присваивать 1ой машине = 1, 2ой машине = число машин, 3ой машине = 2, 4ой - число машин - 1 и т.д. не знаю...

Также очень важный вопрос ПРО БАЛАНСИРОВКУ деревьев. ДДП ведь не предполагает эту операцию, она ведь производная (типа по ситуации).
нужна балансировка или нет? ответа не будет - вангую)

Добавлено 23.06.20, 15:33

Цитата Qraizer @ 23.06.20, 15:20

Другое дело, если целью является написать нечто подобное СУБД самому

прикалываешься что ли)
делать самописные СУБД нужна минимум твоя квалификация, я и на 5% не потяну...

задача академическая ведь.
вся фишка этой задачи выбрать правильное дерево или список деревьев.
данные по сути состоят только из одной таблицы.
почему у вас всех какие-то мысли масштабные: делать СУБД, сделать конурента MS SQL или даже оракла...вы чего)...задача академическая...

Челу дают советы - а он бычится, вместо того, чтобы попытаться осознать. Тупой как дрова

Показываю вам всем нормальный ответ (отвечать на форумах вас нужно учить очень и очень и очень и очень много и долго, спецы тип Qraizer - исключение, ответы его всегда почти идеальны в разделах "си, плюсах и пр."). Хотя поздно учить - форум скоро уйдет в небытие, к сожалению...Это неизбежно!

Вот вам небольшой пример понятного мне ответа!
---------------------------------------------------------------
Так, FasterHarder, по заданию все понятно. Молодец, тщательно все описал, не поленился.
Ты хочешь 2 варианта дерева: посложнее (профессиольное решение) и попроще (с изъянами).
Сложный вариант: можешь попробовать поразбираться с QT-TREE. Но учти, там важна отсортированность данных.
Простой вариант: семейство бинарных деревьев поиска. Каждое дерево отвечает за конкретное поле сущности "Авто". У тебя вроде 6 полей. Вот и построй 6 деревьев. Кстати, балансировка желательна. Сделай, если справишься. И разберись с идентификатором авто, чтобы их отличать друг друга (по примеру первичного ключа)
Если будут вопросы - задавай! При возможности помогу. Если нужна работа под ключ - пиши в личку, сделаю за деньги)
--------------------------------------------------------------

и никаких гвоздей, по крайней на 1е время!!
и не надо ничо больше...

ЗЫ: 80% отвечающих не слышат спрашивающего) Так всегда и на всех форумах во всех разделах! ФАКТ! да даже прочитать постановку не могут, начинают лепить собственное видение, предлагать какие-то альтернативы и пр., хотя спрашивающему все это даром не сдалось)

ЗЫЗЫ: #18 - весь в тебя)

Так в этом-то и корень, FasterHarder, что твоя задача выглядит как многословное "как написать БД". Потому и пишут в ответ ...э-э-э, "фигню". У меня вот тоже первой мыслью было посоветовать почитать теорию проектирования движков СУБД и вырезать оттуда лишнее. Формально там все ответы должны быть. Но не стал, ибо кто я в этом разделе и кто завсегдатаи.

Цитата FasterHarder @ 23.06.20, 08:05

Подскажите, какую бы вы использовали древовидную структуру данных, для решения подобной задачи (создание БД из автомобилей)??

Лично моё мнение будет практически совпадать с уже озвученными. Берём любую подходящую структуру данных, которая имеет амортизируемо константную сложность добавления/удаления элементов и низкие накладные расходы на эти операции и служебную информацию. Из Плюсового stl лучше всего подходит дэк: связный список массивов фиксированного размера. Помещаем в него все структуры в произвольном порядке, почему бы и не в порядке чтения из внешнего источника данных. Индексируем по каждому полю и создаём структуры данных для индексов. Они должны обеспечить логарифмическую сложность поиска и апдейта. Опять же из Плюсового stl тут подходит множества, ибо реализуются через КЧ-деревья, они ещё и балансируются сами... ну, почти сами. На каждое поле, по которому может быть выполнен поиск, свои индексы, т.е. своё множество. Каждый индекс в множестве просто ссылается на конкретный автомобиль в хранящем их дэке. Ключ для сортировки просто определяется методом сравнения автомобилей по соответствующему полю, например, для названий лексикографическое сравнение, для скоростей – простое математическое, итп. При добавлении элемента в нашу БД дописываем его в конец дека и апдейтим множества индексов; при простом поиске выбираем соответствующее критерию множество и отбираем весь удовлетворяющий границам диапазон; при удалении элемента удаляем из дека и опять-же апдейтим индексы; при комплексом поиске можно выбрать один из двух вариантов: либо создаём временный индекс ака множество и пользуем некоторое время, пока актуально, либо разбиваем сложный запрос на простые и применяем последовательно каждый с исключением или объединением, в зависимости от связей простых условий в комплексное, промежуточных результатов.

Сообщение отредактировано: Qraizer - 23.06.20, 16:32

Qraizer, вот чорт меня дернул упомянуть термин БД...у меня просто ДАННЫЕ, ну, тупо 1на таблица...

спс, конечно, но я еще даже не дочитал твой монолог, как сразу 2 момента:
1. язык СИ (который чистейший)
2. структура "дек". Это ведь вставка и в начало и в конец + такие же удаления. Но это ведь НЕ древовидная структура. А др.структуры использовать нельзя. Ну, как минимум обработка дерева начинается с корня (точка входа в дерево), а дек нарушает это требование.

поэтому, я конечно признателен, но такое...про идентификаторы поразбираюсь
так ведь вроде решено делать через семейство бинарок...там есть сложности, но я пока поразбирауюсь как-нибудь с ними

Цитата

Так, FasterHarder, по заданию все понятно. Молодец, тщательно все описал, не поленился.

Не обманывайте себе. У вас описание всегда не годное куча лишней информации и 0 нужной. Во вторых вы все равно не слушаете других и делаете все по своему.

Qraizer, я оценил твои попытки решения - но, уверяю, это пока не твое Когда речь идет о выборках данных - решают две вещи: само проектирование данных и набор запросов ним. Обвязка в виде ЯП - это гораздо вторичнее.

Pavia не льсти себе, "дружок"). У меня исчерпывающие постановки, иначе будет тотальный мрак с ответами...
последних лет 5, наверное, твоя польза в моих глазах равна 0.0! да, возможно, кому-то ты помогаешь как боженька, возможно...
я за себя говорю)

Цитата Pavia @ 23.06.20, 16:38

Не обманывайте себе

+1

Добавлено 23.06.20, 16:46

Скрытый текст

FasterHarder, когда ты проспишься - тебе будет стыдно. Не пей больше смелую воду.

Цитата

так дело в том, что требуется на деревьях все реализовать, БД - типа набор связанных таблиц и все такое.
или имеется в виду, что нужно БД построить на основании деревьев? хм...ну, может быть, кстати, так и нужно) С другой стороны де-факто любое дерево с данными можно рассматривать, как БД по умолчанию...но это все равно все как бы не совсем по теме...

Нет БД это и есть деревья все современные БД используют B+ деревья
http://citforum.ru/programming/theory/sort...ng2.shtml#5_1_2
http://citforum.ru/database/osbd/glava_39.shtml#_4_1_2_1

У крутых СУБД можно ещё другие структуры использовать.

Сообщение отредактировано: Pavia - 23.06.20, 17:18

Я, кажется, догадываюсь, что мечтает получить препод. Задача разбивается на множество подзадач, для каждой из которых оптимальным будет свой тип структуры поиска. Причем одного указания типа мало, нужно еще и подумать (с калькулятором в руках) над деталями реализации, с учетом огромного количества хранящихся записей. При этом также очень полезно помнить про тонкости работы железа (например, кэш-памяти). В общем, может получиться очень интересная и содержательная беседа двух умных людей.

Если нужен полезный совет: FasterHarder, готовь бутылку хорошего коньяка (или что там препод любит).

Цитата FasterHarder @ 23.06.20, 16:37

1. язык СИ (который чистейший)

Не проблема. Я не призывал использовать Плюсы и stl, я лишь, см. начало поста, описал свои мысли. И тем не менее, упоминание языка и библиотеки дают хороший старт к поиску инфы для самореализации описанных в посте идей.

Цитата FasterHarder @ 23.06.20, 16:37

2. структура "дек". Это ведь вставка и в начало и в конец + такие же удаления. Но это ведь НЕ древовидная структура. А др.структуры использовать нельзя. ...

Не проблема. Можно хранить деревом. Только зачем? Поиск всё равно всегда выполняется по индексам, так что выгода от дерева в самом хранилище полезной информации никак не востребована, тогда как дерево имеет бо́льшие накладные на служебную инфу и производительность. Иными словами запрет на использование других структур данных ухудшает ТЗ.

Цитата FasterHarder @ 23.06.20, 16:37

... Ну, как минимум обработка дерева начинается с корня (точка входа в дерево), а дек нарушает это требование.

Предположим, данные исходно лежат на диске в файлике. Вопрос: «можно вообще не хранить инфу, а индексы пусть ссылаются на смещения от начала файла» нарушает ТЗ?

Добавлено 23.06.20, 17:27
Повторю: индексы древовидны.

вот, придумал хороший вариант!
не нужно никакое семейство бинарных деревьев! Как минимум нерациональное использование дин.памяти.

1. индексируем исходные данные (добавляем первичный ключ). Можно рандомом пройти. Общее число записей ведь известно.
2. строим бинарное дерево поиска (без балансировки) по КЛЮЧАМ, второе поле узла дерево - информационная часть об авто. Все в одном месте хранится!
3. операция удаления происходит по ключу, поэтому выполняется за логарифмическое время (или какое-то там, не знаю, в общем быстро)
4. операция вставки - аналогично.
5. сортировка! Допустим, хотим отсортировать данные по названию авто. СТРОИМ вспомогательное дерево (также ДДП), но лексикографическое по названию. Для этого достаточно один раз просмотреть исходное дерево, вынимая от туда узлы и добавлять в вспомогательное. Затем элементарно делаем обход по дереву названий и выводим либо ASC, либо DESC. Это касается всех полей. Да, будет 6 различных функций, делающих примерно одно и то же. Шаблонов в СИ нету. После печати по названий - дерево вспомогательное уничтожаем и получаем исходное состояние.
6. при поиске делаем п№5, а затем запускаем бинарный поиск нужной информацию по конкретному полю.
7. с редактированием. По ключу - поэтому нет проблем.


Все, думаю, меня это устроит! Реализовать еще нужно грамотно - тоже дело непростое ведь)
В итоге сам со всем разобрался. Ну, как и обычно в принципе...)
Насчет балансировки: ну, желательна, конечно...хм...надо подумать...

P.S. вот так и думаешь, ну, канет форум в небытие, много ли я потеряю...сложный вопрос...Иногда на форуме выручают очень круто, но это лишь очень и очень иногда...

Добавлено 23.06.20, 17:34

Цитата AVA12 @ 23.06.20, 17:23

Если нужен полезный совет: FasterHarder, готовь бутылку хорошего коньяка (или что там препод любит)

, если бы все было так просто
эта задача взята с бесконечных просторов инета...

Добавлено 23.06.20, 17:37
Qraizer, спс за конструктивный материал (сложноватый местами для понимания)

Цитата FasterHarder @ 23.06.20, 17:32

не нужно никакое семейство бинарных деревьев! Как минимум нерациональное использование дин.памяти.

B+ это не бинарные деревья.

Цитата

B+ это не бинарные деревья.

Верно. Но при чем тут inode? Это совсем из другой оперы.

AVA12, если есть желание, то плз чекни алгоритм из поста №29 (я там постарался упросить насколько возможно).
там еще можно провести оптимизацию, не удалять из памяти отсортированное дерево, если не было удаления/вставки новых данных.

Пожалуйста, навскидку:

Цитата

1. индексируем исходные данные (добавляем первичный ключ).

Индексирование данных - это не добавление первичного ключа. Это построение индекса (т. е. структуры поиска) по какому-то ключу.

Цитата

2. строим бинарное дерево поиска (без балансировки) по КЛЮЧАМ, второе поле узла дерево - информационная часть об авто. Все в одном месте хранится!

Что такое "дерево поиска по КЛЮЧАМ"? Имеется в виду дерево с составным ключом? Несколько деревьев по разным ключам? Что-то еще?

Цитата

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

"или какое-то там, не знаю" - преподу так же отвечать будешь?

Цитата

5. сортировка! Допустим, хотим отсортировать данные по названию авто. СТРОИМ вспомогательное дерево (также ДДП), но лексикографическое по названию. [...] После печати по названий - дерево вспомогательное уничтожаем

То есть на каждый поисковый запрос строим новый индекс? Ты не забыл, что в базе миллиарды записей? И что для построения индекса нужно просмотреть все записи?

Цитата

7. с редактированием. По ключу - поэтому нет проблем.

Ну, если у нас только один индекс, по неизменному первичному ключу - тогда да, тут проблемы нет.

Ты не рассмотрел проблему большого количества записей (подсказка: в память индекс целиком не влезет, и это только верхний пласт проблемы). Ты не обосновал оптимальность (и даже применимость) двоичных деревьев поиска. Ты не указал, как будешь решать проблему с совпадающими значениями ключей (подсказка: стран, производящих автомобили, гораздо меньше, чем миллиарды). Ты не объяснил, как (и с какой целью) ты будешь индексировать поле "описание".

Короче, садись, неуд.

Цитата AVA12 @ 23.06.20, 18:09

Верно. Но при чем тут inode? Это совсем из другой оперы.

Опера та же самая. ФС и БД не отличимы друг от дружки. Решают одни и тежи задачи.
Во-вторых где Вы там inode разглядели? Ext - хороша тем, что изначально не требует сложной реализации и может реализована в упрощенном виде.
И самое главное она реализована чисто на дереве без использования прочих структур, что и просил ТС.

Цитата

Ты не рассмотрел проблему большого количества записей (подсказка: в память индекс целиком не влезет, и это только верхний пласт проблемы).

ТС вам написал, что для него это задача академическая, а не практическая.

inode в этом плане одна из самых экономичных структур так как часть данные может хранятся непосредственно в ней.

Сообщение отредактировано: Pavia - 23.06.20, 20:58

Цитата

ФС и БД не отличимы друг от дружки. Решают одни и тежи задачи.

Нет, задачи у них во многом схожие, но не совпадающие.
Ты пояснил, что B+ это не бинарные деревья, и привел картинку - зачем? Человек, не знакомый с темой, может решить, что это пример B+ деревьев (что на самом деле не так).

Цитата

Во-вторых где Вы там inode разглядели?

Так ведь карта блоков - это часть inode, разве нет?

Цитата

ТС вам написал, что для него это задача академическая, а не практическая.

Гм. Если задача теоретическая, то зачем упоминать миллиарды записей?

Цитата AVA12 @ 23.06.20, 22:28

Ты пояснил, что B+ это не бинарные деревья, и привел картинку - зачем? Человек, не знакомый с темой, может решить, что это пример B+ деревьев (что на самом деле не так).

На это картинке изображено B+ дерево.


https://ru.wikipedia.org/wiki/B⁺-дерево

Цитата

B⁺-дерево — структура данных на основе B-дерева, сбалансированное {\displaystyle n}n-арное дерево поиска с переменным, но зачастую большим количеством потомков в узле. B⁺-дерево состоит из корня, внутренних узлов и листьев, корень может быть либо листом, либо узлом с двумя и более потомками.

Сообщение отредактировано: Pavia - 24.06.20, 05:08

Цитата AVA12 @ 23.06.20, 19:44

Ты не рассмотрел проблему большого количества записей (подсказка: в память индекс целиком не влезет, и это только верхний пласт проблемы). Ты не обосновал оптимальность (и даже применимость) двоичных деревьев поиска. Ты не указал, как будешь решать проблему с совпадающими значениями ключей (подсказка: стран, производящих автомобили, гораздо меньше, чем миллиарды). Ты не объяснил, как (и с какой целью) ты будешь индексировать поле "описание".

Короче, садись, неуд.

не не не! Двоек у меня никогда не было за последнюю тысячу лет) да и сдавать я буду ее сам себе, хехе.

1. Количество записей будет штучек 30. Ну, максимум 100. Отображение в консоли через псевдографику (красивый каркас таблицы) происходит ооооочень медленно. Даже 20 записей отображаются НЕ мгновенно. миллион, например, записей отобразиться через несколько часов (может суток) - смысла в этом ноль все равно, т к их не просмотреть будет. Делать перелистывание данных в консоли - не вариант, даже думать об этом не буду. Поэтому на ограничение про память забываем. Тут проблемы нет.

2. Идентификатор принято сразу добавить во входной файл с данными. Иначе там будет не стыковка. Это тупо целое натуральное УНИКАЛЬНОЕ число из отрезка [1 ... общее кол-во машин]. Проблемы тут нет! Добавляет по sizeof(int) памяти к каждой записи таблицы. Думаю, памяти хватит. Тут проблемы нет.

3.

Цитата AVA12 @ 23.06.20, 19:44

И что для построения индекса нужно просмотреть все записи?

в процессе сортировки элементы последовательности просматриваются многократно. Мне же для построения упорядоченного дерева по нужному полю потребуется гораздо меньше. Правда при вставке будут многократные спуски по дереву для поиска нужной позиции, но это недолго (правда дерево несбалансированное...хм..)

4.

Цитата AVA12 @ 23.06.20, 19:44

Ты не объяснил, как (и с какой целью) ты будешь индексировать поле "описание".

, из поста №1:

Цитата FasterHarder @ 23.06.20, 08:05

Сортировка по любому из полей (кроме краткого описания)

"Описание" - просто текстовое поле.

Цитата AVA12 @ 23.06.20, 19:44

Ты не обосновал оптимальность (и даже применимость) двоичных деревьев поиска.

Неужели еще никто не понял, что данная задача обладает лютейшей сложностью, т к для выбора правильного дерева нужно знать все ныне существующие деревья, знать их лучшие худшие/случаи производительности и кучу др.характеристик. Этих деревьев изобретено свыше 1000, наверное. Там есть такая жесть. Иногда вижу какие-то закольцованные деревья, со связями к корню, к предку или на какой-то другой уровень и пр. Это все очень сложно. Это все очень сложно. Это все очень сложно. +сами по себе деревья имеют рекурсивную природу, а рекурсия один из сложнейших разделов информатики. На каком-то уровне рекурсию не сможет понимать ни один разработчик (самый великий даже) в мире (это со слов Макконела).

Какое бы дерево не взять за основу нет возможности за разумное время доказать, что оно является оптимальным в данном случае.
Бинарные деревья относительно простые. Но лишь относительно. На самом деле, ИМХО, это достаточно сложная структура данных. Простая структура, ну, например, массив одномерный (статический), да и то, там тоже полно тонкостей.

Жалко, у меня нету в наличии перечня всех названий деревьев существующих в айти на 2020 год. Запостил бы сюда простыню (без спойлера, разумеется) на многие экраны (красный цветом, полужирным, 48 размером шрифта)...ладно...

ЗЫ: мне больше ничего не нужно) ничего не нужно) хватит, пожалейте свое время) ничего мне не надо в рамках этой задачи, ну по крайней мере пока) т к любые ваши ответы (ну большинства) никогда не приближали меня к решению поставленной проблемы (речь не только про эту проблему, а про ЛЮБУЮ в целом)...это факт! ничего не надо, все хватит! Оставьте эту задачку в покое. Не мучайте ее, ей становится только хуже после ответов большинства, ахаха. Закрываем тему. Тему закрываем.

всем спс, кто писал конструктив. Мне это чуть-чуть помогло)

Бурный у вас вечер.

Как сделано у меня в реале.

Есть класс Устройство с кучей полей... храниться в памяти.
делаем std::map или std::unordered_map
Где первичным ключем будет какое-то нужное поле (строка/число), а значением - ссылка на этот класс в оперативной памяти.
Сколько полей для поиска, столько и мап-ов.
Вообщем по аналогии: ключ/ссылка.

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

FasterHarder

Цитата

"Описание" - просто текстовое поле.

Вопрос в том фиксированного размера или это Blobs? И нужен по нему полнотекстовый поиск с обратным индексом.

Цитата

Неужели еще никто не понял, что данная задача обладает лютейшей сложностью, т к для выбора правильного дерева нужно знать все ныне существующие деревья, знать их лучшие худшие/случаи производительности и кучу др.характеристик. Этих деревьев изобретено свыше 1000, наверное. Там есть такая жесть. Иногда вижу какие-то закольцованные деревья, со связями к корню, к предку или на какой-то другой уровень и пр. Это все очень сложно. Это все очень сложно. Это все очень сложно. +сами по себе деревья имеют рекурсивную природу, а рекурсия один из сложнейших разделов информатики. На каком-то уровне рекурсию не сможет понимать ни один разработчик (самый великий даже) в мире (это со слов Макконела).

Как Вам сказать? Просто молчат из вежливости. Сложности нету, если бы вы критерий сравнения озвучили, а Вы не озвучили и решили заняться анализом. Но профессор не читает книжек по анализу алгоритмов. А дедушка Кнут в своем 3-х томнике уже проанализировал кучу деревьев. Многие его тут читали, в отличии от вас поэтому уже знают что B+ деревья оптимальны по большинству параметров. Есть и деревья и по круче которые были разработаны позже и не вошли в эти книги.

У меня проблем не было. После решения 10 учебных задач на деревья и рекурсию и динамическое программирование. Самое сложное что делал это обход AST дерева для определения типа переменной.
https://gitlab.com/pavia00/pop/-/blob/maste...nticCheking.pas

Цитата

1. Количество записей будет штучек 30. Ну, максимум 100. Отображение в консоли через псевдографику (красивый каркас таблицы) происходит ооооочень медленно. Даже 20 записей отображаются НЕ мгновенно. миллион, например, записей отобразиться через несколько часов (может суток) - смысла в этом ноль все равно, т к их не просмотреть будет. Делать перелистывание данных в консоли - не вариант, даже думать об этом не буду. Поэтому на ограничение про память забываем. Тут проблемы нет.

У человека время реакции рук ног не превышает 100 мс. Так что такие задержки он переносит комфортно. Последний дебиа поставил так он теперь летает. Там 1000 мгновенно выводиться.
Для виртуальных компонентов отображать миллионы записей мгновенно не проблема.
https://yadi.sk/d/CLV_V2lVPqyZDA

Добавлено 24.06.20, 06:01

Black_Dragon

Цитата Black_Dragon @ 24.06.20, 05:30

Бурный у вас вечер.

Как сделано у меня в реале.

Есть класс Устройство с кучей полей... храниться в памяти.
делаем std::map или std::unordered_map
Где первичным ключем будет какое-то нужное поле (строка/число), а значением - ссылка на этот класс в оперативной памяти.
Сколько полей для поиска, столько и мап-ов.
Вообщем по аналогии: ключ/ссылка.

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

А есть пример? Мне вот интересно как в Си++ такое делается. И насколько Delphi в этом плане убог.

Сообщение отредактировано: Pavia - 24.06.20, 06:02

Pavia, не-не-не! я не понимаю, зачем все это! я не оценю этого ни на йоту!
мне нужен твой ответ стандартный: "так книгу открыть не пробовали и почитать".

не утруждай себя в будущем больше, я не оценю)
вот чего ты вообще прицепился к этой задаче? заняться больше не чем)) ты желаешь мне помочь - не смеши мои тапочки) У тебя единственная цель: понтануться своими знаниями и унизить спрашивающего) ВСЕ! другого не дано!

ЗЫ: господи, вот какие ты убогие сравнения приводишь, типа не читал и пр. Читать - не значить понимать! Время жалко на тебя, чтобы написать, что 90% из тобою написанного не помогает мне абсолютно...

N.B. поиск по описанию нужно исключать, т к нет четких правил этого поиска. Не нужно мне писать про LIKE и мета символы. Про полнотекстовый поиск, который реализован в промышленных СУРБД. Речь про то, что в задании нет четких инструкций поиска. Все будет упрощаться, все предельно будет упрощаться! Буду упрощать настолько, пока не останется то, что мне будет понятно на 100%. Все упрощу, донельзя, до копейки...до грамма...

Цитата Pavia @ 24.06.20, 05:59

Мне вот интересно как в Си++ такое делается.

Я бы просто с помощью boost::multi_index_container сделал это.

Цитата Pavia @ 24.06.20, 05:59

А есть пример?

класса обвертки?

Цитата Black_Dragon @ 24.06.20, 06:43

класса обвертки?

Да.

кстати, я тут уточнил насчет задания.
оказывается нужно ведь построить именно модель современной СУБД, ну, такую махонькую)
также есть призыв сделать нормализацию данных. хрен знает, зачем, ну ладно.

В общем нужно соорудить архитектуру похожую на архитектуру современных СУРБД (sql server, oracle).
не-не-не! я не готов! нет, конечно, конечно же нет! Это нереально абсолютно! Нереально. Ни за что на свете.

Во-первых, нужно досконально понимать внутреннее устройство хранения данных в БД. Там всякие В+, самоперестраюивающиеся деревья. Там чего-то данные хранятся по 8Кб или по 32, вообще не важно мне все это. За разумное время с этим мне не разобраться (если вы можете за 10 минут, ну, ладно, я вот не могу).
Во-вторых, нужно досконально знать все эти структуры данных. Тоже сложно. В+ какое-нибудь навороченное + нету как всегда НОРМАЛЬНОГО описания в инете. Спрашивать на форуме про В+-деревья - это сразу смерть понимания процесса. Этот этап можно поднять, но уйдет оч.много времени.

нет, не готов, конечно, строить такую архитектуру. нереал, без вариантов, ответ ОТРИЦАТЕЛЬНЫЙ, ни за что! нет нет нет...
все сделаю на бинарках) это еще сделать надо! на словах то все легко, а тут проектировать нужно еще все корректно, что тоже не просто...

все оказалось достаточно серьезно в плане постановки. тут за пару часов и не закодировать. хм...
ладно, упрощу донельзя, сделаю НЕОПТИМАЛЬНО на бинарках (понятно, что реализовано будет ужасно, алгоритмы будут несовершенные и пр.).
и тай сойдет (с)

подчеркиваю еще раз: и так сойдет (с)
если я добьюсь тупо работоспособности - буду считать, что я молодец и справился с задачей!
ВСЕ!!!

// Класс автомобиль
class Car {
string m_Name;
string m_Firma;
}
typedef Car* PtrCar;
 
// Базовый класс
class Wrap {
public:
virtual void Add(string key, PtrCar val) = 0;
virtual void Del(string key) = 0;
virtual PtrCar Find(string key) = 0;
virtual void DelAll() = 0;
}
// Класс по конкретному дереву
class WrapBTree : public Wrap {
protected:
// Внутренняя реализация
std::map<string, PtrCar> m_Tree;
public:
virtual void Add(string key, PtrCar val) { m_Tree[key] = val; };
virtual void Del(string key);
virtual PtrCar Find(string key)
virtual void DelAll();
}
 
Wrap *ptrName = new WrapBTree;
Wrap *ptrFirma = new WrapBTree;
PtrCar c = new Car;
c->m_Name = "Копейка"
c->m_Firma = "ВАЗ"
ptrName->Add(c->m_Name, c);
ptrFirma->Add(c->m_Firma, c);

Тестовый набор действий можно загнать в функцию, и только менять враперы под разные деревья и замерять нужные временные интервалы

Сообщение отредактировано: Black_Dragon - 24.06.20, 07:21

Как хорошо, что здесь все специалисты по деревьям!
Кроме меня
У меня как раз с деревьями проблема.

Скрытый текст

Хакими за счёт использования 2-3 деревьев понизил сложность своего алгоритма с O(n^3) до O(nlogn).
Мне даже смотреть противно на эти 2-3 деревья.
У меня честные двумерные массивы и двойной цикл крутится.
Чтобы догнать Хакими, мне нужно всего-то с O(n^2) понизить до O(nlogn). Вот только не пойму как.
Кнута что ли почитать...

Добавлено 24.06.20, 07:25
На топикстартёра не наезжайте, на нём одном весь раздел держится

Цитата swf @ 24.06.20, 07:23

на нём одном весь раздел держится

шаришь)

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

Цитата FasterHarder @ 24.06.20, 07:32

создай отдельную тему и там разбирайся

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

А что за задача-то?

Сообщение отредактировано: amk - 24.06.20, 07:41

ОФТОП!
Я забыла поверх своего сообщения написать одно слово - ОФТОП
Так что сорри, рейдерский захват темы не предполагался.
to amk

Скрытый текст

Задачу я непременно тут запощу в отдельной теме, только сейчас не могу, статья ещё не вышла.
Может кто помнит, 5 лет назад я тут на сорцах мучалась с алгоритмом размещения абсолютного 1-центра неориентированного графа, даже тема старая есть.
Вот эту задачу я сделала, алгоритм простой, прямыми вычислениями в двойном цикле за квадратичное время все эквивалентные центры находятся для одного ребра.
Эту задачу и некоторые обобщения.

Теперь нужно использовать специальные деревья и понизить выч. сложность до nlogn.
Пока я этого не сделала, у Хакими алгоритм быстрее.
Вначале, конечно, сама попробую сделать, всё равно летом никуда не поедешь.

Цитата swf @ 24.06.20, 08:40

Теперь нужно использовать специальные деревья и понизить выч. сложность до nlogn.

OpenMP?

Pavia:

Цитата

На это картинке изображено B+ дерево.

Не-а.

1. У B(+)-деревьев количество дочерних узлов может варьироваться. У карты файловых блоков количество элементов в каждом узле (кроме последнего "листа") фиксировано.
2. B(+)-деревья позволяют вставку и удаления узла/листа, при этом затрагивается максимум log(n) узлов. Чтобы вставить или удалить узел в карту файловых блоков, нужно перетряхнуть все последующие узлы (в худшем случае - вообще все).
3. Узлы B(+)-дерева содержат как ссылки на дочерние узлы/листья, так и значения ключей. Карта файловых блоков содержит только ссылки, никаких ключей в ней нет.
4. B(+)-дерево - это дерево поиска. Карта файловых блоков - это, в общем-то, и не дерево, это сегментированный массив.

AVA12
1)

Цитата

У B(+)-деревьев количество дочерних узлов может варьироваться. У карты файловых блоков количество элементов в каждом узле (кроме последнего "листа") фиксировано.

.
В википедии сказано что как правило фиксированное:

Цитата

In B-trees, internal (non-leaf) nodes can have a variable number of child nodes within some pre-defined range.

Плюс у DOUGLAS COMER так же чётко сказано что ключей в узле 2d.
https://dl.acm.org/doi/pdf/10.1145/356770.356776

Цитата

i) Each path from tire-root to any leaf has the same length h, also called the
height of T, i.e., h = number of nodes in path.

https://www.inf.fu-berlin.de/lehre/SS10/DBS...yerBTree-72.pdf

3.

Цитата

Узлы B(+)-дерева содержат как ссылки на дочерние узлы/листья, так и значения ключей. Карта файловых блоков содержит только ссылки, никаких ключей в ней нет.

Ещё скажите что файлов не существует. Ключи там есть К примеру такие ключи как i_size и i_mtime используются для синхронизации файлов.

Цитата

struct ext2_inode {
__u16 i_mode; /* Тип файла и права доступа (см.ниже) */
__u16 i_uid; /* UserID */
__u32 i_size; /* Размер в байтах */
__u32 i_atime; /* POSIX время последнего обращения к файлу */
__u32 i_ctime; /* POSIX время создания */
__u32 i_mtime; /* POSIX время последней модификации */
__u32 i_dtime; /* POSIX время удаления */
__u16 i_gid; /* GroupID */
__u16 i_links_count; /* Кол-во ссылок на дескриптор */
__u32 i_blocks; /* Кол-во секторов (не блоки!) */
__u32 i_flags; /* Флаг (см.ниже) */
union {
struct {
__u32 l_i_reserved1; /* Зарезервировано */
} linux1;
struct {
__u32 h_i_translator; /* ??? */
} hurd1;
struct {
__u32 m_i_reserved1; /* Зарезервировано */
} masix1;
} osd1;
__u32 i_block[EXT2_N_BLOCKS];/* Указатели на блок */
__u32 i_generation; /* Версия файла (для NFS) */
__u32 i_file_acl; /* Доп. аттрибуты файла */
__u32 i_dir_acl; /* Доп. аттрибуты директории */
__u32 i_faddr; /* Адрес фрагмента */
union {
struct {
__u8 l_i_frag; /* Номер фрагмента */
__u8 l_i_fsize; /* Размер фрагмента */
__u16 i_pad1; /* Зарезервировано */
__u16 l_i_uid_high; /* 16 старших битов UserID */
__u16 l_i_gid_high; /* 16 старших битов GroupID */
__u32 l_i_reserved2; /* Зарезервировано */
} linux2; /* LINUX */
struct {
__u8 h_i_frag; /* Номер фрагмента */
__u8 h_i_fsize; /* Размер фрагмента */
__u16 h_i_mode_high; /* 16 старших битов T&P */
__u16 h_i_uid_high; /* 16 старших битов UserID */
__u16 h_i_gid_high; /* 16 старших битов GroupID */
__u32 h_i_author; /* UserID или автор */
} hurd2; /* GNU HURD */
struct {
__u8 m_i_frag; /* Номер фрагмента */
__u8 m_i_fsize; /* Размер фрагмента */
__u16 m_pad1; /* Зарезервировано */
__u32 m_i_reserved2[2]; /* Зарезервировано */
} masix2; /* MASIX */
} osd2; /* Специфичные значения */
};

4.

Цитата

B(+)-дерево - это дерево поиска. Карта файловых блоков - это, в общем-то, и не дерево, это сегментированный массив.

В ext не используется битовая карта(сегментированный массив блоков)

2)

Цитата

2. B(+)-деревья позволяют вставку и удаления узла/листа, при этом затрагивается максимум log(n) узлов. Чтобы вставить или удалить узел в карту файловых блоков, нужно перетряхнуть все последующие узлы (в худшем случае - вообще все).

Б+-деревья используются для хранения данных на жёстких дисках. Если Если использовать сегментированный массив и поверх положить Б+ дерево, то да.
Это будет быстрее, поэтому NFTS и выигрывает у EXT в скорости. Но тут палка о двух концах либо вы сразу занимаетесь балансировкой дерева либо потом делаете дефргаментацию массива.

Сообщение отредактировано: Pavia - 24.06.20, 19:34

Pavia
У меня складывается впечатление, что кто-то из нас бредит.

Цитата

В википедии сказано что как правило фиксированное:

Цитата

In B-trees, internal (non-leaf) nodes can have a variable number of child nodes within some pre-defined range.

Как ты думаешь, как переводится процитированная тобой фраза? В моем мире это переводится как "В B-деревьях внутренний узел (не лист) может содержать различное/переменное количество дочерних узлов, в рамках некоторого определенного диапазона." А как она переводится в твоем мире?

Цитата

Плюс у DOUGLAS COMER так же чётко сказано что ключей в узле 2d.

Да ну?

Цитата

In general, each node in a B-tree of order d contains at most 2d keys and 2d + 1 pointers, as shown in Figure 4.

В моем мире это переводится как "Вообще, каждый узел B-дерева порядка d содержит максимум 2d ключей и 2d + 1 указателей, как показано на рис. 4." А в твоем?

Цитата

i) Each path from tire-root to any leaf has the same length h, also called the
height of T, i.e., h = number of nodes in path.

И при чем тут высота дерева? Мы же говорим, скорее, о его ширине.

Цитата

Ключи там есть К примеру такие ключи как i_size и i_mtime

Во-первых, указанные поля inode ни к какому дереву не принадлежат, ни B-, ни C-, ни D-. Во-вторых, ты показал на картинке только часть inode - карту размещения файловых блоков. Т. е. структуру, хранящую номера всех блоков (в мире [Win]do[w]s их называют кластерами) с полезной нагрузкой конкретного файла.

Цитата

В ext не используется битовая карта(сегментированный массив блоков)

При чем тут битовые карты? (В ext они, кстати, используются - для поиска свободных inode и блоков). Слово "сегментированный" (синоним - "фрагментированный") означает "разбитый на части, возможно, хранящиеся в разных местах". Карта блоков в ext - это, по сути, массив, i-тый элемент которого (начиная с 0) является номером блока, который хранит байты [i*s .. (i+1)*s-1] конкретного файла (где s - это фиксированный размер блока). Поскольку разместить этот массив одним куском не всегда возможно (файлы растут, блоки добавляются), то приходится массив разбивать.

Цитата Pavia @ 24.06.20, 19:33

В википедии сказано что как правило фиксированное:

И сам тут же цитируешь: "variable number of child nodes" - переменное число дочерних узлов. А то, что выделено означает "в фикмрованных границах"

Цитата Pavia @ 24.06.20, 19:33

Б+-деревья используются для хранения данных на жёстких дисках.

Ты уверен, что именно данных, а не структуры файлов? То бишь дерева каталогов. Просто вставка данных в середину файла ни в одной файловой системе не реализуется системой, и возможности B+-деревьев оказываются сильно избыточными.

Насколько помню, в файловых системах ext, как и в UNIX (именно эту ФС использовала упомянутая в википедии Minix), используются иерархические списки блоков. Только размеры записей другие, что позволяет создавать очень большие файлы на просто огромных "дисках".

Про Minix я дописал после того, как проверил, что в вики написано.

Всё прочитал, ничего не понял.

Если исходить из полной постановки задачи, включая весьма странное требование "а подать сюда дерево", то первый вывод, который вылезает - а не будет тут дерева как такового.

Есть у нас автомобиль А в состоянии Ах. Мы что-то с ним делаем (любая операция корректировки), получаем автомобиль А в состоянии Ау, а родителем состояния Ау является состояние Ах. Делаем вторую операцию, получаем состояние Аz. Так вот - родителем состояния Az может быть только и исключительно состояние Ау, и ни при каких обстоятельствах родителем не будет Ах. Так что мы получаем не дерево, а его частный случай, прозываемый односвязным списком.

Уже проще.

Далее - условие задачи, озвученное в инит-посте, однозначно говорит о том, что этот односвязный список должен храниться в БД. Что опять же практически однозначно порождает структуру

- Уникальный идентификатор автомобиля (разумнее использовать естественный уникальный признак, а именно VIN);
- Уникальный автоинкрементный номер состояния (или штамп времени перехода в это состояние);
- Прочие атрибуты, в том числе FK.

Забавно, что постановка задачи такова, что исключает удаление записей, что в свою очередь делает ненужным наличие ссылки на запись-родитель, достаточно последовательной нумерации.

Комбинация первых двух полей образует естественный ПК. Для ускорения описанных операций используются соответствующие индексы. А вот когда заходит речь о том, как именно оптимизировать конкретную отдельную операцию - необходимо сначала определиться с конкретной СУБД и конкретной структурой, а потом мыслить об оптимизации.

Формально это, конечно, дерево, хотя реально - лес, где совокупность записей для отдельного автомобиля образует самостоятельное и независимое дерево.

Не, можно пробовать любую истинно "древесную" структуру - но смысл-то? то, что эффективно работает с деревом, скорее всего не будет самым эффективным в случае односвязного списка. Я уж не говорю о том, что некоторые структуры не работают с лесом, им одно дерево подавай (хотя на уровне СУБД это пофиг, просто ещё одно условие в запросе).

---

А дальше практически по всей теме идёт мысль, что никакой БД нет и в помине, что все данные загружены в память приложения, и там оно с этими данными и работает. Поневоле
хочется изречь нечто типа "Батюшка, вы уж определитесь, ...".

Проблема в том, что все очень умные, и задачу 3 класса пытаются решать интегралами и другими вузовскими приемами...
Задача академическая.

Я понял так.
В памяти есть большой объеме информации, как туда она попала не интересует, рандомный генератор делает...
Надо эмулировать работу с этой информацией как с БД: поиск, добавление и т.д.
Использовать деревья, определить эффективные (из какого-то набора) методом тестирования.

Цитата Black_Dragon @ 25.06.20, 05:55

Я понял так.
В памяти есть большой объеме информации, как туда она попала не интересует, рандомный генератор делает...
Надо эмулировать работу с этой информацией как с БД: поиск, добавление и т.д.
Использовать деревья, определить эффективные (из какого-то набора) методом тестирования.

Гм... рождается очередная резидентная БД? тогда мои соболезнования.

Цитата Akina @ 25.06.20, 06:07

Гм... рождается очередная резидентная БД? тогда мои соболезнования.

Дело не в БД, а применить деревья на чем-нибудь, сравнить их.

Цитата Black_Dragon @ 25.06.20, 08:00

Дело не в БД, а применить деревья на чем-нибудь, сравнить их.

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

Автомобиль тут формальность. Разноплановый набор данных, не более.
Например, ВИН или Госномер полностью уникальный ИД, не особо интересен. Кроме случая Госномера для поиска частичного соответствия.
Другие парамметры менее уникальные.

Вот ситуация.
Идет девушка, к ней подъезжает машина, водитель из машины дарит цветы и быстро уезжает.
Она хочет его найти.

Вбиваем в поиск: феррари, красный, двухдверный (трех), с откидным верхом (или с люком), пассажир назвал водителя Миша.

Цитата Black_Dragon @ 25.06.20, 08:52

Вбиваем в поиск: феррари, красный, двухдверный (трех), с откидным верхом (или с люком), пассажир назвал водителя Миша.

Так это обычный атрибутный поиск, логическое деление. Деревьями тут даже не пахнет.

Цитата Black_Dragon @ 25.06.20, 08:52

Вбиваем в поиск: феррари, красный, двухдверный (трех), с откидным верхом (или с люком), пассажир назвал водителя Миша.

ОФТОП
Типичная прологовская задача на организацию Базы знаний. И мудрить с деревьями не надо, список в прологе стандартно организован в виде дерева(голова - хвост).
Создаём предикат (отношение) owner(имя_владельца, автомобиль), а автомобиль - сложная структура car(марка, цвет, госномер, ...).
Записываем в Базу знаний факты по каждому владельцу и его автомобилю. У владельца может быть несколько автомобилей, для бесхозных автомобилей можно ввести какое-нибудь noname.

Цитата

список в прологе стандартно организован в виде дерева(голова - хвост).

Голова-хвост - это односвязный список. В принципе, можно трактовать его, как абсолютно вырожденное дерево, но зачем?

А у меня тем временем все готово! хехе

По факту получилось:
- 1300+ строк высокопроизводительного кода)
- 50+ функций, выполняющих строго одну операцию
- около 10 структур данных (очень похожих по составляющим)
----------------------------------------------------------
все прекрасно работает, интерфейс предельно дружественный и интуитивно понятный (куча подсказок и пр.).
глобальной обработки ошибок нет, так, местами есть кой какая защита
утечек в памяти не наблюдается (а там есть чему утекать, хехе)
система хорошо поддается расширению, вроде, хотя...может нет!
ход документирован, старался делать по Макконелу) (этого чувака люто уважаю и читаю его книги запоем!)
основная структура данных: двоичное дерево поиска с возможностью хранения дубликатных ключей БЕЗ балансировки

Единственное место, где мне пришлось отойти от бинарок - обработка количества пассажиров, находящихся в машине. Оно варьируется от 1 до 6. Я так чего-то прикинул, ну максимально тупо строить бинарку, хранящую всего 6 различных ключей (с дубликатами, разумеется). Если дано 90 млн. машин, у которых кол-во пассажиров равно 3 и ОДНА машина с кол-вом = 4 и эта машина (с 4мя пассажирами) добавляется последней в дерево, то все вырождается в ЛОС, при этом 4ка висит на хвосте, т е чтобы найти все машины с 4мя пассажирами пришлось бы просканировать 90млн узлов дерева. Нет уж, увольте, требования требованиями, но малейшая логика должна быть! Сделал массив списков, состоящий из 6 элементов и из каждого узла идет подписок на нужное число пассажиров. Дерево ли это? ну издалека похоже) Вообще, нет, ну, если допустить, что у узла может быть один потомок, то да)

Очень плохо, что структуры в СИ не имеют индексацию своих полей (хотя где-то видел пример через добавление указателей и чего то там мутили с объединениями, в общем я там ничего не понял и оч.рад этому) + единственная возможность в коде обращаться к ним - прописывать их название целиком.
В итоге мне нужно было строить СВОЮ отдельную бинарку для каждого поля сущности "авто", а их штук 8. При этом многие из них похожи донельзя(отличие только в названии поля). При этом ведь нужно добавить узел, сделать обход (2 способами) и удалить из памяти, минимум 4ре функции. А т к 8 полей, то РЕЗКО получаем избыточную хрень 8 * 4 = 32 функции, которые крайне похожи по обработке, но там разные поля структуры прописываются. Я хрен знает, как это шаблонизировать в си, вроде как-то делают, но я не выкупаю, да и так неплохо вышло)

Без понятия как оценить производительность работы прожки. Сравнивать не с чем. Данных нет, да и толку от них, все равно даже миллион записей не вывести на экран. Уверен, что можно все организовать эффективные в разы, используя ПРАВИЛЬНЫЕ древовидные структуры (да как бы еще знать их, века не хватит на их фундаментальное изучение), но и так все работает неплохо)

Если менять структуры данных. то придется выбросить весь код в корзину и переписывать с нуля (многие скажут, да-да, это будет лучшее в твоем случае, хе-хе, вот и выбрасывайте свои исходники, а мне мой нра)

В общем я доволен результатом! Нет, даже ОЧЕНЬ ДОВОЛЕН!!! Пойду съем мороженку)

И самое главный императив: и тай сойдет (с)

Цитата FasterHarder @ 25.06.20, 14:54

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

В чем проблема?
База есть, делаем разные алгоритмы, а потом для каждого запускаем идентичные операции и мерим время.

а это вот такая архитектура должна быть на уровне структур данных??

Прикреплённая картинка

Цитата AVA12 @ 25.06.20, 13:59

Цитата

список в прологе стандартно организован в виде дерева(голова - хвост).

Голова-хвост - это односвязный список. В принципе, можно трактовать его, как абсолютно вырожденное дерево, но зачем?

Бинарное дерево

Сообщение отредактировано: swf - 25.06.20, 17:23

FasterHarder
Кроме ФИО, все остальные поля - это справочники, по ним тупо отдельный массив с индексами (число), которые и будут использоваться.
По этому, структура для всех случаев будет идентична.

Цитата Black_Dragon @ 26.06.20, 02:55

ФИО

ягуар Сергей Иванович
опель Виктор Сергеевич
ты об этом ведать...

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

я приложил картинку, и спросил "да или нет?". так и не понял, так "да или нет"

FasterHarder
Ягуар, Опель, ВАЗ и т.д. Красный, Зеленый и т.д. и многие другие поля, это справочники, они кодируются 1, 2, 3 и т.д.

Структура да.

Цитата Black_Dragon @ 26.06.20, 07:56

Ягуар, Опель, ВАЗ и т.д. Красный, Зеленый и т.д. и многие другие поля, это справочники, они кодируются 1, 2, 3 и т.д.

как минимум это не поля, а значения полей конкретных объектов структуры, но пока на мой взгляд это не важно вообще. Называть можно как угодно.
а, я понял, ты хочешь создать для марок ОДТЕЛЬНУЮ таблицу с целочисленным первичным ключом и сделать связь не через строки, а через целые числа (по айдишнику). И так для каждого поля. Понятно, вот почему был призыв к нормализации. В итоге получаем солнцеобразную структуру БД: в центре данные и лучики исходят к 8 справочникам. Что характерно справочники между собой НЕ имеют ни одной связи. Такое оч.редко бывает в норм. БД)

Цитата Black_Dragon @ 26.06.20, 07:56

Структура да.

так, ясно. У меня реализовано не так, ну частично так. На миллиарды процентов Макконел прав, когда говорит, что оптимальное решение проблемы приходит только тогда, когда сделана минимум одна попытка решить эту проблему неэффективно. Как правило это приводит к ПОЛНОМУ переписыванию проекта (иногда больше 1го раза, хехе).

И тут есть такой важный момент с точки зрения памяти и эффективности.
Вот мы прочитали данные (ну, пусть из файла или с клавиатуры или еще как-нибудь - не важно вообще) и построили ГЛАВНОЕ бинарное дерево поиска (ключ у него идентификатор авто). Это как бы главное дерево для хранения данных.

Можно СРАЗУ построить все бинарки вспомогательные для всех полей сущности "Авто", их там штук 8. Т е обязательно строим главное дерево и можно построить 8 дополнительных (для каждого поля, по которому будет идти поиск, сортировка и пр.)
Минус первый - нужно много памяти. Хотя, если в узлах будут храниться целые числа, то sizeof(long) * 8 * <количество машин> + на указатели что-то там по мелочевке.
Во-вторых, если есть поля, по которым редко происходит обработка, ну, например, малое число запросов по полю "страна-производитель", то в таких случаях эту бинарку можно строить по мере необходимости? имеет смысл? (с др.стороны я уже писал раньше, что обращение к любому полю авто равновероятно)
в-третьих, когда меняются данные (удаление, вставка, апдейт), то сразу перестраиваем ГЛАВНОЕ дерево + нужно отследить все ссылки из всех бинарок на эти изменения. Чем больше вспомогательных деревьев, тем больше работы по этим указателям.

У меня в исходном проекте происходит некое дублирование всех данных об авто в памяти + деревья строятся по мере необходимости, т е в памяти висит ТОЛЬКО главное дерево с данными, а когда, например, нужно получить список авто отсортированных по марке, то я строию эту бинарку и вывожу ее на экран, после этого дропаю из памяти. это проблема...

Цитата FasterHarder @ 26.06.20, 08:18

сделать связь не через строки, а через целые числа (по айдишнику)

Да. Упрощает код, так как везде ИД. Ну и быстрее будет работать.

Цитата FasterHarder @ 26.06.20, 08:18

ГЛАВНОЕ бинарное дерево поиска (ключ у него идентификатор авто)

Да. И оно отвечает за сохранность данных.
Во всех остальных деревьях хранятся ссылки на эти данные.

Дальше я вижу так: деревья по главным полям.
Но размер этих деревьев будет очень мал, сколько у нас фирм? сколько у нас моделей у фирмы? Даже если взять года, то 100 всего будет.
Толку ноль...
Достраивать деревья во время поиска. Первичный Фирма, а там уже по годам и будет проще потом двигаться по разным годам.

Но если ключи сделать комбинацией полей... Фирма+Модель+Цвет (ID1*1000000 + ID2*1000 + ID3), Фирма+Цвет (ID1*1000 + ID2) и т.п.

Вообщем, все упирается в поиск

еще такой момент!
если в наличии у нас 50 млн. машин, то это НЕ означает, что у них уникальные атрибуты. Стран-производителей, ну 100, ну макс. 200 (ну не миллионы, однозначно ). Аналогично по цвету, по макс. скорости, по кол-ву пассажиров и т.д.

В итоге, нужно все нормализовать (как правильно заметил Black_Dragon), создать для каждого поля справочники со своими айдишниками и уникальными значениями.
исходные данные заменить на соот-щие коды из этих справочников. В итоге исходные данные превратятся В ЦЕЛЫЕ ЧИСЛА - крайне эффективно хранить в памяти.

Возьмем цвет для примера. В наличии 1200 машин зеленых и 1700 красных и 500 черных. По факту в справочнике цветов 3 записи с кодами (1 - зеленые, 2 - красный, 3 - черный). Получаем дерево из ТРЕХ узлов, но ключом выступает цвет при построении (а не код, т к если брать код, то все вырождается в список). И у каждого узла есть поле - массив указателей на все машины в главном дереве соот-щего цвета. Т е у корня (там зеленый цвет) будет массив указателей на 1200 узлов в главное дерево и т.д.

Это дает предельно быстрый поиск. Сортировать НЕ нужно, просто сделать ЛКП обход, т к информация в деревьях уже упорядочена при построении.
Можно сразу все грузить в память, т к это ничтожно мало занимает.

Единственная проблема, чисто техническая, правильно обрабатывать сильноветвящиеся деревья при удалении, вставке, апдейте.

Вот она, идеальная структура, только сейчас стало понятно, что должно быть) Да уж...нужно ВСЕ перекраивать (ну кроме импорта / экспорта данных). Эх, ну и ладно)

Цитата FasterHarder @ 26.06.20, 08:49

Единственная проблема, чисто техническая, правильно обрабатывать сильноветвящиеся деревья при удалении, вставке, апдейте.

Юзай готовые решения.
std::unordered_map

и, например, если потребуется тупо вывести информацию о конкретном авто (задается уник. айдишник авто), то:
1. ищем его в бинарном дереве поиска с данными(выраженными в числах) и запоминаем все внешние ключи (целые числа)
2. запускаем поиск по дереву нужной марки (код цвета мы взяли из этапа №1)
3. поиск по дереву нужного производителя
и т д.

10. вывод данных на экран

т е придется просмотреть ВСЕ деревья, чтобы собрать воедино реальные данные, а не их числовые айдишники. Учитывая то, что эти деревья небольшие, то все будет мгновенно.

это ладно, когда уникальных атрибутов не много. А если было бы какое-то поле типа данных float (дробное) с большим разбросом. В этом случае это дерево было бы по объему не меньше главного дерева. В этом случае это поле можно включить в главное дерево и не создавать для него справочника отдельного.

т е в справочники выносим частоповторяющуюся информацию, а редкую включаем в главное дерево.
понятно...

Цитата FasterHarder @ 26.06.20, 09:02

т е придется просмотреть ВСЕ деревья, чтобы собрать воедино реальные данные

Нет.
У тебя все данные хранятся в одной структуре, которая хранится в главном дереве по уникальном коду.

Добавлено 26.06.20, 09:09

struct Car {
ULONG m_VIN;
ULONG m_Firma;
ULONG m_Model;
ULONG m_Color;
//....
}

Цитата Black_Dragon @ 26.06.20, 09:07

У тебя все данные хранятся в одной структуре, которая хранится в главном дереве по уникальном коду.

я понимаю, о чем ты, но это не много не соот-ет духу БД.
ведь у нас в главной таблице обычно хранятся внешние ключи на справочники. а в справочниках реальные данные.

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

+зачем тебе хранить дубликаты данных в главном дереве.

не-не, у меня все шикарно)
ну не знаю, может есть какая-то грубая ошибка, но пока не вижу!

Добавлено 26.06.20, 09:21
вообще, как пишут в разных пособиях по SQL, мол, когда ищем информацию из связанных таблиц, итерпретатор (или кто там делает всю работу по поиску данных) начинает просматривать построчно все записи главное таблицы, а потом для каждой записи по коду ищет соот-вие в нужном справочнике, чтобы выдернуть реальное данное (а не код).

мне же НЕ придется этого делать!
скажут, хочу все машины ЗЕЛЕНОГО цвета. Я не буду сканировать все узлы данного дерева (если что, их там миллионы может быть). Тупо уйду в дерево, отвечающее за цвет, там найду узел с "зеленым цветом" и через массив ссылок узнаю, все нужные мне машины. Это эффективнее в миллионы раз может быть, чем перебирать все узлы главного дерева...

я пока так это понимаю

Цитата FasterHarder @ 26.06.20, 09:12

ведь у нас в главной таблице обычно хранятся внешние ключи на справочники. а в справочниках реальные данные.

У тебя справочники это: Цвет, Марка и т.д., которые ты заменил цифровыми ИД.
Основная запись и состоит из кучи ИД и некоторые оставшихся полей, например, вин, год, количество пассажиров, ФИО и т.д.

Получил ты эту запись и из массивов-справочников вытащил текстовые данные полей.

Добавлено 26.06.20, 09:31
+
Будет избыточность, но это это даст быстродействие.

Добавлено 26.06.20, 09:31
+
Ну и по хожу жизни программы ты можешь просто генерировать любые деревья на ходу.

вообще, тут глобальный момент такой: что быстрее (сделать один раз пробег по всем узлам главного дерева (там мжет быть под лярд данных) и очень много раз по вспомогательным, учитывая, что узлов во вспомогательных не больше 200 (по факту будет гораздо меньше)...

если примерное одинаково, тогда удобнее один раз по главному дереву, выдергивая по одной ссылке нужны данные!

Добавлено 26.06.20, 09:43
Вот, последний момент здесь остался!
Допустим, миллиард авто. (можно взять просто сто).
Из них 150 миллионов красных)

в одном случае чтобы получить все красные авто (+ все остальные поля, разумеется), нужно просканировать все узлы главного дерева). Ведь главное дерево упорядочено НЕ по цвету, а по своему АЙДИ. И это касается любого поиска, кроме поиска по айди!

в другом случае, чтобы получить все красные деревья - идем в цветовое дерево. МОменально определяем цвет и все ссылки на узлы главного дерева. Но этого недостаточно, нужно еще для каждой машины найти другие атрибуты. Всего 150 млн. красных. Значит для каждого другого цвета по 150 млн. раз ищем нужные атрибуты. Если деревьев еще 8 штук, то будет 150 * 8 = 1.2 млрд. узлов нужно просмотреть. Это чуть менее эффективно, чем в случае №1.

Но, если машин красных, всего 15 тысяч, то во втором случае потребуется 15 * 8 = 90 тысяч. Что эффективнее первого варианта в 10 раз.

Считаю, что 2й вариант производительнее в среднем! Но его сложнее кодировать, чем 1й...

Добавлено 26.06.20, 09:44

Цитата Black_Dragon @ 26.06.20, 09:30

У тебя справочники это: Цвет, Марка и т.д., которые ты заменил цифровыми ИД.
Основная запись и состоит из кучи ИД и некоторые оставшихся полей, например, вин, год, количество пассажиров, ФИО и т.д.

я это описывал выше!

Цитата FasterHarder @ 26.06.20, 09:32

Но, если машин красных, всего 15 тысяч, то во втором случае потребуется 15 * 8 = 90 тысяч. Что эффективнее первого варианта в 10 раз.

миллиард авто минус 15 тысяч, что с ними будешь делать?
Это твое убыстрение не по цвету в общем, а по конкретному цвету, т.е. по красному, значит остальные цвета в пролете.

Если тебе надо будет добавить еще поле или еще какие-то деревья, код переделывать не нужно.

Цитата Black_Dragon @ 26.06.20, 09:49

миллиард авто минус 15 тысяч, что с ними будешь делать?

в смысле?! они лежат там себе, греются на солнышке, ждут своей обработки)

короче! я определился! нужно делать через сильноветвящиеся деревья.
справочники ТОЛЬКО для строковых данных. Все числа хранятся в узле главного дерева. Какой смысл выносить число в справочник, если код тоже целое число, лол
справочников будет штук 5-6.
там еще есть поле "тип кузова" - вообще будет перечисление - через целое число.

Есть всегда сканировать все узлы главного дерева при поиске, то нет НИКАКОГО прееимущества поиска. Искать нужно начинать через спец.дерево (цветовое, марочное и пр.), а уже потом уточнять информацию через другие деревья.

этот вариант кодировать сложнее! если не получится, то перейду на скан всегда главного дерева, но это менее эффективно, разумеется! Лишь в некоторых случаях будет производительнее. А вообще все это оч. сильно зависит от типа входных данных.

На данный момент мне кажется, что я очень глубоко понимаю эту задачу и проблемы, которая она ставит.
Когда будет 2-й вариант программы, откроются новые страшные подводные камни и придется все перекраивать)) хехе

ты говоришь про масштабирование системы...хм...ну, допустим появляется НОВОЕ поле у авто (ну, например, степень изношенности, там типа бывает 35 видов ее), новый справочник со степенью изношенности добавили. все вспомогательные деревья перестраиваться не будут.
да, когда полей ооооочень много, штук 200, тогда оч.долго будет доставать всю информацию по кусочкам из каждого справочника - проще просканировать главное дерево.

я посчитал конкретно, сколько мне нужно справочников: 4 штуки всего.
кстати поле "краткое описание" по факту является уникальным (ну там могут быть случайные совпадения вплоть до буквы) придется хранить в узлах главного дерева.

ладно, я понял..
надо еще подумать немного и хватит)

Добавлено 26.06.20, 10:14
можно предельно упростить (за счет памяти дикой)
если включить все данные в узел главного дерева + все деревья построить для нужно поля. это по факту отказаться от связи по кодам!
тогда поиск - почти моментальный, просто сверхбыстрый
сортировка - почти моментальная, тупо обход нужного вспомогательного дерева

единственынй минус - хранить избыточные данные в колоссальном кол-ве! хм...
но быстродействие будет дичайшим!!!!

Цитата FasterHarder @ 26.06.20, 10:05

Есть всегда сканировать все узлы главного дерева при поиске, то нет НИКАКОГО прееимущества поиска.

Как это нет? Оно в дереве лежит, где поиск быстрее линейного перебора.
И не забывай, тебе на экран надо выводить по каждому авто всю инфу, когда человек будет листать список... По уникальному коду ты будешь сразу же быстро получать всю инфу по авто.

Цитата Black_Dragon @ 26.06.20, 10:24

Как это нет? Оно в дереве лежит, где поиск быстрее линейного перебора.

ты бы уточнял, о каком дереве речь: главном или вспомогательном/ых.
главное дерево построено по айдишникам авто, там все остальные поля в разнобой.

если просматривать все узлы дерева, то уже по боку, список (частный случай вырожденного дерева) это или дерево - сложность одна - просмотреть все элементы.

Цитата Black_Dragon @ 26.06.20, 10:24

По уникальному коду ты будешь сразу же быстро получать всю инфу по авто.

я нигде выше этого и НЕ отрицал) ну опять-таки, если под кодом понимается айдишник


здесь без сильноветвящихся деревьев не обойтись, лишь благодаря им можно в "миллионы" раз поднять производительность, иначе всегда полный скан главного дерева.
меня люто смущает, что нужно правильно закодировать эти сильноветвящиеся! там до хрена нюансов при удалении, вставке. на этом этапе, скорее всего встряну на глушняк, хотя...
ведь может быть ситуация, когда удаляется авто (последняя белая), то нужно вычеркивать белый цвет из справочника. можно оставить "на будущее" с NULL-ссылками.

короче, ладно! точно знаю, что сейчас уже знаю, как можно значительно улучшить все по сравнению с 1-ой версией. Кстати, она неплохая, когда данных мало, на десятках миллионов авто система умрет)) и по памяти и по скорости...ладно, а что сделать-то, а ничего...только переписывать!

ЗЫ: по-разному делать можно, но самый эффективный вариант (особенно по памяти требуемой) самый сложный в реализации. ладно!

Добавлено 26.06.20, 10:42
и последнее!
вот, например, будет такой запрос: "получить кол-во красных машин". ОПА!
на сильноветвящихся деревьях (к чему я тяготею) это будет сделано почти моментально, а тебе придется просмотреть ВСЕ УЗЛЫ главного дерева и проверить у каждого цвет на равенство с красным. Отличие в скорости может быть в "десятки миллионов" раз...ну или в тысячи...в общем быстрее гораздо.

Цитата Black_Dragon @ 26.06.20, 09:01

std::unordered_map

Хотя я в этой теме persona non grata, но выскажусь ... ты частично не прав! Все зависит от "режима" использования! Если де-факто редкие модификации и частый поиск - следует наоборот использовать упорядоченную карту std::map (т.к. ее порядок по поиску = O(lgN)). Строго экономим на поиске. А у std::unordered_map он равен O(N). Но если модификация данных происходит значительно чаще поиска - ты на 117% прав! Тогда важнее успеть "занести" данные. И std::unordered_map будет идеален.

JoeUser
Цель была в другом: типа используй готовые наработки.

У меня раньше быль файлик , шаблон простого списка с минимум функций (кода на два экрана), кочевал из проекта в проект.
Потом в какой-то дискуссии натолкнулся на набор из std, плюнул на свой файлик....

Но тут смотря какая цель, тебе просто нужен функционал и ты используешь готовое, или хочешь поковыряться под капотом этого функционала сам.

Цитата FasterHarder @ 26.06.20, 10:36

главное дерево построено по айдишникам авто

Да, и оно же является основным хранилищем всех данных.

Если поиск идет больше 10с и там есть главный цикл, то используй OpenMP или изобретай ухищрения....

Геометрическая обработка

Скрытый текст

--- Загрузка ---
Количество прочтенных строк файла - 676537
Количество загруженных полилиний - 12094
Количество созданных линий - 124421
Затраченное время: 00:00:01.4973356
--- Создаем базу линий ---
Затраченное время: 00:00:00.1499118
--- Обработка ---
Количество обработанных полигонов - 45832
Затраченное время: 00:04:34.3432271
Общее время: 00:04:35.9934664
--- Конец ---

Тоже, но с ухищрениями

Скрытый текст

--- Загрузка ---
Количество прочтенных строк файла - 676537
Количество загруженных полилиний - 12094
Количество созданных линий - 124421
Затраченное время: 00:00:01.5067219
--- Создаем базу линий ---
Затраченное время: 00:00:00.1795199
--- Обработка ---
Количество обработанных полигонов - 45832
Затраченное время: 00:00:03.1831981
Общее время: 00:00:04.8764213
--- Конец ---

OpenMP (6C/12T)

Скрытый текст

--- Загрузка ---
Количество прочтенных строк файла - 676537
Количество загруженных полилиний - 12094
Количество созданных линий - 124421
Затраченное время: 00:00:01.6982313
--- Создаем базу линий ---
Затраченное время: 00:00:00.1680519
--- Обработка ---
Количество потоков: 12
Количество обработанных полигонов - 45832
Затраченное время: 00:00:32.8862290
Общее время: 00:00:34.7565014
--- Конец ---

Ухищрения + OpenMP

Скрытый текст

--- Загрузка ---
Количество прочтенных строк файла - 676537
Количество загруженных полилиний - 12094
Количество созданных линий - 124421
Затраченное время: 00:00:01.4844383
--- Создаем базу линий ---
Затраченное время: 00:00:00.1695467
--- Обработка ---
Количество потоков: 12
Количество обработанных полигонов - 45832
Затраченное время: 00:00:01.6181071
Общее время: 00:00:03.2770786
--- Конец ---

Цитата JoeUser @ 26.06.20, 14:24

вот, например, будет такой запрос: "получить кол-во красных машин". ОПА!
на сильноветвящихся деревьях (к чему я тяготею) это будет сделано почти моментально, а тебе придется просмотреть ВСЕ УЗЛЫ главного дерева и проверить

Я же писал, главное дерево с данными и деревья по основным поисковым запросам с ссылками на основе данные.

Black_Dragon, в твоем предыдущем сообщении - цитата не моя. Я и так знаю количество красных машин в мире!

Все, проблема решена! 1800+ строк кода, функций стало еще больше + они стали сложнее местами гораздо (где-то 450 строк взял из 1ой версии).
Все реализовал на чистейшей динамике. Все статические строковые массивы (марка и пр.) заменил на char * с выделением дин. памяти. Кол-во указателей какое-то дичайшее получилось.

Сделал тесты на 10 авто, 100, 1000, 10 000, 100 000, 1 000 000, 5 000 000, 25 000 000 (файлик текстовый весит 2.5+ Гигов). Во всех случаях поиск МГНОВЕННЫЙ. Как я понимаю, замеряем время до нахождения первого блока искомых данных (а потом они идут все последовательно, благодаря списку ссылок из узла дерева). От 5млн. комп начинает терять сознание, на 25млн. завис наглушняк (оперативку забрал всю теор.возможную) - ребут пришлось делать.

Самая тяжелая операция: загрузка данных в память. Для 1млн. длится несколько минут(даже вроде больше 10 длилось). При очистке памяти аналогично.
Производительность по сравнению с 1ой версии увеличена в +бесконечность (особенно при увеличении объема входных данных).

Если добавить балансировку главного дерева (вспомогательных бессмысленно, вроде), можно еще ускорить поиск, например (по коду, хотя на 1млн. авто поиск коду был ПОЧТИ мгновенным, правда не тестировал вырожденные случаи), но балансировать дерево даже на 1млн. авто - жесть.

Как я понимаю, ускорить импорт данных не представляется возможным. Фундаментально структуру входных файлов не изменить.
Вижу лишь единственный полуминус - данные как бы пришлось закачивать в двойном экземпляре в память (всего лишь в двойном!!). С другой стороны, ну, вот, например, марка машины "Jaguar", занимаем 7байт информации. Если заменить на целое число, то будет 4байта (или 2 байта). Благодаря указателям (char*) на каждое строковое данное было использовано минимально требуемое число памяти, не сильно превышающее числовой код (раньше была константа = 100 символам для всех строк, кроме краткого описания, там было под 500). Тут все как бы оптимально!

Кардинально программу уже менять стопудова не придется, т к:
и тай сойдет (с) - и реально сойдет!

P.S. сложно проводить тесты на больших объемах данных, нужен супермощный комп с дичайшим объемом ОЗУ...

Цитата FasterHarder @ 27.06.20, 23:32

нужен супермощный комп с дичайшим объемом ОЗУ

На мощном компе ты не оценишь быстродействие...
А сколько памяти было?
При загрузке где узкое место? Диск был загружен или проц?
На моем компе с обычного HDD 10Гб читались (в nul) 1 минуту.
Имхо, оптимизируй добавлений данных...

Цитата JoeUser @ 26.06.20, 14:24

Строго экономим на поиске. А у std::unordered_map он равен O(N).

Цитата

Constant on average, worst case linear in the size of the container.

В принципе, если не умничать и не писать хеши самому, либо не ломать специально хеш-функцию специально подобранными данными (на реальных данных это 100% не произойдёт), то можно надеяться на average.

Цитата OpenGL @ 28.06.20, 18:42

Constant on average, worst case linear in the size of the container.

Надеясь на лучшее - готовься к ужасному (С)

Кстати, по мап-у.
А если часто используется поиск и полный перебор по всем данным?

Сообщение отредактировано: Black_Dragon - 29.06.20, 07:50

Цитата Black_Dragon @ 29.06.20, 07:50

А если часто используется поиск и полный перебор по всем данным?

Немношко неправильный вопрос!

"часто используется поиск" - это вывоз поисковой процедуры
"полный перебор" - это вызов поисковой процедуры в условиях неупорядоченных данных

Если ты хотел спросить "а если часто используется поиск" (гораздо чаще операций вставки) - то ответ прост: используй упорядоченные мапы. Хотя.. я об этом уже писал чуть ранее. Ну а если желаешь "полный перебор" - понятное дело, неупорядоченные мапы.

Цитата JoeUser @ 29.06.20, 15:06

"полный перебор" - это вызов поисковой процедуры в условиях неупорядоченных данных

for (auto &itmain : mainBase)

Цитата Black_Dragon @ 29.06.20, 16:06

or (auto &itmain : mainBase)

Ну если > c++11, то где-то так.

Цитата Black_Dragon @ 29.06.20, 07:50

А если часто используется поиск и полный перебор по всем данным?

По идее проще всего написать и проверить. Зависеть может много от чего - от адекватности хеш-функции, от частоты коллизий, от фазы Луны, в конце-концов

Вообщем провел тест, тестовый набор 7,5 тыс записей

namespace MapBench
{
    TEST_CLASS(TestMap)
    {
    public:
        size_t test_find_count = 400000000;
        size_t test_all_count = 1000000;
        size_t test_arr = 8;
        CMacAddr arrmac[8] = { CMacAddr(0x0036A9F36550), CMacAddr(0x002A23B31D00), CMacAddr(0x0025D2D1E778), CMacAddr(0x5661562BD93C), CMacAddr(0x40758E924A3C), CMacAddr(0xC1F0F3FD8CA0), CMacAddr(0x0B629D565000), CMacAddr(0xAE8FDD0C5E4C) };
        TEST_CLASS_INITIALIZE(ClassInitialize)
        {
            SNMPManager::getManager()->startup();
            if (SQLOpen())
            {
                int size_bd = SQLReadBase();
                Assert::IsTrue(size_bd > 0);
                SQLClose();
            }
            else Assert::Fail(L"Don't Open");
        }
        TEST_CLASS_CLEANUP(ClassCleanup)
        {
            SNMPManager::getManager()->cleanUp();
        }
        TEST_METHOD(FindMap)
        {
            for (size_t iter = 0; iter < test_find_count; ++iter)
            {
                for (size_t ind = 0; ind < test_arr; ++ind)
                {
                    auto it = mainBase.find(arrmac[ind]);
                    Assert::IsTrue(it != mainBase.end());
                }
            }
        }
        TEST_METHOD(AllMap)
        {
            for (size_t iter = 0; iter < test_all_count; ++iter)
            {
                for (auto &it : mainBase)
                {
                }
            }
            Assert::IsTrue(true);
        }
    };
}

#define ETHER_ADDR_LEN 6
typedef u_char macaddr[ETHER_ADDR_LEN];
union unmacaddr
{
    macaddr m_mac; // mac адрес
    UINT64  m_64mac = 0;
    struct
    {
        UINT32 m_l;
        UINT32 m_h;
    } m_32x2;
 
    unmacaddr() {}
    explicit unmacaddr(UINT64 mac) : m_64mac(mac) {}
};
class CMacAddr
{
public:
    unmacaddr u;
 
public:
    // Создание нулевого МАК-адреса
    CMacAddr() {}
    CMacAddr(const macaddr ptr) { for (size_t i = 0; i < ETHER_ADDR_LEN; ++i) u.m_mac[i] = ptr[i]; }
    CMacAddr(const CMacAddr &obj) { u = obj.u; }
    explicit CMacAddr(UINT64 obj) : u(obj) {};
    // Создание МАК-адреса из текстовой строки, true - успешно
    static bool ConvertFromCStr(const CStr &txt, CMacAddr *ma);
    //CMacAddr(const CStr &txt);
    CStr Str() const;
    CWideStr WStr() const;
    bool IsZero() const { return (u.m_64mac == 0); }
    bool IsBroadcast() const { return (u.m_64mac == 0xFFFFFFFFFFFF); }
    CMacAddr &operator=(const UINT64 &obj) { u.m_64mac = obj; return *this; }
    bool operator<(const CMacAddr &obj) const { return (u.m_64mac < obj.u.m_64mac); }
    bool operator>(const CMacAddr &obj) const { return (u.m_64mac > obj.u.m_64mac); }
    bool operator==(const CMacAddr &obj) const { return (u.m_64mac == obj.u.m_64mac); }
    bool operator!=(const CMacAddr &obj) const { return (u.m_64mac != obj.u.m_64mac); }
};
 
namespace std
{
    template <> struct hash<CMacAddr>
    {
        using argument_type = CMacAddr;
        using result_type = size_t;
        result_type operator()(const argument_type &key) const
        {
            return static_cast<result_type>(key.u.m_32x2.m_l + key.u.m_32x2.m_h);
        }
    };
};
typedef std::unordered_map<CMacAddr, PDevice> mapMacDev;
mapMacDev   mainBase;

std::map

Прикреплённая картинка

std::unordered_map

Прикреплённая картинка

Сообщение отредактировано: Black_Dragon - 30.06.20, 15:03