Почему у map::erase ( range version ) линейная сложность?
Ведь там внутри бинарное дерево поиска ... насколько я помню все реализации хранят в каждом узле ссылку на родителя — т.е. удаление всех элементов в диапазоне (first,last] сводится к нахождению общего предка ( что есть логарифмическая сложность).
Вот что говорит документация —
Complexity:
For the last version (erase(first,last)), linear in the distance between first and last.
Здравствуйте, nobody1985, Вы писали:
N>Почему у map::erase ( range version ) линейная сложность?
Скорее всего потому, что сложность балансировки дерева после удаления больше чем одного элемента равно по сложности балансировке всего дерева. Поэтому удаление реализовано поэлементно.
Здравствуйте, nobody1985, Вы писали:
N>Почему у map::erase ( range version ) линейная сложность?
N>Ведь там внутри бинарное дерево поиска ... насколько я помню все реализации хранят в каждом узле ссылку на родителя — т.е. удаление всех элементов в диапазоне (first,last] сводится к нахождению общего предка ( что есть логарифмическая сложность).
удаление range не эквивалентно удалению поддерева
берем картинку из вики: https://en.wikipedia.org/wiki/File:AVLtreef.svg
у range от 9 до 19 включительно общий предок — узел 17
но при удалении мы должны на место узла 17 поставить узел 23 из поддерева
если удалять range от 14 до 19 включительно, то нужно сохранить 9, 12 и 23
Здравствуйте, nobody1985, Вы писали:
N>что есть логарифмическая сложность
кстати, логарифм для данной операции — это слишком дорого
стандарт предлагает гораздо круче
вспомним, что map.erase(it) делается за константу, а не за логарифм
отсюда легко выводится, что удаление набора итераторов будет пропорционально кол-ву итераторов (напомню, что удаление по итератору не инвалидирует остальные итераторы)
Здравствуйте, uzhas, Вы писали:
U>Здравствуйте, nobody1985, Вы писали:
N>>что есть логарифмическая сложность
U>кстати, логарифм для данной операции — это слишком дорого
Я имел в виду логарифм от количества итераторов ( а не от общего числа элементов дерева ).
U>стандарт предлагает гораздо круче U>вспомним, что map.erase(it) делается за константу, а не за логарифм U>отсюда легко выводится, что удаление набора итераторов будет пропорционально кол-ву итераторов (напомню, что удаление по итератору не инвалидирует остальные итераторы)
То что map.erase(it) делается за константу — это понятно.
Я находился в заблуждении что map.erase(first, last) оптимизированно и выполняется быстрее чем distance(first, last) * map.erase(it)
Здравствуйте, uzhas, Вы писали:
U>Здравствуйте, nobody1985, Вы писали:
N>>Почему у map::erase ( range version ) линейная сложность?
N>>Ведь там внутри бинарное дерево поиска ... насколько я помню все реализации хранят в каждом узле ссылку на родителя — т.е. удаление всех элементов в диапазоне (first,last] сводится к нахождению общего предка ( что есть логарифмическая сложность).
U>удаление range не эквивалентно удалению поддерева U>берем картинку из вики: https://en.wikipedia.org/wiki/File:AVLtreef.svg U>у range от 9 до 19 включительно общий предок — узел 17 U>но при удалении мы должны на место узла 17 поставить узел 23 из поддерева
U>если удалять range от 14 до 19 включительно, то нужно сохранить 9, 12 и 23
Это понятно, что нахождение общего предка это сильное упрощение и там надо некоторые элементы оставлять в дереве. Но есть подозрение, что все эти операции по перекидыванию указателей можно сделать за 1 проход в процессе поиска общего предка( т.е. в процессе восхождения от first и last наверх по дереву к их общему предку ) т.е. общая сложность будет все та-же O(log(кол-во итераторов от first до last))
Здравствуйте, nobody1985, Вы писали:
N>Вот что говорит документация —
N>Complexity: N>For the last version (erase(first,last)), linear in the distance between first and last.
кстати, качество документации оставляет желать лучшего
давайте из стандарта возьмем, чтобы не вводить читателей в заблуждение:
a.erase(q), q — iterator -> amortized constant
a.erase(q1, q2), q1, q2 — iterators -> log(a.size()) + N where N has the value distance(q1, q2)
a.clear() -> linear in a.size()
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, nobody1985, Вы писали:
N>>Почему у map::erase ( range version ) линейная сложность?
К>Потому что надо удалить [first;last) элементов?
это плохое объяснение
так же плохо расписаны сложности в стандарте, а именно наблюдается неконсистентность — иногда пишут амортизационную сложность, а иногде худшую
для erase(it) выписали амортизационную. причем я бы предположил, что худшая сложность — это log(a.size()), но этот момент почему-то не зафиксирован в стандарте
теперь про erase(it1, it2) — сложность в стандарте для наихудшего сценария, я думаю
если оценивать в лоб, то я бы оценил erase(it1, it2) в log(a.size()) * distance(it1, it2), то есть не сумма, как в стандарте, а произведение
внимание вопрос: как получают сумму и верна ли такая сложность для красно-черных деревьев? как обосновать эту сложность для красно-черных деревьев?
в реализации VS2015 можно увидеть банальную реализацию:
Здравствуйте, uzhas, Вы писали:
U>так же плохо расписаны сложности в стандарте, а именно наблюдается неконсистентность — иногда пишут амортизационную сложность, а иногде худшую
Это правда
Как посчитать сложность наивного удаления?
Ну, можно сходу предложить вот такой плохой случай: пусть у нас диапазон из 1 элемента, который на один шаг левее корня.
Мы на одной лишь беготне it++, получим логарифм.
А если левое поддерево предельно разбалансировано, то удаление одного элемента приведёт к его перестроению вплоть до корня, — и это опять логарифм.
Вот и получили log(N)*M, где N — размер дерева, M=1 — размер диапазона
Наверно, и для любого количества элементов придумать такое разбалансированное дерево, чтобы каждое удаление приводило к массовым перестроениям — это в случае наивного алгоритма.
И наверно, можно придумать способ удаления диапазона, который сперва поубивал бы узлы, а потом перебалансировал оставшееся за log(N-M) вместо M*log(N).
Здравствуйте, uzhas, Вы писали:
U>как-то плохо ты в последнее время объясняешь
Ну так десять вечера, "у царей рабочий день ненормированный", тут думать надо.
При обходе диапазона — логарифмическая добавка, а не множитель.
По самому диапазону мы бежим за линейное время (по каждому ребру один раз спускаемся и один раз поднимаемся), а в конце делаем один бесполезный забег до следующего за концом диапазона элемента.
А с удалением и перебалансировкой — буду дальше подумать.
Здравствуйте, Кодт, Вы писали:
К>Ну так десять вечера, "у царей рабочий день ненормированный", тут думать надо.
ну вот ты в девять вышел — думаешь, просветление у меня настало?
К>При обходе диапазона — логарифмическая добавка, а не множитель.
да я даже не учитывал эту сложность (О малое!), ибо у меня уже произведение нарисовалось
Здравствуйте, uzhas, Вы писали:
К>>При обходе диапазона — логарифмическая добавка, а не множитель. U>да я даже не учитывал эту сложность (О малое!), ибо у меня уже произведение нарисовалось
С обходом разобрались, там log(N) нас не испугал.
Теперь разберёмся с удалениями серии.
Удаление узла с 0 или 1 поддеревом — в худшем случае, приведёт к одному вращению. Что в АВЛ, что в КЧД.
Удаление узла с 2 поддеревьями — это надо взять смежный (в поперечном обходе) узел — у которого, очевидно, 0 или 1 поддерево, — и пересадить вместо удаляемого.
При этом выполняются процедуры балансировки, такие же, как если бы мы наглухо удаляли этот смежный узел.
Например, возьмём смежный справа. У него заведомо нет левого поддерева.
Удаляем B, замещаем его на C
B
___/ \________
A F
... ...
.....
E......
___/ .......
C ........
\
D может отсутствовать, если C - лист
...
C
___/ \________
A F
... ...
.....
E......
_/ .......
D ........
...
Само пересаживание выполняется за константное время, — фигли там, три ребра перерисовать (AB — AC; BF — CF; EC — ED).
Плюс, возможно, вращение узла E, что тоже делается за константное время.
Зато спуск от B к C — за логарифмическое время.
Возьмём достаточно большое дерево и диапазон, начинающийся с корня.
Наивный алгоритм будет каждый раз искать смежный узел (пусть даже чередуя — то левее, то правее), и каждый раз отхватывать логарифмическое время.
Покуда длина диапазона меньше примерно четверти размера дерева, этот множитель будет на нас давить. Для больших диапазонов рано или поздно мы перебалансируем корень и слезем с него, начнём удалять другие узлы.
Не наивный алгоритм должен поступить хитрее: один раз найти итератор правого смежного элемента (т.е. C) и затем за амортизированно-единичное время каждый раз прыгать вправо.
Аналогично, — такой же итератор для левого смежного элемента.
При этом мы на каждом шаге удаляем только один элемент и оставляем дерево в консистентном (сбалансированном) состоянии.
По-хорошему, можно было бы выполнить групповую операцию:
— прибить все узлы из диапазона — и получить лес — кучу маленьких несвязных деревьев (каждое из которых сбалансировано в смысле АВЛ или КЧ)
— аккуратно снизу вверх начать их сшивать, вращая корни для балансировки сшитого дерева
пример
||||||
_@_______________
... _______P_
___H___ ...
_D_ _L_
B F J N
A C E G I K M O
||||||
FGHIJK удаляем
_@
... P_
...
_D L_
B N
A C E M O
у нас дерево распалось на лес ...@, ABCD, E, LMNO, P...
Тогда мы получим ровно один забег во всю высоту дерева, то есть, логарифмическую добавку.
Т.е. вместо O(M*logN) будет O(M) + O(logN).
Но это "аккуратное сшивание" — более заморочно в реализации, чем слежение за пачкой итераторов в "ненаивном" пошаговом алгоритме.
я кажется понял, как тут ухитрились такую хорошую сложность нарисовать
утверждается (хз как доказать), что удаление — амортизационно константа и далеко поднимаемся при удалении маленького множества вершин. то есть чаще всего не подымаемся по дереву далеко вверх
In the algorithm above, all cases are chained in order, except in delete case 3 where it can recurse to case 1 back to the parent node: this is the only case where an iterative implementation will effectively loop. No more than h loops back to case 1 will occur (where h is the height of the tree). And because the probability for escalation decreases exponentially with each iteration the average removal cost is constant.
очень мутная фраза, но будем полагаться на умных людей
то есть надо оценить просто итерацию по входному range
мы знаем, что можно и логарифм отмочить, а можно и единичными инкрементами замучать себя
получаем O(max(distance(it1, it2), log(N))), что эквивалентно сумме из стандарта
Перекуём баги на фичи!
