Ну как сказать несравнимо, shared_ptr по крайней мере при удалении последней ссылки не ходит по непонятного размера спику weak_ptr-ов, чтобы их все занулить. А ваш trackable ходит, к тому же еще делает это зачем-то рекурсивно.
Кажется, что ваш анализ неправильный. Представим, что мы добавляем в ваше дерево элементы в таком порядке:
— 1, 10, 2 (тут мы получаем дерево высоты 2, в корне 1 в левом поддереве 2, в правом 10)
— 9 (9 станет левым ребенком 2, потому что 9 больше 1 и 2 в левом поддереве, но меньше 10, значит по коду идем в левое поддерево, где вставка уже делается очевидным образом)
— 3 (3 станет левым ребенком 2 как раньше было с 9, а 9 станет правым ребенком 2)
— 8 (8 станет левым ребенком 3)
— 4 (4 станет левым ребенком 3, а 8 станет правым)
— 7 (7 станет левым ребенком 4)
— 5 (5 станет левывм ребенком 4, а 7 станет правым)
Если я правильно понял, тот такой паттерн вырождает ваше дерево практически в бамбук, и при этих вставках
поле k вообще не проверяется. Мне серьезно кажется, что гораздо проще просто использовать TreeSet/TreeMap и после каждого обновления переискивать минимальный элемент.
Действительно, для такого случая легко создать подходящую функцию, но если вы затачиваетесь только под этот случай, то зачем вообще переопределять хеш? Его можно забить внутри класса.
Почему вместо этого просто не параметризовать вашу структуру ассоциативным контейнером? Можно будет использовать простой массив, если возможно, а можно хеш-таблицу. И не нужно будет делать странных оговорок про хеш без коллизий.
1. min-heap тоже может работать с любыми данными, проблема стандартных реализаций min-heap заключается в том, что обычно они не поддерживают эффективное удаление произвольного элемента из кучи, даже если известна позиция элемента в куче;
2. Чтобы асиптотика операций над вашим деревом была логарифмической, высота дерева должна быть логарифмический, что из вашего кода не очевидно, в то время как TreeMap/TreeSet гарантируют логарифмическую сложность.
Кроме того
3. Если вы используете хеш, то не должны ли вы предусмотреть возможность коллизий? Или просто использовать HashSet, который уже умеет это делать.
4. Ваша функция connectNodes выглядит как-то странно, допустим вы хотите объединить два узла, у которых есть дети (в зависимости от реализации getElemeInArray, которую вы нигде не упоминаете, это может произойти при удалении элемента по значению), тогда посмотрим на этот код в самом начале функции:
вы проверяете, что один из них меньше и подцепляете больший к меньшему в качестве левого ребенка теряя все что там было в левом поддереве. Это особенно странно, потому что ваш connectNodes может быть вызван для братьев, но при этом работает для них как-то не симметрично, если один из них меньше, то вы тут же возвращаетесь из функции, а если другой меньше то вы идете в цикл.
Перед тем как заниматься сравнением производительности, не могли бы вы показать более или менее формально, что:
1. ваша структура данных вообще кооректно работает
2. что ваша асимптотика такая, как вы заявляете?
Нумерация, несмоненно, задает порядок, но не каждый порядок сводится к нумерации, просто потому что не каждое множество счетное и, соответственно, не каждое множество можно занумеровать.
Я спорю не о том как написано у автора, а с вашим мнением, о том, что для бинарного поиска нужен массив — это не правда.
Ничего подобного, массив, какое бы определение вы не использовали, всегда предполагает нумерацию, т. е. как максимум счетное множество (я бы даже сказал конечное, но да это не важно). А бинарный поиск можно использовать и не на счетном множестве. Я уже приводил пример монотонной функции, множество точек которой совсем не обязательно должно быть счетно.
Например, для поиска нуля монотонной функции — массив не нужен в явном виде, достаточно уметь вычислять функцию в точке.
Про отсутствие элементов или порядка я ничего не говорил, только про отсутствие массива.
Боюсь ваша «простая житейская логика» не имеет право называть логикой. И то что я в академической среде не запрещает мне также иметь отношение и к реальной разработке. Но да, я бы предпочел, чтобы вы «умыли руки».
Я то умею, а вы? Напомню вам, что это вы назвали конкретное число взятое опять же из воздуха лишь бы было какое-нибудь.
Дайте свой вариант, почему «хороших» программистов не так много, как бы хотелось, с вашей отличной аргументацией.
Я вам ничего давать не буду, как я уже сказал, я показываю вам слабость вашей аргументации, а вы пока только в штыки все воспринимаете.
Я указал вам на факт, что спрос на специалистов есть (не каких попало и не только крутых, а самых нормальных — разбирающихся в основах) как минимум в больших компаниях, откуда он берется, учитывая, что каждый год куча вузов выпускает кучу «программистов» по всему миру, для меня загадка. Но факт есть факт — специалистов не хватает.
Они приложили свои 20% усилий и получили 80% своего результата. Принцип Парето для них срабатывает.
Да с чего вы это взяли?
Вот специально для вас сходил на hh.ru
Распределение по з.п. С++
до 55 000 руб — 177
от 55 000 до 105 000 — 102
от 150 000 до 200 — 69
от 200 000 — 29
Итого всего 377 вакансий? Вам не кажется это число маленьким, чтобы делать на его основании какие-то выводы?
Сколько вакансий высококлассных спецов в больших компаниях?
Все? Или таки меньшее количество?
Вы, очевидно, не поняли мое утверждение, мое утвержджение — большие компании набирают специалистов (и не только классных) постоянно, не только когда у них открыласаь какая-то вакансия для классного спеца. Потому что классному специалисту (и это чуть более высокий уровень, чем умеет реализовать сортировку пузырьком — не великое достижение) работа в большой компании найдется. При условии, что он знаком с базовыми вещами и умеет свои мысли превращать в алгоритмы, а алгоритмы в код.
А ЗП в районе 100 000, это весьма неплохая ЗП.
Если вы живете в Питере -> Красноярске -> Хабаровске, то может быть. А если вы живете в Дублине, то очень сомневаюсь.
И ее вполне может хватать для того, что бы дальше не напрягаться.
Ну как вариант.
Не нравится, предложите свой.
Мне в первую очередь не нравится аргументация вашей своей позиции, на что я и пытаюсь обратить ваше внимание.
Всмысле как? Очевидно, 20% не большинство программистов — я вам показал, что этот принцип можно как угодно поворачивать, чтобы подтверждить свою позицию — какой удобный принцип.
Тех усилий, которые прилагают большинство программистов, хватает этим программистам на хлеб с маслом.
Так яснее?
Может и яснее, но это своершенно другое утверждение по сравнению с:
И работает принцип Парето. 20% усилий дают 80% результата.
Кроме сомнительного использорвания принципов, у вас еще есть плохая привычка говорить за других (большинству хватает, где вы взяли эту информацию?) и использорвать взятые из воздуха числа (100-1000, сотни тысяч, откуда это?). И про спрос на серьезных кандидатов попадает в эту же кучу, большие компании практически не переставя ищут кандидатов, и не каких папало.
Вы очень своевольно интерпретируете принцип Парето. Если так, то почему тогда не интерпретировать его как: 20% разработчиков (как раз таки не большинство), создают 80% результата?
Ну так и я пытался вам показать, что пример-то для наследования не очень удачный (как вы можете видеть, мое решение не очень-то далеко ушло от switch-а).
Еще раз, я до вас пытаюсь донести мысль, что алгоритмические вопросы на собеседовании оценивают не как кандидат может решать какую-то конкретную задачу, знает ли он какой-то конкретный алгоритм или структуру данных, и уж тем более не знание интерфейса очередной нелепой библиотеки для построения отчетов. Проверяется, как он может искать решение задачи, для которой решения не известно. Проверяется как он может думать, как он может оценивать, может ли обоснованно принимать решения.
Среди моих утверждений не было:
1. только алгоритмические вопросы и никакие другие;
2. алгоритмическиме вопросы работают для всех;
Среди моих утверждений было:
1. нет ничего плохого в попытке оценить мысленный процесс;
2. нет ничего плохого в использовании алгоритмических вопросов для оценки мысленного процесса;
3. алгоритмические задачи встречаются в реальной жизни;
4. инженер — интеллектуальная работа, т. е. он должен уметь искать решение задач.
Если инженер не может нормально разрабатывать решение проблемы, с которой он раньше не сталкивался, то какой от него толк? Собственно, это и пытаются оценить, и я не вижу ничего плохого в попытке оценить «как мыслит кандидат». В конечном итоге любая инжеренерия — это интеллектуальная работа, мысленный процесс.
— 1, 10, 2 (тут мы получаем дерево высоты 2, в корне 1 в левом поддереве 2, в правом 10)
— 9 (9 станет левым ребенком 2, потому что 9 больше 1 и 2 в левом поддереве, но меньше 10, значит по коду идем в левое поддерево, где вставка уже делается очевидным образом)
— 3 (3 станет левым ребенком 2 как раньше было с 9, а 9 станет правым ребенком 2)
— 8 (8 станет левым ребенком 3)
— 4 (4 станет левым ребенком 3, а 8 станет правым)
— 7 (7 станет левым ребенком 4)
— 5 (5 станет левывм ребенком 4, а 7 станет правым)
Если я правильно понял, тот такой паттерн вырождает ваше дерево практически в бамбук, и при этих вставках
поле k вообще не проверяется. Мне серьезно кажется, что гораздо проще просто использовать TreeSet/TreeMap и после каждого обновления переискивать минимальный элемент.
Не обязательно, можно просто после каждой изменяющей дерево операции за высоту дерева найти минимум — асимптотика никак не пострадает.
Действительно, для такого случая легко создать подходящую функцию, но если вы затачиваетесь только под этот случай, то зачем вообще переопределять хеш? Его можно забить внутри класса.
Почему вместо этого просто не параметризовать вашу структуру ассоциативным контейнером? Можно будет использовать простой массив, если возможно, а можно хеш-таблицу. И не нужно будет делать странных оговорок про хеш без коллизий.
2. Чтобы асиптотика операций над вашим деревом была логарифмической, высота дерева должна быть логарифмический, что из вашего кода не очевидно, в то время как TreeMap/TreeSet гарантируют логарифмическую сложность.
Кроме того
3. Если вы используете хеш, то не должны ли вы предусмотреть возможность коллизий? Или просто использовать HashSet, который уже умеет это делать.
4. Ваша функция connectNodes выглядит как-то странно, допустим вы хотите объединить два узла, у которых есть дети (в зависимости от реализации getElemeInArray, которую вы нигде не упоминаете, это может произойти при удалении элемента по значению), тогда посмотрим на этот код в самом начале функции:
вы проверяете, что один из них меньше и подцепляете больший к меньшему в качестве левого ребенка теряя все что там было в левом поддереве. Это особенно странно, потому что ваш connectNodes может быть вызван для братьев, но при этом работает для них как-то не симметрично, если один из них меньше, то вы тут же возвращаетесь из функции, а если другой меньше то вы идете в цикл.
Перед тем как заниматься сравнением производительности, не могли бы вы показать более или менее формально, что:
1. ваша структура данных вообще кооректно работает
2. что ваша асимптотика такая, как вы заявляете?
Я спорю не о том как написано у автора, а с вашим мнением, о том, что для бинарного поиска нужен массив — это не правда.
Про отсутствие элементов или порядка я ничего не говорил, только про отсутствие массива.
2. Что, не исключает индийский подход.
Я вам ничего давать не буду, как я уже сказал, я показываю вам слабость вашей аргументации, а вы пока только в штыки все воспринимаете.
Я указал вам на факт, что спрос на специалистов есть (не каких попало и не только крутых, а самых нормальных — разбирающихся в основах) как минимум в больших компаниях, откуда он берется, учитывая, что каждый год куча вузов выпускает кучу «программистов» по всему миру, для меня загадка. Но факт есть факт — специалистов не хватает.
Да с чего вы это взяли?
Итого всего 377 вакансий? Вам не кажется это число маленьким, чтобы делать на его основании какие-то выводы?
Вы, очевидно, не поняли мое утверждение, мое утвержджение — большие компании набирают специалистов (и не только классных) постоянно, не только когда у них открыласаь какая-то вакансия для классного спеца. Потому что классному специалисту (и это чуть более высокий уровень, чем умеет реализовать сортировку пузырьком — не великое достижение) работа в большой компании найдется. При условии, что он знаком с базовыми вещами и умеет свои мысли превращать в алгоритмы, а алгоритмы в код.
Если вы живете в Питере -> Красноярске -> Хабаровске, то может быть. А если вы живете в Дублине, то очень сомневаюсь.
Мне в первую очередь не нравится аргументация вашей своей позиции, на что я и пытаюсь обратить ваше внимание.
Может и яснее, но это своершенно другое утверждение по сравнению с:Кроме сомнительного использорвания принципов, у вас еще есть плохая привычка говорить за других (большинству хватает, где вы взяли эту информацию?) и использорвать взятые из воздуха числа (100-1000, сотни тысяч, откуда это?). И про спрос на серьезных кандидатов попадает в эту же кучу, большие компании практически не переставя ищут кандидатов, и не каких папало.
Среди моих утверждений не было:
1. только алгоритмические вопросы и никакие другие;
2. алгоритмическиме вопросы работают для всех;
Среди моих утверждений было:
1. нет ничего плохого в попытке оценить мысленный процесс;
2. нет ничего плохого в использовании алгоритмических вопросов для оценки мысленного процесса;
3. алгоритмические задачи встречаются в реальной жизни;
4. инженер — интеллектуальная работа, т. е. он должен уметь искать решение задач.