Комментарии 26
Увидев название публикации, обрадовался, думал — сейчас зайду и пополню сокровищницу своих знаний об алгоритмах.
Абзацы будут отделены друг от друга пустой строкой, текст проиллюстрирован парой-тройкой «многомерно-древообразных» разноцветных диаграммок, смысловые блоки разбиты с помощью подзаголовков и в качестве бонуса автор ключевые слова выделит жирным шрифтом. Будет, где взгляду зацепиться.
В общем, по тексту статьи можно будет бегло (но результативно) пробежаться «по диагонали», занести в закладки и вернуться к теме многомерных деревьев через час-два, дамы вдумчиво впитать в себя полезный материал. В предвкушении профита, захожу, а тут — шиш. Пичалька.
Абзацы будут отделены друг от друга пустой строкой, текст проиллюстрирован парой-тройкой «многомерно-древообразных» разноцветных диаграммок, смысловые блоки разбиты с помощью подзаголовков и в качестве бонуса автор ключевые слова выделит жирным шрифтом. Будет, где взгляду зацепиться.
В общем, по тексту статьи можно будет бегло (но результативно) пробежаться «по диагонали», занести в закладки и вернуться к теме многомерных деревьев через час-два, дамы вдумчиво впитать в себя полезный материал. В предвкушении профита, захожу, а тут — шиш. Пичалька.
Михаил, вас уже несколько раз коллеги на форуме просили, выложите в отрытый доступ ваши наработки. И тогда возможно найдутся желающие посмотреть и оценить ваши труды. Раз вы не выкладываете в открытый доступ, полагаю вы планируете на этом заработать, в таком случае, скорее всего вам будет сложно, найти помощников в этом нелегком деле.
Ну во первых не просили.
Что вы имеете в виду говоря о наработках? MSH не готов, находится в разработке. База как то сделана и сыро отлажена. Нужно тестирование. Я готов ее предоставить тому кто захочет это сделать. Куда я ее мог выложить. Собираюсь я на этом зарабатывать или нет я еще не знаю. До этого еще далеко. Заработать можно только на готовом продукте с развитой инфраструктурой языка. А до этого еще ой как далеко. Вопрос о заработке пока еще не стоит вообще. А просил помочь я только тебя. Рассчитываю что для тестирования базы кто нибудь найдется. Надежда умирает последней. Если захочешь помочь, пиши вышлю проект для тестирования и описание API обращений к базе данных.
Что вы имеете в виду говоря о наработках? MSH не готов, находится в разработке. База как то сделана и сыро отлажена. Нужно тестирование. Я готов ее предоставить тому кто захочет это сделать. Куда я ее мог выложить. Собираюсь я на этом зарабатывать или нет я еще не знаю. До этого еще далеко. Заработать можно только на готовом продукте с развитой инфраструктурой языка. А до этого еще ой как далеко. Вопрос о заработке пока еще не стоит вообще. А просил помочь я только тебя. Рассчитываю что для тестирования базы кто нибудь найдется. Надежда умирает последней. Если захочешь помочь, пиши вышлю проект для тестирования и описание API обращений к базе данных.
Нет уж, давайте разберемся.
Нет, на дереве не моделируется граф.
Что такое «ветвь»? Чем она отличается от стандартного ребра (из которых в норме состоит граф)?
Вы хотите сказать, что у вас между вершинами в дереве могут быть ребра, отличные от условных «вверх-вниз»? Поздравляю вас, это больше не дерево, а обычный граф (скорее всего, направленный).
Это [дерево] наиболее общая организация данных и на ней легко моделируются все остальные структуры данных.
Нет, на дереве не моделируется граф.
Это такое дерево каждый узел которого кроме данных и прямых потомков содержит еще N — ветвей.
Что такое «ветвь»? Чем она отличается от стандартного ребра (из которых в норме состоит граф)?
Такая структура необходима, когда основные ветви отражают взаимосвязь сущностей, а сами сущности являются иерархическими объектами.
Вы хотите сказать, что у вас между вершинами в дереве могут быть ребра, отличные от условных «вверх-вниз»? Поздравляю вас, это больше не дерево, а обычный граф (скорее всего, направленный).
Дерево уже есть граф.
|Нет, на дереве не моделируется граф.
Если в узел писать ссылки на другие узлы, то вполне моделируется.
|Что такое «ветвь»? Чем она отличается от стандартного ребра (из которых в норме состоит граф)
Ветвь это не ребро а поддерево узлов. Из каждого узла выходит N- поддеревьев.
|Вы хотите сказать, что у вас между вершинами в дереве могут быть ребра, отличные от условных «вверх-вниз»? Поздравляю вас, это больше не дерево, а обычный граф (скорее всего, направленный).
Ребра всегда имеют связь предок-потомки. Для меня не важно является ли эта структура графом или нет, а вот иерархическим деревом она является.
|Нет, на дереве не моделируется граф.
Если в узел писать ссылки на другие узлы, то вполне моделируется.
|Что такое «ветвь»? Чем она отличается от стандартного ребра (из которых в норме состоит граф)
Ветвь это не ребро а поддерево узлов. Из каждого узла выходит N- поддеревьев.
|Вы хотите сказать, что у вас между вершинами в дереве могут быть ребра, отличные от условных «вверх-вниз»? Поздравляю вас, это больше не дерево, а обычный граф (скорее всего, направленный).
Ребра всегда имеют связь предок-потомки. Для меня не важно является ли эта структура графом или нет, а вот иерархическим деревом она является.
Дерево уже есть граф.
Дерево — это частный случай графа.
Если в узел писать ссылки на другие узлы, то вполне моделируется.
… а если в массив писать ссылки вверх и вниз, то им вполне «моделируется» дерево. Только это не модель, это реализация.
Ветвь это не ребро а поддерево узлов. Из каждого узла выходит N- поддеревьев.
Тогда ваша структура в целом — это обычное дерево, в чем пойнт?
Ребра всегда имеют связь предок-потомки.
Только если это ребро в дереве.
Для меня не важно является ли эта структура графом или нет, а вот иерархическим деревом она является.
Если она является деревом, то она по определению является графом.
|… а если в массив писать ссылки вверх и вниз, то им вполне «моделируется» дерево. Только это не модель, это реализация.
Дерево можно с помощью ссылок смоделировать как угодно. Но в данном случае речь как раз и идет о конкретной реализации структуры данных необходимой для конкретного языка MSH.
|Тогда ваша структура в целом — это обычное дерево, в чем пойнт?
Именно так. А прикол в обработке такого дерева. При работе со связями объекта, мне не нужны свойства объекта. Это разные сущности и их обработка разделена на уровне структуры данных. Обращение к структуре связных объектов отделено от обращения к свойствам объекта.
Дерево можно с помощью ссылок смоделировать как угодно. Но в данном случае речь как раз и идет о конкретной реализации структуры данных необходимой для конкретного языка MSH.
|Тогда ваша структура в целом — это обычное дерево, в чем пойнт?
Именно так. А прикол в обработке такого дерева. При работе со связями объекта, мне не нужны свойства объекта. Это разные сущности и их обработка разделена на уровне структуры данных. Обращение к структуре связных объектов отделено от обращения к свойствам объекта.
Вот только никакого «расширения структуры данных» или «многомерного дерева» вы не придумали или не показали. То, о чем вы пишете — самое обычное дерево (если вы, конечно, не ввели в нем циклы). А критерии обхода — дело совершенно пятнадцатое.
|А критерии обхода — дело совершенно пятнадцатое
В разработке языка это имеет первостепенное значение. Я не мог построить язык пока не догадался как разделить в одном дереве разные сущности. И это не пятнадцатое дело эта же проблема стоит и в других случаях о которых я писал в статье. В программировании обработка данных является основой алгоритма и от устройства данных зависит эффективность и надежность программ.
В разработке языка это имеет первостепенное значение. Я не мог построить язык пока не догадался как разделить в одном дереве разные сущности. И это не пятнадцатое дело эта же проблема стоит и в других случаях о которых я писал в статье. В программировании обработка данных является основой алгоритма и от устройства данных зависит эффективность и надежность программ.
«Устройство данных» у вас — обычное дерево. Никаких «многомерных» деревьев не существует, потому что у дерева вообще нет каких-либо координат, потому нет и многомерности.
Чем ваше дерево отличается от обычного, описанного во всех учебниках?
Какая именно проблема?
Чем ваше дерево отличается от обычного, описанного во всех учебниках?
эта же проблема стоит и в других случаях о которых я писал в статье
Какая именно проблема?
Совсем недавно я пытался разобраться в структуре 2-3-кучи, так там автор использовал именно многомерные деревья. Дерево размерности N у него — массив деревьев размерности N-1 (организованный, как список), и в итоге каждый узел N-мерного дерева содержит и ссылку на деревья-сёстры той же размерности (с которыми он вместе составляет N+1-мерное дерево), и список детей меньших размерностей (точнее, сестёр самого себя, интерпретируемого, как дерево меньшей размерности). Хранить структуру как обычное N-уровневое дерево там нельзя, поскольку нужен быстрый доступ к «угловому» элементу, в итоге получается что-то совершенно страшное — главным образом, из-за того, что поддерево с индексом 0 выглядит не так, как поддеревья с ненулевыми индексами. Но дерево действительно N-мерное. С координатами и направлениями.
|«Устройство данных» у вас — обычное дерево. Никаких «многомерных» деревьев не существует, потому что у дерева вообще нет каких-либо координат, потому нет и многомерности.
У вас в голове координат может и нет. А у меня в реализации очень даже есть. В данном случае у меня построено 2-х мерное дерево. В каждой вершине 2 координаты в которых находятся потомки данного узла.
|Чем ваше дерево отличается от обычного, описанного во всех учебниках?
Отличается структурой узла.
У вас в голове координат может и нет. А у меня в реализации очень даже есть. В данном случае у меня построено 2-х мерное дерево. В каждой вершине 2 координаты в которых находятся потомки данного узла.
|Чем ваше дерево отличается от обычного, описанного во всех учебниках?
Отличается структурой узла.
В каждой вершине 2 координаты в которых находятся потомки данного узла.
А можете пояснить рисунком?
В каждой вершине 2 координаты в которых находятся потомки данного узла.
… и чем это отличается от «обычного» дерева с помеченными ребрами? (а все это вместе — частный случай графоориентированной БД)
Даже, собственно, помеченные ребра не нужны, можно сразу вершины размечать (поскольку это дерево, ребро+вершину можно схлопнуть до ссылки на вершину).
Так ведь разметка вершин и обсуждается в следующем комментарии (про типы узлов).
Тогда это обычное дерево, про что я с начала и говорил.
Я так понял, что автору эта идея не нравится. И могу согласиться: если у нас есть ровно два типа — узел дерева и свойство, то свойства неплохо сгруппировать в отдельные списки, привязанные к узлу. Уйдёт проблема динамического определения типов, прохода по списку в поисках того, что нужно (только детей или только свойств) — ведь перебирать детей и свойства вперемешку приходится очень редко.
Вот только называть это двумерным деревом (и вообще заострять на этой структуре внимание) что-то не хочется. Действительно, обычное дерево, в узлах или листьях которого лежат объекты+их свойства.
Вот только называть это двумерным деревом (и вообще заострять на этой структуре внимание) что-то не хочется. Действительно, обычное дерево, в узлах или листьях которого лежат объекты+их свойства.
Мне это дерево не кажется двумерным. Если у «свойств» нет своих потомков, образующих поддеревья, то оно просто двуслойное — есть слой дерева объектов, и из каждого объекта ссылка во второй слой, где лежат свойства. Это если свойства нельзя загнать внутрь объектов.
Если же свойства могут иметь потомков, которые могли бы быть как свойствами, так и объектами, то получилось бы дерево с размеченными рёбрами или вершинами.
Честное двумерное дерево — это не больше и не меньше, чем дерево деревьев. Например, его можно использовать, когда объект индексируется двумя ключами. Вполне нормальная структура, но, увы, ничего нового.
Если же свойства могут иметь потомков, которые могли бы быть как свойствами, так и объектами, то получилось бы дерево с размеченными рёбрами или вершинами.
Честное двумерное дерево — это не больше и не меньше, чем дерево деревьев. Например, его можно использовать, когда объект индексируется двумя ключами. Вполне нормальная структура, но, увы, ничего нового.
Любая вершина может иметь N-поддеревьев, значит свойство может быть само объектом.
|Честное двумерное дерево — это не больше и не меньше, чем дерево деревьев. Например, его можно использовать, когда объект индексируется двумя ключами. Вполне нормальная структура, но, увы, ничего нового.
Причем тут ключи? Ключ один.
|Честное двумерное дерево — это не больше и не меньше, чем дерево деревьев. Например, его можно использовать, когда объект индексируется двумя ключами. Вполне нормальная структура, но, увы, ничего нового.
Причем тут ключи? Ключ один.
Я плохо представляю как можно декларировать данные в различных узлах дерева.
А можно в глобале метаданных описать типы а у узла указывать его тип?
|А можно в глобале метаданных описать типы а у узла указывать его тип?
Можно, но зачем? Что это даст? В MUMPS загоняют огромные массивы данных различной структуры и типов, и что на каждое значение хранить его тип? Для чего? Проверяй корректность данных на входе и будет тебе счастье, тем более что тип данных мало что говорит о его корректности.
Можно, но зачем? Что это даст? В MUMPS загоняют огромные массивы данных различной структуры и типов, и что на каждое значение хранить его тип? Для чего? Проверяй корректность данных на входе и будет тебе счастье, тем более что тип данных мало что говорит о его корректности.
Однажды я b+tree скрестил с b-tree когда в первый раз реализовывал. Такая хрень получилась.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Многомерное дерево Mtree