На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (7) [1] 2 3 ...  6 7 все  ( Перейти к последнему сообщению )  
> Выбор типа дерева (структура данных) для хранения данных в БД, БД "Гараж из автомобилей"
Всем хай! Сходу к делу!

Столкнулся с такой задачей.
Есть сущность "Автомобиль", описываемый следующими полями:
  • Марка
  • Страна-производитель
  • Год выпуска
  • Максимальная скорость
  • Стоимость
  • Краткое описание
Допустимо иметь всякие разные служебные поля (аля первичные ключи для данных). Например, можно добавить ИД_двигателя для каждого авто, чтобы как-то отличать дубликатные варианты.

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

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

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

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

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

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

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

спс. за внимание
Сообщение отредактировано: FasterHarder -
I originate
You must appreciate, all the others imitate

SCOOTER "GUEST LIST"

'Pon the mic I'm the teacher!
Spread my words like a preacher!
Yiiihhaaaa!!!!

SCOOTER "WEEKEND"
Цитата FasterHarder @
Есть жесткое требование: нужно использовать структуру данных дерево

Список автомобилей в виде дерева? :blink: Это как пониматьвашу? :blink:
Мои программные ништякиhttps://majestio.info
JoeUser, ну, да, что тут такого!)
Нужно в программе задействовать древовидную структуру данных, благодаря которой происходит обработка данных (БД из авто)

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

Добавлено
Скрытый текст
Цитата JoeUser @
Список автомобилей в виде дерева?

или речь про слово "список"?)
ну, возьми синонимы: набор, перечень, множество (хотя перечень и множество тоже могут вызывать вопросы)
I originate
You must appreciate, all the others imitate

SCOOTER "GUEST LIST"

'Pon the mic I'm the teacher!
Spread my words like a preacher!
Yiiihhaaaa!!!!

SCOOTER "WEEKEND"
FasterHarder, если ты реально хочешь пользоваться всеми плюшками SQL реляционной базы данных - проектируй наборы и отношения согласно стандарту SQL. А это - плоские таблицы и их отношения. И "дерево" из них можешь построить. Ну а если nosql движки - тогда обозначь, что собираешься юзать.
Мои программные ништякиhttps://majestio.info
Хрень какая-то. Ну заведи таблицу со всеми индексами, в чём проблема? Конкретный тип индекса выбирай такой, который строит деревья. Зачем что-то самому для этого писать?
Подпись была включена в связи с окончанием срока наказания
OpenGL, плюсую.

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

Нет такого типа индекса :) Индексы существуют для быстрого упорядочивания по полю (или группе полей). А вот "построение дерева" - это уже прерогатива запросов. Как "запросишь"- то и получишь.
Мои программные ништякиhttps://majestio.info
Цитата OpenGL @
Хрень какая-то. Ну заведи таблицу со всеми индексами, в чём проблема? Конкретный тип индекса выбирай такой, который строит деревья. Зачем что-то самому для этого писать?

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

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

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

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

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

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

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

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

Если бы я узнал, какое дерево наиболее эффективно в данном случае, то смог бы с ним поразбираться)
I originate
You must appreciate, all the others imitate

SCOOTER "GUEST LIST"

'Pon the mic I'm the teacher!
Spread my words like a preacher!
Yiiihhaaaa!!!!

SCOOTER "WEEKEND"
Цитата FasterHarder @
Есть на выбор любая древовидная структура данных.

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

Добавлено
Цитата JoeUser @
Нет такого типа индекса
А это что? :)
Цитата
PostgreSQL поддерживает несколько типов индексов: B-дерево, хеш, GiST, SP-GiST, GIN и BRIN.

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

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

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

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


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

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

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

ДЕРЕВЬЯ!!! есть такая динамическая структура данных мощнейшая...
I originate
You must appreciate, all the others imitate

SCOOTER "GUEST LIST"

'Pon the mic I'm the teacher!
Spread my words like a preacher!
Yiiihhaaaa!!!!

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

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

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

Заметь - это реализация "одна из". Тк. вторая таблица может содержать не отношения "чел-потомок", а, допустим "чел-родитель". И тогда пересчет будет совсем иным.
Мои программные ништякиhttps://majestio.info
JoeUser вот чего ты мне затираешь? умным хочешь показаться? так лучше ответь на поставленный вопрос!)
есть четко формализованная задача! куда вам еще больше разжевывать? ну, куда? машинку нарисовать в пэинте только остается для визуализации...так все равно и это НЕ поможет)

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

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

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

ЗЫ: вангую, ответ я НЕ получу, как и много раз раньше...все это проходилось и повторяется многократно...хотя если знать, можно за минуту ответить...если знать...
I originate
You must appreciate, all the others imitate

SCOOTER "GUEST LIST"

'Pon the mic I'm the teacher!
Spread my words like a preacher!
Yiiihhaaaa!!!!

SCOOTER "WEEKEND"
И что характерно, данный мной вполне чёткий ответ с указанием типа дерева ТС проигнорировал :D
Подпись была включена в связи с окончанием срока наказания
    Цитата OpenGL @
    данный мной вполне чёткий ответ с указанием типа дерева ТС проигнорировал

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

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

    короче: я думаю, что все сведется к построению семейства бинарных деревьев в соот-вии с полями сущности авто. Непонятно? да плевать))
    I originate
    You must appreciate, all the others imitate

    SCOOTER "GUEST LIST"

    'Pon the mic I'm the teacher!
    Spread my words like a preacher!
    Yiiihhaaaa!!!!

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

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

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

    Да, как-то так.
    Подпись была включена в связи с окончанием срока наказания
    1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
    0 пользователей:
    Страницы: (7) [1] 2 3 ...  6 7 все


    Рейтинг@Mail.ru
    [ Script Execution time: 0,1376 ]   [ 19 queries used ]   [ Generated: 5.07.20, 04:50 GMT ]