Comments 22
Nested sets часто используется в крупных магазинах, смысл не только в том что можно от рекурсии избавится, а к примеру получить дерево одним запросом
SELECT id, name, step FROM category_tree ORDER BY left
В итоге, после небольшой обработки (в которой step играет роль множителя отступа), получим следующий список:
• Узел 1
• • Узел 2
• • • Узел 5
• • • • Узел 10
• • • • Узел 11
• • Узел 3
• • • Узел 6
• • • Узел 7
• • • • Узел 12
• • • • Узел 13
• • • • Узел 14
• • • Узел 8
• • Узел 4
• • • Узел 9
• • • • Узел 15
• • • • Узел 16
А скиплисты не рассматривали?
https://15721.courses.cs.cmu.edu/spring2018/papers/08-oltpindexes1/pugh-skiplists-cacm1990.pdf
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.524&rep=rep1&type=pdf
Очень эта структура нравится.
Оно, конечно, полезно пытаться что-то сделать самому, но неплохо-бы еще прокачать оценку своих изысканий и не тащить на хабр откровенно нубский материал.
Проблемы в порядке чтения, а не в порядке важности:
Использование глобальных переменных и статических функций исключительно для того, чтоб избежать передачи лишнего параметра в функцию, мягко говоря, неоправданно.
Дерево не самобалансирующее, а это значит, что на отсортированных данных заполнение дерева даст квадратичную сложность. Ну и на рандомных данных сложность будет гулять от O(n*log(n)) до O(n*n).
Для задачи поиска повторяющихся значений деревья вообще не нужны, можно использовать HashMap у которого сложность добавления и поиска элементов - константа, в результате сложность заполнения мапы будет линейная O(n), а если еще дубли просто класть в HasSet, то проход по всем дублям будет размером с количество оных дублей.
Поиск дублей капец замороченный, прям мозг отказывается читать, ибо надо чуть напрячься, тогда как в нормальном проходе по дереву все ясно с первого взгляда.
С учетом того, что во время поиска в step кладутся либо 0, либо 1, либо 2, есть стойкое подозрение, что на длинных ветках оный поиск просто будет ломаться.
Вообще в рекурсии нет ничего плохого, есть знать, что делаешь.
Дерево не самобалансирующее, а это значит, что на отсортированных данных заполнение дерева даст квадратичную сложность. Ну и на рандомных данных сложность будет гулять от O(n*log(n)) до O(n*n).
Вы придумываете проблемы, чтобы придраться чтоли? если данные отсортированы, то мы просто бинарным поиском ищем, если данные как попало поступают, то делаем дерево.
я сделал сбалансированное дерево. исправил. можете проверить даже, что всё работает.
Самое большое преимущество рекурсии, как мне кажется в том, что она позволяет написать аналитический код. Т.е. такой, который можно проанализировать человеческим разумом, логикой и существующим мат. аппаратом.
Тем же преимуществом обладает подход замены "просто цикла" на стандартизированные, предсказуемые и анализируемые сверку, маппинг и фильтр.
А цикл, в котором происходит что то забористое и замороченное плохо поддается анализу. Невозможно предугадать как он себя поведет в том или ином ом случае и какие в нем могут быть скрыты потенциальные баги и проблемы.
Я думаю что оно в некоторых случаях будет более удобно, нежели дерево с рекурсией.
В каких случаях? Чем удобнее? Удалось ли подтвердить свое предположение? Непонятен смысл всех этих танцев с бубном.
Я указал локальные переменные как регистры, чтобы хоть чуточку быстрее работало. Если посмотреть через дизассемблер, то можно увидеть, что у 64 битного проца хватает регистров.
Это уже давно не влияет, компилятор сам решает, где ему лучше разместить переменные, так что использовать register смысла нет.
И количество регистров никак не связано с разрядностью проца, если вдруг это подразумевалось.
У x64 вдвое больше регистров общего назначения по сравнению с x86, если вдруг это подразумевалось.
Несомненно, но ведь вызвано это отнюдь не увеличением разврядности. Не удивлюсь, если у какого-то древнего 32-битного RISC'а из 90-х (типа IBM POWER2) регистров намного больше, чем у x86_64
А из текста автора может показаться, что разрядность и кол-во регистров - вещи связанные.
Да, это подразумевалось.
В каких случаях? Чем удобнее? Удалось ли подтвердить свое предположение? Непонятен смысл всех этих танцев с бубном.
Ну как? Даже Robert Sedgewick пишет в своей книге Algorithms in C, что стек может переполниться. ну вы представляете если у вас 30 000 000 или больше вложений получиться в дереве, какой будет стек? 30 000 000 * 8 = 180 000 000, а тут же ещё память выделенная для данных. Короче я опять думаю что вы не подумав мне написали.
Вы считаете все атомы во Вселенной, что у вас 30 млн уровней в двоичном дереве? И если вы имели в виду 30 млн узлов в дереве, то это всего лишь 25 уровней в сбалансированном дереве, значит глубина рекурсии не более 25.
С учетом того, что по AMD64 ABI все параметры и результат передаются в регистрах, локальные переменные скорее всего тоже будут в регистрах, стэк будет использоваться по минимуму.
А хамить не стоит.
Я задал вопросы, которые, на мой взгляд, должны были быть раскрыты в статье, иначе непонятно, зачем это было писать. Если вы не принимаете конструктивную критику, то не станете лучше писать.
Компилятор сам отлично умеет разворачивать хвостовую рекурсию в цикл (равно как и раскладывать локальные переменные по регистрам). Какой смысл все это расписывать вручную? Автор черпал вдохновение в афоризме Ларри Уолла "Real programmers can write assembly code in any language"?
У меня вопрос - зачем это делать, если есть стандартная библиотека С++ и на выбор set, multiset, map, multimap, unorderes_set, unorderes_multiset, unorderes_map, unorderes_multimap?
Кроме того, стандартная библиотека шаблонная. А здесь, при смене типа хранимых данных, придется все переписывать.
И еще - чем больше кода, тем больше ошибок. И времени на отладку. Например n->step == 2; в функции find_matches. Или calloc без free.
На С++ со стандартными библиотеками это могло выглядеть примерно так:
int main(int argc, char **argv)
{
srandom(time(0));
std::map tree;
for (unsigned long i = 0; i < 1000000; i++){
unsigned long r = random () % 1000;
tree[r]++;
}
for (auto e : tree) {
std::cout << e.first << ": " << e.second << std::endl;
}
return 0;
}
Зачем м в узле определять и родителей и потомков? Это не избыточно?
Дерево без рекурсии