Я книги по алгоритмам воспринимаю исключительно как справочники.

+

Я книги по алгоритмам воспринимаю исключительно как справочники.

CLRS особенна тем, что в ней больше упор на методики построения алгоритмов, а не на конкретные алгоритмы

Таки да. Не факт, правда, что это хорошо.

CLRS особенна тем, что в ней больше упор на методики построения алгоритмов, а не на конкретные алгоритмы

Кинь сюда книгу. И пометь тегами)

у нас даже js-макак так интервьюируют, можем чебе позволить)

достаточно, чтобы эти знания были критическими для моей работы

Зависит от области. Я работаю на двух работах на одинаковой должности. На одной алгоритмы не нужны никогда, на другой - каждый второй день.

достаточно, чтобы эти знания были критическими для моей работы

разумеется, это так далеко не в любом проекте и роли

общее понимание надо иметь всё равно

хотя бы отличия в space и time complexity

ну вот ты умеешь объяснять, как и почему вставка в вектор - именно такая по времени, как она есть?

Знать историю алгоррттмов

ну вот ты умеешь объяснять, как и почему вставка в вектор - именно такая по времени, как она есть?

Еще спроси сколько форич сета работает)

вот CLRS дает инструменты, чтобы такое понимание было, и как аналогические вещи в других алгоритмах понимать

Еще спроси сколько форич сета работает)

например)

А average-case quicksort-а?

ну вот ты умеешь объяснять, как и почему вставка в вектор - именно такая по времени, как она есть?

Если не изменяент память, вся ссуть в реаллоке и переприсваивании со смещением, верно?

Мне не нравится наличие значения плохо

Срсли? Там весьма нетривиальное доказательство.

чтобы знать когда остановиться)

Срсли? Там весьма нетривиальное доказательство.

Хм... лол щито

ответа на SO хватит на понимание одного конкретного примера (вектор), а не общего принципа

дискуссия интересная, но я спать - 2 часа ночи(

Срсли? Там весьма нетривиальное доказательство.

Совершенно очевидно, что средняя высота дерева логарифм

чтобы уметь в голове прикинуть время работы аналогичного алгоритма

Так можно луучше понять что автор прав в оценке

у кнута неплохая

кодерам - вообще не надо, в отличии от инженеров

Совершенно очевидно, что средняя высота дерева логарифм

Это во-первых не очевидно, и скорее всего неправда, а во-вторых, будь это даже так где доказательство что квиксорт именно так поступает?

программирование вообще не особо нужно многим

Вот тебя я и ждал. Расскажи

https://yandex.ru/search/?text=виртуальные%20функции%20с%2B%2B

Просто нужно понимать специфику задачт

Вот кормена почитать, напримернапример

я лично - против такого широкого термина "программист". Только путаницу вносит

Это во-первых не очевидно, и скорее всего неправда, а во-вторых, будь это даже так где доказательство что квиксорт именно так поступает?

Квиксорт очевидно строит случайное дерево, а случайно дерево очевидно имеет логарифмическую высоту хотя бы по форме чисел каталана

да уже есть, де-факто

просто пока все по-своему эти категории называют

Квиксорт очевидно строит случайное дерево, а случайно дерево очевидно имеет логарифмическую высоту хотя бы по форме чисел каталана

логарифмическая высота у бинарных деревьев только если они сбалансированны, куда вероятнее построить несбалансированное дерево. Так что случайно построенное бинарное дерево вовсе не факт что имеет логарифмическую высоту.

Скорее всего даже наоборот. Чтобы аккуратно ответить на этот вопрос, надо посчитать матожидание выосты бинарного дерева.

Сильно сомневаюсь, что это будет функция от log(n)

логарифмическая высота у бинарных деревьев только если они сбалансированны, куда вероятнее построить несбалансированное дерево. Так что случайно построенное бинарное дерево вовсе не факт что имеет логарифмическую высоту.

таки имеет, как раз в Кормене разбирается, кажется

таки имеет, как раз в Кормене разбирается, кажется

Допускаю, но это надо очень аккуратно показать, и честно посчитать.

логарифмическая высота у бинарных деревьев только если они сбалансированны, куда вероятнее построить несбалансированное дерево. Так что случайно построенное бинарное дерево вовсе не факт что имеет логарифмическую высоту.

Случайное бинарное дерево очевидно имеет логарифмическую высоту, говорю, посмотрите на форму чисел Каталана

Квиксорт очевидно строит случайное дерево, а случайно дерево очевидно имеет логарифмическую высоту хотя бы по форме чисел каталана

То что что-то происходит случайно, не значит, что происходит равномерно.

Случайное бинарное дерево очевидно имеет логарифмическую высоту, говорю, посмотрите на форму чисел Каталана

Что значит «форма чисел» ?

https://en.wikipedia.org/wiki/Random_binary_tree#The_longest_path

Хотя с числами каталана я нагнал, видимо. Это другое распределение жи

Емнип Каталан — это проивзольные деревья, не только бинарные.

https://en.wikipedia.org/wiki/Random_binary_tree#The_longest_path

это не про uniform distribution на бинарных деревьях, правда, но в qsort'е должно получаться именно такое же распределение

Емнип Каталан — это проивзольные деревья, не только бинарные.

именно бинарные

(()()())

отвечает вершине с тремя потомками

Короче с деревьями никаких подводных камней никогда

Как не генерь рандомом логарифм высоты)

всем привет, пытаюсь портировать прогу с мака на линукс, не совсем корректно работает, есть подозрения в этой штуке: template< class T > T& getData( T* ) { return *(T*)(&m_data); }, пробовал через reinterpret_cast, не помогло. как еще можно это преобразовать?

именно бинарные

Каталан бинарные с точностью до изоморфизма. Так что там гораздо меньше деревьев большой высоты.

Как не генерь рандомом логарифм высоты)

Возрастабщая последовательность?)

Ноэто маловероятно на случайных

это не про uniform distribution на бинарных деревьях, правда, но в qsort'е должно получаться именно такое же распределение

Я бы предложил заглянуть в самого же Кормена чтобы посмотреть ка ктам оценивается сложность квиксорта (если там вообще есть)

Там правда не всё так просто.

Возрастабщая последовательность?)

Ну если я буду пихать случайную возрастающую последовательность, то да xD

Вы не можете гарантировать что случайный выбор на каждом подотрезке pivot-а в среднем действительно даёт нужную сложность. Все доказательства которые мне известны привлекают немного из теорвера.

в ран-тайме, тесты не так проходят

пробовал на разных gcc & clang, результат одинаковый

всем привет, пытаюсь портировать прогу с мака на линукс, не совсем корректно работает, есть подозрения в этой штуке: template< class T > T& getData( T* ) { return *(T*)(&m_data); }, пробовал через reinterpret_cast, не помогло. как еще можно это преобразовать?

Без контекста сложно сказать законно ли это вообще.

Без контекста сложно сказать законно ли это вообще.

This

Что именноты пытаешься сделать и как тестируешь

оптимизация -O0, можно попробовать отдельно просмотреть, просто контекст достаточно большой( в gdb просматриваю, есть негативные значения, которых быть не должно, подозрение на плохое кастование пока попробую действительно отдельные части прогнать, сложно все нюансы вам вытащить, чтобы понятнее было)

Ну вообще это должен быть реинтерпрет каст если ты эту область памяти пытаешься считать другим типом

https://github.com/berkus/libarsenal/blob/work/include/arsenal/byte_array.h я сделал возврат пойнтера который потом можно дерефнуть если надо см. as()

ок, спасибо

Валгринд не нужен, есть asan

Валгринд не нужен, есть asan

у меня была ситуация когда валгринд не ловил

Валгринд не нужен, есть asan

но согласен, asan сначала лучше

+1. valgrind хуже ловит, чем asan

Tsan, ubsan

см все санитайзеры :) Они все хороши

С этими разберись сначала

+1. valgrind хуже ловит, чем asan

но было и обратное

но было и обратное

Давно? Я перу месяцев назад наталкивался на то, что валгринд не ловил. Версии санийтазеров и валгринда были сеженькие