Comments 32
В 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 с полным проектом, а так… Плюс в карму, минус за статью, в целом лабораторная работа — хорошая.
WAT? В-дерево, как и прочие деревья поиска, работают за log n и имеют упорядоченную структуру, т.е. полная противоположность unordered_map aka хэш-таблицы.
Maps are typically implemented as binary search trees.www.cplusplus.com/reference/map/map
А оно подходит для внешней памяти?) Сомневаюсь.
Ну как бы B-дерево для внешней памяти прежде всего используют.
2. реализация в статье не работает с внешней памятью и вообще никаким образом не упоминает внешнюю память;
3. реализация в статье даже если бы работала с внешней памятью была бы не сильно эффективнее обычного бинарного дерева, потому что t = 2.
unordered_map — хеш-таблица, амортизированный доступ O(1), элементы не упорядочены
map — двоичное дерево, амортизированный доступ O(logN), элементы упорядочены, упор на скорость доступа в памяти
b-tree — N-ричное сильноветвящееся дерево, амортизированный доступ O(logN), элементы упорядочены, упор на скорость доступа на блочном устройстве хранения (т.е. количество узлов до листа 3-4, но узлы большие и хранят сразу много элементов)
2. двоичных деревьев поиска есть много разных и не все из них дают «амортизированный доступ» за O(log N), но вы их почему-то смешли в одну кучую;
3. ну и map — это стандартный контейнер C++, от него требуются определенные гарантии, но использование двоичного дерева поиска в качестве реализации не является одной из этих гарантий.
двоичных деревьев поиска есть много разных и не все из них дают «амортизированный доступ» за O(log N), но вы их почему-то смешли в одну кучуюЯ в курсе про двоичные деревья, и я комментировал ответ, там понятно о чем речь. На мой взгляд, логично предположить что любое, практичное, двоичное сбалансированное дерево будет иметь сложность основных операции O(logN), а не O(N^2).
ну и map — это стандартный контейнер C++, от него требуются определенные гарантии, но использование двоичного дерева поиска в качестве реализации не является одной из этих гарантий
Я в курсе про стандарт и мне не хотелось бы уходить в такие дебри. Опять же, де факто, используется красно-черные двоичные деревья, которые, по факту, 2-3-4 деревья. Используются для экономии в реализации по памяти, т.к. нужен всего один дополнительный бит на узел.
С чем вы спорите мне не понятно.
Я вам тонко намекают, что вы зря критикует человека за то что он что-то там смешал, во первых потому что он ничего не смешивали, а как вы выразились "не стал уходить в дебри", а во вторых потому что вы сами много чего намешали в кучу.
И кстати придумать бинарное дерево поиска в котором базовые операции работают за квадрат, а не за линию, это нужно немного постараться.
Вот просто так берет и уступает? Безотносительно нагрузки? А как насчёт кеш локальности и TLB локальности?
А может быть разработчикам STL нужно было соблюдать семантику итераторов описанную в стандарте и поэтому они решили использовать бинарное дерево поиска с которым проще этого добиться, а скорость и затраты памяти тут не причём? Может вы не будете выставлять свои гадания как подтвержденные факты?
Стандарт закладывался в 90-е годы, 20-25 лет назад. Тогда действительно случайный доступ к памяти можно было считать условно-мгновенным и эффектами локальности кэша пренебречь. С тех пор многое изменилось. Вы можете сами попробовать: возьмите stx-btree или cpp-btree и сравните с std::map. На многих задачах превосходство оказывается очень серьезным.
Вы не видите проблемы, а я вижу. Для b-tree можно реализовать итераторы, но если соблюдать все требования итераторов std::map, толку от такой реализации будет не много.
И да, то что создатели C++ не определили семантику std::map и его итераторов так, чтобы её можно было эффективно реализовать используя b-tree не делает их идиотами, но это и не делает 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 же умные дяди сделали, стали подтягивать всякую разную (и не всегда корректную) аргументацию, чтобы оправдать это решение.
Сбалансированное дерево поиска B-tree (t=2)