Comments 32
Было бы интересно увидеть сравнение скорости работы (вставка/поиск/и т.д.) с другими реализациями.
Не понятно зачем нужно и «bool leaf;», и метод «is_leaf()», лучше назвать по разному, если у них разное назначение, либо от одного избавиться.
В C++ дурной тон писать NULL. Либо 0, либо nullptr, как появилось в новом C++11.
Непонятно что с exception-safety, дерево в неконсистентное состояние придёт, если один из new бросит исключение, например.
Метод search() как и другие нужно сделать константными, const, noexcept и другие модификаторы очень важны. Во-первых, константные методы должны быть константными, чтобы не нужно было читать имплементацию для уверенности этого, во-вторых, компилятор генерирует более эффективный код в среднем, в-третьих, из-за одного пропущенного const приходится в десятках мест использующий ваш код множить mutable, const_cast'ы или пропускать const в множестве кода вокруг. Плохой стиль в общем.
Вот эта часть совсем не C++, а C77:
Кучи лишних проверок на нулевой указатель, например здесь:
Ну и код. Огромные куски кода. Статья стала бы действительно хорошей, если бы вы совместили теорию и под спойлеры спрятали куски кода + ссылка на GitHub с полным проектом, а так… Плюс в карму, минус за статью, в целом лабораторная работа — хорошая.
В C++ дурной тон писать NULL. Либо 0, либо nullptr, как появилось в новом C++11.
Непонятно что с exception-safety, дерево в неконсистентное состояние придёт, если один из new бросит исключение, например.
Метод search() как и другие нужно сделать константными, const, noexcept и другие модификаторы очень важны. Во-первых, константные методы должны быть константными, чтобы не нужно было читать имплементацию для уверенности этого, во-вторых, компилятор генерирует более эффективный код в среднем, в-третьих, из-за одного пропущенного const приходится в десятках мест использующий ваш код множить mutable, const_cast'ы или пропускать const в множестве кода вокруг. Плохой стиль в общем.
Вот эта часть совсем не C++, а C77:
int i;
for (i=0; i<=(node->count-1); i++){Кучи лишних проверок на нулевой указатель, например здесь:
if(root!=NULL) deletenode(root);Ну и код. Огромные куски кода. Статья стала бы действительно хорошей, если бы вы совместили теорию и под спойлеры спрятали куски кода + ссылка на GitHub с полным проектом, а так… Плюс в карму, минус за статью, в целом лабораторная работа — хорошая.
unordered_map? Я тоже когда-то лет 15 назад такой велосипед изобретал, когда в STL ещё не было реализации.
to:Tantrido (ошибся веткой)
WAT? В-дерево, как и прочие деревья поиска, работают за log n и имеют упорядоченную структуру, т.е. полная противоположность unordered_map aka хэш-таблицы.
WAT? В-дерево, как и прочие деревья поиска, работают за log n и имеют упорядоченную структуру, т.е. полная противоположность unordered_map aka хэш-таблицы.
Простите: std::map :
Maps are typically implemented as binary search trees.www.cplusplus.com/reference/map/map
А оно подходит для внешней памяти?) Сомневаюсь.
А при чём тут внешняя память? В постановке задачи это было?
Ну как бы B-дерево для внешней памяти прежде всего используют.
1. прежде всего, не значит всегда, b-tree очень успешно используется и для работы в оперативной памяти;
2. реализация в статье не работает с внешней памятью и вообще никаким образом не упоминает внешнюю память;
3. реализация в статье даже если бы работала с внешней памятью была бы не сильно эффективнее обычного бинарного дерева, потому что t = 2.
2. реализация в статье не работает с внешней памятью и вообще никаким образом не упоминает внешнюю память;
3. реализация в статье даже если бы работала с внешней памятью была бы не сильно эффективнее обычного бинарного дерева, потому что t = 2.
Такое многообразие существующих структур данных, которые вы, почему-то, смешали в одну кучу, существует именно из-за того, что каждая из них более эффективна и применима в своем конкретном случае:
unordered_map — хеш-таблица, амортизированный доступ O(1), элементы не упорядочены
map — двоичное дерево, амортизированный доступ O(logN), элементы упорядочены, упор на скорость доступа в памяти
b-tree — N-ричное сильноветвящееся дерево, амортизированный доступ O(logN), элементы упорядочены, упор на скорость доступа на блочном устройстве хранения (т.е. количество узлов до листа 3-4, но узлы большие и хранят сразу много элементов)
unordered_map — хеш-таблица, амортизированный доступ O(1), элементы не упорядочены
map — двоичное дерево, амортизированный доступ O(logN), элементы упорядочены, упор на скорость доступа в памяти
b-tree — N-ричное сильноветвящееся дерево, амортизированный доступ O(logN), элементы упорядочены, упор на скорость доступа на блочном устройстве хранения (т.е. количество узлов до листа 3-4, но узлы большие и хранят сразу много элементов)
1. вы мешаете в кучу амортизированные оценки и средние оценки, а это не одно и тоже;
2. двоичных деревьев поиска есть много разных и не все из них дают «амортизированный доступ» за O(log N), но вы их почему-то смешли в одну кучую;
3. ну и map — это стандартный контейнер C++, от него требуются определенные гарантии, но использование двоичного дерева поиска в качестве реализации не является одной из этих гарантий.
2. двоичных деревьев поиска есть много разных и не все из них дают «амортизированный доступ» за O(log N), но вы их почему-то смешли в одну кучую;
3. ну и map — это стандартный контейнер C++, от него требуются определенные гарантии, но использование двоичного дерева поиска в качестве реализации не является одной из этих гарантий.
двоичных деревьев поиска есть много разных и не все из них дают «амортизированный доступ» за O(log N), но вы их почему-то смешли в одну кучуюЯ в курсе про двоичные деревья, и я комментировал ответ, там понятно о чем речь. На мой взгляд, логично предположить что любое, практичное, двоичное сбалансированное дерево будет иметь сложность основных операции O(logN), а не O(N^2).
ну и map — это стандартный контейнер C++, от него требуются определенные гарантии, но использование двоичного дерева поиска в качестве реализации не является одной из этих гарантий
Я в курсе про стандарт и мне не хотелось бы уходить в такие дебри. Опять же, де факто, используется красно-черные двоичные деревья, которые, по факту, 2-3-4 деревья. Используются для экономии в реализации по памяти, т.к. нужен всего один дополнительный бит на узел.
С чем вы спорите мне не понятно.
Я вам тонко намекают, что вы зря критикует человека за то что он что-то там смешал, во первых потому что он ничего не смешивали, а как вы выразились "не стал уходить в дебри", а во вторых потому что вы сами много чего намешали в кучу.
И кстати придумать бинарное дерево поиска в котором базовые операции работают за квадрат, а не за линию, это нужно немного постараться.
По поводу замечаний про деревья я с вашими замечаниями согласен и в курсе, что на самом деле все намного сложней. Теперь, в рамках обсуждения b-tree, Tantrido упомянул сначала unordered_map (очевидно, по названию, что в контексте С++), потом поправился на map. Я, всего-лишь, хотел уточнить что b-tree другая структура и используется, как правило, с внешней памятью, т.к. по скорости поиска в памяти, где прыжки по случайным адресам, относительно внешних носителей, дешевы, уступает двоичному дереву.
Вот просто так берет и уступает? Безотносительно нагрузки? А как насчёт кеш локальности и TLB локальности?
Смотря какие операции и кокой N в узлах. Если только поиск, то может и не уступает. А вот балансировка и вставка будет сложнее. Если брать все операции, в общем, то разработчики stl посчитали что уступает.
А может быть разработчикам STL нужно было соблюдать семантику итераторов описанную в стандарте и поэтому они решили использовать бинарное дерево поиска с которым проще этого добиться, а скорость и затраты памяти тут не причём? Может вы не будете выставлять свои гадания как подтвержденные факты?
Ну давайте не будем считать разработчиков STL идиотами. Кстати, итераторы не лучшая из концепций, во всяком случае, в том виде как она реализована в STL, но, исходя из эффективности, разработчики пошли на компромисс между скоростью, удобством и безопасностью. В STL стандартизована куча интерфейсов, реализация которых не описана, но почти напрямую из них вытекает, именно потому, что об эффективности думали не в последнюю очередь. Не вижу проблем реализовать итераторы в AVL-tree или в B-Tree. Нет, вы всерьез считаете что сначала появился стандарт, а потом уже думали как его эффективно реализовать на С++?
Стандарт закладывался в 90-е годы, 20-25 лет назад. Тогда действительно случайный доступ к памяти можно было считать условно-мгновенным и эффектами локальности кэша пренебречь. С тех пор многое изменилось. Вы можете сами попробовать: возьмите stx-btree или cpp-btree и сравните с std::map. На многих задачах превосходство оказывается очень серьезным.
Я нигде не утверждал и не спорю что нельзя сделать эффективнее в конкретном случае, но для повседневных задач, где и планировалось использовать STL, его скорости, вполне хватает. std::map действительно не очень шустрый, в основном из-за new, да и памяти жрет многовато. Но если в конкретном месте нужна сверхэффективность, то там STL никто не будет использовать и стандартный new тоже, согласитесь?
Вы не видите проблемы, а я вижу. Для b-tree можно реализовать итераторы, но если соблюдать все требования итераторов std::map, толку от такой реализации будет не много.
И да, то что создатели C++ не определили семантику std::map и его итераторов так, чтобы её можно было эффективно реализовать используя b-tree не делает их идиотами, но это и не делает b-tree медленнее бинарного дерева поиска и не делает ваши гадания фактами.
Еще раз, я не утверждаю, что нельзя эффективнее сделать. Я знаю что B-Tree на современном железе быстрее из-за последовательного доступа и минимизации использования new. Но мы, вроде, обсуждали STL и стандартные контейнеры, и в рамках STL B-tree реализовать можно (собственно красно-черное дерево, которое обычно используется там и есть 2-3-4 дерево, которое есть частный случай B-tree, и итераторы там работают), но будет не эффективно.
Вы не утверждали? А я вот читаю ваши комментарии и вижу обратное.
Нет мы обсуждали не стандартные контейнеры, а то что вы смешали кучу всего в кучу (при этом обвинив в этом кого-то другого), затем мы обсуждали ваше утверждение о том, что бинарные деревня поиска при работе в памяти быстрее чем b-tree (сильное утверждение без всяких оговорок, но, если и может быть), а затем мы обсуждали создателей STL и то какие они не дураки...
Нет, мы обсуждали не стандартные контейнеры
Такое ощущение, что вас было много и я вклинился не в тему. Давайте вы не будете за других решать что им обсуждать, а что нет. Обсуждать B-tree в отрыве от конкретики, как вы это предлагаете мне не интересно.
Интересно обсудить почему в стандарте контейнеры реализованы так, а не иначе и почему не используется B-tree. Вашу точку зрения я понял. Вы педалируете идею что B-tree, чуть ли не, серебряная пуля и пора уже заменить все деревья на B-Tree. Я с вами не согласен. Кеш и локальность играет тем большее значение, чем тип хранимого значения ближе к POD. Даже если бы возможно было изменить интерфейс, то в библиотеке общего плана, такой как STL, невозможно полагаться что большинство объектов в таком дереве будет «плоскими» и иметь быстрые компараторы. При большом количестве элементов в узле (а иначе какая может быть локальность) в b-tree вам придется линейно пробегаться и вызывать большое число компараторов, возможно, не «линейных» объектов, которые вы не контролируете. В двоичном дереве за одно сравнение вы сразу отсекаете половину элементов. Выигрыш от кеша и локальности вы получите только при быстрых компараторах, если это возможно и POD-like элементах, на что в общем случае полагаться невозможно. Именно по этой причине разработчики и и меняют реализацию дерева в std::map, а не потому что они ретрограды и 25 лет ковыряются в носу. Чем сложнее объекты, тем больше нивелируется влияние кеша и тем больше выигрывает двоичное дерево у B-tree.
Давайте вы не будете за других решать что им обсуждать, а что нет.Я ничего за других не решаю, а вам бы стоило перечитать свои же комментарии.
Вы педалируете идею что B-tree, чуть ли не, серебряная пуля и пора уже заменить все деревья на B-Tree.Да ну? Покажите пожалуйста, где я такое утверждал?
в b-tree вам придется линейно пробегаться и вызывать большое число компараторовА про бинарный поиск вы не слышали?
В двоичном дереве за одно сравнение вы сразу отсекаете половину элементов.А в B-tree нет?
Выигрыш от кеша и локальности вы получите только при быстрых компараторах, если это возможно и POD-like элементах, на что в общем случае полагаться невозможно.Вы пишете ерунду, из того, что на кеш и TLB локальность в общем случае нельзя полагаться никак не следует, что нужно их всегда игнорировать. И перед тем как делать такие сильные утверждения возьмите и потестируйте разные алгоритмы.
Да ну? Покажите пожалуйста, где я такое утверждал?Вот же.
А про бинарный поиск вы не слышали?Опа, а как же ваш «любимый» кеш? Бинарный поиск с O(logN) разве не эквивалентен бинарному дереву?
А в B-tree нет?Элементов в узле то больше. Чуть выше вы же говорили про бинарный поиск.
Вы пишете ерунду.Это не я пишу ерунду, а вы используете подростковую категоричность не желая слушать другую точку зрения. Почитайте любую книгу по теории структур данных и вы узнаете что любое дерево, в том числе и B-Tree можно представить в виде эквивалентного двоичного дерева. Такое дерево всегда будет иметь больше узлов, больше сравнений и менее сбалансированное (не обязательно буквально, ваш бинарный поиск это просто кусок этого бинарного дерева). То, что на практике кеш ускоряет константную составляющую и B-tree во многих случаях выходит вперед не делает его универсальным. Чем больше нивелируется влияние кеша тем быстрее двоичное дерево и наоборот. Все остальное зависит от задачи и параметров. Думаю что разработчики stl не глупее нас и лучше понимают каких задачи, на практике, встречаются чаще.
Вот же.И там прямым текстом написано что в C++ есть требования к итераторам, которые не получится эффективно реализовать для b-tree. Да уж действительно серебрянная пуля…
Опа, а как же ваш «любимый» кеш? Бинарный поиск с O(logN) разве не эквивалентен бинарному дереву?1. Я уже писал про TLB, который вы категорически игнорируете. 2. С деревьями не только поиск, вставку и удаление производят, по ним еще иногда и итерируются.
Хотя я вроде уже упоминал, что есть разные нагрузки, и утверждать, что одна структура лучше другой независимо от нагрзуки (как вы сделали и на что я вам уже указывал) странно.
Элементов в узле то больше. Чуть выше вы же говорили про бинарный поиск.Да говорил и?
Почитайте любую книгу по теории структур данных и вы узнаете что любое дерево, в том числе и B-Tree можно представить в виде эквивалентного двоичного дерева.И это гарантирует функциональную эквивалентность, но не одинаковую эффективность.
Такое дерево всегда будет иметь больше узлов, больше сравнений и менее сбалансированное (не обязательно буквально, ваш бинарный поиск это просто кусок этого бинарного дерева).Бинарное дерево полученное из b-tree может быть, но вот b-tree это всегда идеально сбалансированное дерево поиска и с учетом бинарного поиска и без него (может вам стоит самому обратиться к книгам по алгоритмам?).
То, что на практике кеш ускоряет константную составляющую и B-tree во многих случаях выходит вперед не делает его универсальным.И я ведь нигде не говорил про универсальность, более того прямым текстом указал вам, что как минимум существует проблема с итераторами. Но вы опять же это проигнорировали или просто не поняли (к вопросу про подростковую категаричность и нежелание слушать).
Извините, я ошибся веткой и нечаянно ответил вам сюда
Ошибся комментварием. Ответ сюда
И там прямым текстом написано что в C++ есть требования к итераторамВы сами игнорируете аргументы. Давайте на время забудем про них.
Хотя я вроде уже упоминал, что есть разные нагрузки, и утверждать, что одна структура лучше другой независимо от нагрузки (как вы сделали и на что я вам уже указывал) странно.А никто с этим и не спорит
И это гарантирует функциональную эквивалентность, но не одинаковую эффективность.Правильно. Пока у процессора и памяти нет операций по мгновенному сравнению всех N вершин, любое дерево отличное от бинарного потребует столько же либо больше операций сравнения и будет менее эффективным.
Бинарное дерево полученное из b-tree может быть, но вот b-tree это всегда идеально сбалансированное дерево поиска и с учетом бинарного поиска и без него (может вам стоит самому обратиться к книгам по алгоритмам?).Это в идеальном сферическом вакууме, а на практике, любое не бинарное дерево потребует количество операций такое же как в эквивалентном бинарном. Ну не умеет пока железо и память работать сразу с узлами B-tree целиком. Что бы не придумали количество операций сравнения всегда будет либо столько же, либо больше чем в эквивалентном бинарном.
И я ведь нигде не говорил про универсальность, более того прямым текстом указал вам, что как минимум существует проблема с итераторами.И я не говорил. Я, просто, не согласен с вами в том что в std::map используется бинарное дерево лишь потому, что стандарт стар. B-tree будет сильно опережать двоичное дерево там, где есть выгода по скорости от локальности данных. Особенно эта разница проявляется на внешних носителях. Также, B-tree будет иметь значительный оверхед по памяти, о чем вы тактично умалчиваете.
Вы сами игнорируете аргументы. Давайте на время забудем про них.Вы утверждали, что я продвигаю b-tree, как серебрянную пулю и в качестве аргумента привели мое утверждение, где прямым текстом сказано обратное, а теперь предлагаете забыть про аргументы? Вы серьезно?
А никто с этим и не спорит
Вы сделали утверждение, что бинарные деревья поиска в памяти лучше b-tree безотносительно чего бы то ни было (прямо тут) вас поправили, а вы вместо того чтобы на этом успокоиться стали привелкать аргументы вроде, а там вот дяди умные сделали значит так правильно! При этом почему умные дяди приняли то или иное решение вы только гадаете. Вы только и делаете что спорите, причем спорите не аргументированно.
Правильно. Пока у процессора и памяти нет операций по мгновенному сравнению всех N вершин, любое дерево отличное от бинарного потребует столько же либо больше операций сравнения и будет менее эффективным.И что? Из этого разве следует, что бинарное дерево как минимум не хуже b-tree по производительности? И почему вы опять лихо отбрасываете в сторону такие вещи как кеш и TLB (про которые я уже неоднократно вам упоминал)? Более того, даже большее количество сравнений само по себе не значит меньшую скорость работы.
Это в идеальном сферическом вакууме, а на практике, любое не бинарное дерево потребует количество операций такое же как в эквивалентном бинарном. Ну не умеет пока железо и память работать сразу с узлами B-tree целиком. Что бы не придумали количество операций сравнения всегда будет либо столько же, либо больше чем в эквивалентном бинарном.Нет, b-tree идеально сбалансированное дерево поска без всяких вакуумов, тем более сферических. И опять же напомню, хотя зря наверно, что речь ведь не только о количестве сравнений, но о производительности на реальном железе (да-да том самом железе, где есть кеш и TLB, если повезет).
Я, просто, не согласен с вами в том что в std::map используется бинарное дерево лишь потому, что стандарт стар.Вы не согласны со мной? А где я такое утверждал, чтобы вы со мной были не согласны? Более того я вам говорил уже несколько раз про проблему с итераторами (и при этом ни разу ни слова не сказал про чей бы то ни было возраст).
Также, B-tree будет иметь значительный оверхед по памяти, о чем вы тактично умалчиваете.Ну да? А вы это видели? Опять же b-tree будет иметь оверхед по памяти (о котором я оказывается тактично умалчиваю) безотносительно чего бы то ни было?
Вообще у меня складываеится впечатление, что вы посмотрели, что в std::map используется бинарное дерево поиска, а потом уже на основании того, что std::map же умные дяди сделали, стали подтягивать всякую разную (и не всегда корректную) аргументацию, чтобы оправдать это решение.
Sign up to leave a comment.
Сбалансированное дерево поиска B-tree (t=2)