Здравствуйте, Vain, Вы писали: V>Речь идёт о том, что корень не обязательно в дереве хранить. Пользователь его может положить рядом с деревом, будет тот же эффект.
Фантастическая картина.
V>Вы пример привели, где один set на дерево и поиск во всём дереве происходит. А у меня set в каждой ноде.
Очень уж у вас нечёткое описание получилось.
V>Ну и будет сложность поиска O(M) (все вершины), у меня же сложность поиска O(log(M)*L) (log(среднее кол-во детей в ноде)*высота дерева).
O(M*L) вообще-то, где M -- количество детей на узел, L -- глубина дерева (L=log(N)/log(M)). Иногда, между прочим, O(M) меньше O(log(M)).
Но если у вас детей в узле сотни и тысячи -- да, дополнительный set имеет смысл. Ну так просто будет:
Здравствуйте, gegMOPO4, Вы писали:
V>>Речь идёт о том, что корень не обязательно в дереве хранить. Пользователь его может положить рядом с деревом, будет тот же эффект. MOP>Фантастическая картина.
Обычная нормальная реализации, ничего фантастичного.
V>>Вы пример привели, где один set на дерево и поиск во всём дереве происходит. А у меня set в каждой ноде. MOP>Очень уж у вас нечёткое описание получилось.
Ну это обычная реализация дерева — через уже имеющиеся контейнеры.
V>>Ну и будет сложность поиска O(M) (все вершины), у меня же сложность поиска O(log(M)*L) (log(среднее кол-во детей в ноде)*высота дерева). MOP>O(M*L) вообще-то, где M -- количество детей на узел, L -- глубина дерева (L=log(N)/log(M)). Иногда, между прочим, O(M) меньше O(log(M)).
Вы меня не путайте, в моей реализации как раз log будет, в вашей не будет, т.к. в вашей реализации небыло никаких std::set внутри ноды, только итераторы:
Поэтому определить где начинается и где заканчивается дерево можно только за O(N), где N — все вершины поддерева.
MOP>Но если у вас детей в узле сотни и тысячи -- да, дополнительный set имеет смысл. Ну так просто будет: MOP>
Здравствуйте, Vain, Вы писали: V>Вы меня не путайте, в моей реализации как раз log будет, в вашей не будет, т.к. в вашей реализации небыло никаких std::set внутри ноды, только итераторы:
Ну кто ж знал, что вам логарифм именно здесь нулжен. Яснее описывайте свою задачу.
V>Поэтому определить где начинается и где заканчивается дерево можно только за O(N), где N — все вершины поддерева.
Что значит, где начинается и где заканчивается? Начинается в корне, заканчивается на глубине O(log(N)).
V>Про это и речь, что хочется написать контейнер без лишнего и без г-на.
За использование ненадлежащих инструментов приходится платить.
В первом варианте, с самодельными односвязными списками, расходы на узел 5 указателей + двойной размер узла std::set (ещё около 10 указателей в сумме). Используя собственную реализацию дерева вместо std::set можно сократить оверхед на него вдвое. Итого 10 максимум. Использую специальную хеш-таблицу можно ещё сократить. И от поля last_child можно избавиться небольшой ценой.
Во втором варианте, с std::list, имеем в лучшем случае 10 указателей + оверхед на std::set -- в сумме 20. Минимум вдвое дороже. Не говоря уж о потере производительности на лишней косвенности некоторых операций.
Re[16]: STL: Сравнение валидных итераторов на разные контейн
Здравствуйте, gegMOPO4, Вы писали:
V>>Вы меня не путайте, в моей реализации как раз log будет, в вашей не будет, т.к. в вашей реализации небыло никаких std::set внутри ноды, только итераторы: MOP>Ну кто ж знал, что вам логарифм именно здесь нулжен. Яснее описывайте свою задачу.
Так я и указал
MOP>std::set и так реализован обычно через дерево, вы навернули ещё одно поверх? И зачем тогда set?
Чтобы find был по детям за O(long(n)).
V>>Поэтому определить где начинается и где заканчивается дерево можно только за O(N), где N — все вершины поддерева. MOP>Что значит, где начинается и где заканчивается? Начинается в корне, заканчивается на глубине O(log(N)).
Ох, ну у вас один std::set, как вы собираетесь от него кусок отрезать не за O(N)?
V>>Про это и речь, что хочется написать контейнер без лишнего и без г-на. MOP>За использование ненадлежащих инструментов приходится платить.
Каких ещё ненадлежащих, вы про STL чтоли?
MOP>В первом варианте, с самодельными односвязными списками, расходы на узел 5 указателей + двойной размер узла std::set (ещё около 10 указателей в сумме). Используя собственную реализацию дерева вместо std::set можно сократить оверхед на него вдвое. Итого 10 максимум. Использую специальную хеш-таблицу можно ещё сократить. И от поля last_child можно избавиться небольшой ценой.
Этого можно добиться и с использованием STL, только оно агрегирование не держит, а так с лишней косвенностью — можно.
MOP>Во втором варианте, с std::list, имеем в лучшем случае 10 указателей + оверхед на std::set -- в сумме 20. Минимум вдвое дороже.
Во втором варианте, также, кусок дерева придётся отрезать за O(N):
struct Tree {
set<Node>::iterator root;
list<set<Node>::iterator> tree_list;
};
Т.к. придётся обойти tree_list и найти в нём начало поддерева и конец. Иначе Node должен back iterator содержать на ваш tree_list, что уже оверхед.
MOP>Не говоря уж о потере производительности на лишней косвенности некоторых операций.
Потеря производительности если и будет, то не на косвенности, а на излишнем выделении/высвобождении памяти как для std::list'а, в случае если елементов десятки тысяч и дерево постоянно создаётся/уничтожается.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[17]: STL: Сравнение валидных итераторов на разные контейн
Ну вы же не сказали сразу, что у вас set в каждом узле.
V>Ох, ну у вас один std::set, как вы собираетесь от него кусок отрезать не за O(N)?
Никак. Не ставьте невыполнимых задач.
MOP>>За использование ненадлежащих инструментов приходится платить. V>Каких ещё ненадлежащих, вы про STL чтоли?
Я про стандартные контейнеры. Не не предусмотрена в них такая частность, как использование одного узла несколькими ортогональным спискам одновременно. Под специальные задачи -- специальные средства.
MOP>>В первом варианте, с самодельными односвязными списками, расходы на узел 5 указателей + двойной размер узла std::set (ещё около 10 указателей в сумме). Используя собственную реализацию дерева вместо std::set можно сократить оверхед на него вдвое. Итого 10 максимум. Использую специальную хеш-таблицу можно ещё сократить. И от поля last_child можно избавиться небольшой ценой. V>Этого можно добиться и с использованием STL, только оно агрегирование не держит, а так с лишней косвенностью — можно.
Как? С STL вы в любом случае получаете для этой специальной задачи вдвое больше накладные расходы по памяти.
MOP>>Во втором варианте, с std::list, имеем в лучшем случае 10 указателей + оверхед на std::set -- в сумме 20. Минимум вдвое дороже. V>Во втором варианте, также, кусок дерева придётся отрезать за O(N): V>
V>Т.к. придётся обойти tree_list и найти в нём начало поддерева и конец. Иначе Node должен back iterator содержать на ваш tree_list, что уже оверхед.
Ну что же вы хотели? Если сквозной список в порядке вставки, то в любом случае O(N) для обработки всех элементов. Быстрее никак невозможно.
MOP>>Не говоря уж о потере производительности на лишней косвенности некоторых операций. V>Потеря производительности если и будет, то не на косвенности, а на излишнем выделении/высвобождении памяти как для std::list'а, в случае если елементов десятки тысяч и дерево постоянно создаётся/уничтожается.
Ну тем более. Два узла списка на каждый узел дерева.
Re[18]: STL: Сравнение валидных итераторов на разные контейн
: MOP>Ну вы же не сказали сразу, что у вас set в каждом узле.
Это было понятно из фразы "find был по детям за O(log(n))".
V>>Ох, ну у вас один std::set, как вы собираетесь от него кусок отрезать не за O(N)? MOP>Никак. Не ставьте невыполнимых задач.
Неправда, это вполне выполнимая задача.
MOP>>>За использование ненадлежащих инструментов приходится платить. V>>Каких ещё ненадлежащих, вы про STL чтоли? MOP>Я про стандартные контейнеры. Не не предусмотрена в них такая частность, как использование одного узла несколькими ортогональным спискам одновременно. Под специальные задачи -- специальные средства.
Ну, раз спец средства будут позволять сделать то, что делает STL, то зачем тогда STL?
MOP>>>В первом варианте, с самодельными односвязными списками, расходы на узел 5 указателей + двойной размер узла std::set (ещё около 10 указателей в сумме). Используя собственную реализацию дерева вместо std::set можно сократить оверхед на него вдвое. Итого 10 максимум. Использую специальную хеш-таблицу можно ещё сократить. И от поля last_child можно избавиться небольшой ценой. V>>Этого можно добиться и с использованием STL, только оно агрегирование не держит, а так с лишней косвенностью — можно. MOP>Как? С STL вы в любом случае получаете для этой специальной задачи вдвое больше накладные расходы по памяти.
Почему, это зависит от sizeof(T) вообще-то. К тому же такая реализация переиспользует уже написанный код — STL контейнеры и проще, потому-что использует уже известные контейнеры простым способом.
MOP>>>Во втором варианте, с std::list, имеем в лучшем случае 10 указателей + оверхед на std::set -- в сумме 20. Минимум вдвое дороже. V>>Во втором варианте, также, кусок дерева придётся отрезать за O(N): V>>
V>>Т.к. придётся обойти tree_list и найти в нём начало поддерева и конец. Иначе Node должен back iterator содержать на ваш tree_list, что уже оверхед. MOP>Ну что же вы хотели? Если сквозной список в порядке вставки, то в любом случае O(N) для обработки всех элементов. Быстрее никак невозможно.
Потому-что не надо, во-первых, хранить все ноды дерева в одном списке, для дерева это оверхед в прямом виде. Во-вторых, базовая реализация дерева не должна требовать объединять все ноды в цепочку, там свои связи и обход всего дерева может делатся как минимум двумя способами, что у вас не отражено вообще. В-третьих, ноду можно хранить по указателю (как сделано, к примеру, в TCL) и остыковать поддерево можно будет за O(1).
MOP>>>Не говоря уж о потере производительности на лишней косвенности некоторых операций. V>>Потеря производительности если и будет, то не на косвенности, а на излишнем выделении/высвобождении памяти как для std::list'а, в случае если елементов десятки тысяч и дерево постоянно создаётся/уничтожается. MOP>Ну тем более. Два узла списка на каждый узел дерева.
Сложность всё-равно O(N), это ничего не меняет.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[19]: STL: Сравнение валидных итераторов на разные контейн
Здравствуйте, Vain, Вы писали: V>Здравствуйте, gegMOPO4, Вы писали: MOP>>Ну вы же не сказали сразу, что у вас set в каждом узле. V>Это было понятно из фразы "find был по детям за O(log(n))".
Ну, я так понял, что раз у вас один set зачем-то, то и искать собираетесь по всем детям. Сказали бы сразу ясно, что у вас за структуры данных.
V>>>Ох, ну у вас один std::set, как вы собираетесь от него кусок отрезать не за O(N)? MOP>>Никак. Не ставьте невыполнимых задач. V>Неправда, это вполне выполнимая задача.
std::set не предоставляет такого интерфейса.
MOP>>Я про стандартные контейнеры. Не не предусмотрена в них такая частность, как использование одного узла несколькими ортогональным спискам одновременно. Под специальные задачи -- специальные средства. V>Ну, раз спец средства будут позволять сделать то, что делает STL, то зачем тогда STL?
Для быстрого и удобного решения стандартных задач.
MOP>>>>В первом варианте, с самодельными односвязными списками, расходы на узел 5 указателей + двойной размер узла std::set (ещё около 10 указателей в сумме). Используя собственную реализацию дерева вместо std::set можно сократить оверхед на него вдвое. Итого 10 максимум. Использую специальную хеш-таблицу можно ещё сократить. И от поля last_child можно избавиться небольшой ценой. V>>>Этого можно добиться и с использованием STL, только оно агрегирование не держит, а так с лишней косвенностью — можно. MOP>>Как? С STL вы в любом случае получаете для этой специальной задачи вдвое больше накладные расходы по памяти. V>Почему, это зависит от sizeof(T) вообще-то.
вдвое больше накладные расходы по памяти
V>К тому же такая реализация переиспользует уже написанный код — STL контейнеры и проще, потому-что использует уже известные контейнеры простым способом.
Односвязный список -- очень сложный код, да. Обвязка что вокруг STL, что вокруг своего специализированного списка -- одинаковой сложности. Пожалуй, во втором случае код даже будет короче и яснее. И уж в любом случае проще модифицируется.
MOP>>Ну что же вы хотели? Если сквозной список в порядке вставки, то в любом случае O(N) для обработки всех элементов. Быстрее никак невозможно. V>Потому-что не надо, во-первых, хранить все ноды дерева в одном списке, для дерева это оверхед в прямом виде.
Вы же сами говорили, что нужен ещё список, связывающий все узлы дерева для обхода в порядке времени вставки. Какую задачу поставили, такой решение и получили. Вы уж определитесь, крестик вам, или голая попа.
V>Во-вторых, базовая реализация дерева не должна требовать объединять все ноды в цепочку, там свои связи и обход всего дерева может делатся как минимум двумя способами, что у вас не отражено вообще.
Вообще-то, структура предполагает итерацию по крайней мере тремя способами. По общему списку в порядке времени вставки и обход вглубь по детям используя set или по времени вставки внутри родителя.
V>В-третьих, ноду можно хранить по указателю (как сделано, к примеру, в TCL) и остыковать поддерево можно будет за O(1).
Вообще-то, в любой разумной реализации дерева стоимость отстыковки поддерева O(1). Коли уж мы нашли узел. И если не нужна перебалансировка, разумеется.
V>>>Потеря производительности если и будет, то не на косвенности, а на излишнем выделении/высвобождении памяти как для std::list'а, в случае если елементов десятки тысяч и дерево постоянно создаётся/уничтожается. MOP>>Ну тем более. Два узла списка на каждый узел дерева. V>Сложность всё-равно O(N), это ничего не меняет.
Сложность поиска O(log(N)), сложность вставки/удаления из родителького set-а O(log(M)), сложность коррекции указателей для вставки O(1), для удаления O(M) (для односвязных списков, для двусвязных O(1), но с большим множителем).
Re[20]: STL: Сравнение валидных итераторов на разные контейн
Здравствуйте, gegMOPO4, Вы писали:
MOP>Здравствуйте, Vain, Вы писали: V>>Здравствуйте, gegMOPO4, Вы писали: MOP>>>Ну вы же не сказали сразу, что у вас set в каждом узле. V>>Это было понятно из фразы "find был по детям за O(log(n))". MOP>Ну, я так понял, что раз у вас один set зачем-то, то и искать собираетесь по всем детям. Сказали бы сразу ясно, что у вас за структуры данных.
Я ничего не говорил про один std::set. Очевидно, что у каждой ноды дети "свои", поэтому непонятно откуда вы про один std::set подумали.
V>>>>Ох, ну у вас один std::set, как вы собираетесь от него кусок отрезать не за O(N)? MOP>>>Никак. Не ставьте невыполнимых задач. V>>Неправда, это вполне выполнимая задача. MOP>std::set не предоставляет такого интерфейса.
Не предоставляет, но задача не становится от этого невыполнимой.
MOP>>>Я про стандартные контейнеры. Не не предусмотрена в них такая частность, как использование одного узла несколькими ортогональным спискам одновременно. Под специальные задачи -- специальные средства. V>>Ну, раз спец средства будут позволять сделать то, что делает STL, то зачем тогда STL? MOP>Для быстрого и удобного решения стандартных задач.
А спец средства для медленного и неудобного?
MOP>>Как? С STL вы в любом случае получаете для этой специальной задачи вдвое больше накладные расходы по памяти. V>Почему, это зависит от sizeof(T) вообще-то. MOP>
MOP>вдвое больше накладные расходы по памяти
В двое больше по сравнению с чем? По сравнению с полезным грузом — не вдвое.
V>>К тому же такая реализация переиспользует уже написанный код — STL контейнеры и проще, потому-что использует уже известные контейнеры простым способом. MOP>Односвязный список -- очень сложный код, да. Обвязка что вокруг STL, что вокруг своего специализированного списка -- одинаковой сложности. Пожалуй, во втором случае код даже будет короче и яснее. И уж в любом случае проще модифицируется.
Это ещё вопрос, что проще поддерживать, ноду с кастомными указателями или готовые самодостаточные контейнеры, которые при возможности можно просто подменить.
MOP>>>Ну что же вы хотели? Если сквозной список в порядке вставки, то в любом случае O(N) для обработки всех элементов. Быстрее никак невозможно. V>>Потому-что не надо, во-первых, хранить все ноды дерева в одном списке, для дерева это оверхед в прямом виде. MOP>Вы же сами говорили, что нужен ещё список, связывающий все узлы дерева для обхода в порядке времени вставки. Какую задачу поставили, такой решение и получили. Вы уж определитесь, крестик вам, или голая попа.
Уж чего не говорил — того не говорил:
добавил в контейнер отдельно std::list для пометки листьев и std::list в каждую ноду, чтобы сохранять порядок вставки
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
