+

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

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

по моему это понимание и без CLRS читается на SO сразу же

а это зачем?

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

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

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

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

а зачем мне доказательство? я просто смотрю в вики average complexity

по моему это понимание и без CLRS читается на SO сразу же

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

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

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

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

а зачем мне доказательство? я просто смотрю в вики average complexity

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

дискуссия холиварная, и я буду настаивать на том, что большинству кодеров этих знаний просто не надо

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

Тогда может посоветуете ваши шпаргалки?

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

а вот в том то и едло, что это нафиг не сдалось многим

Всё-таки если часто будешь использовать, то запомнишь, но всё же

а зачем мне доказательство? я просто смотрю в вики average complexity

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

Тогда может посоветуете ваши шпаргалки?

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

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

я верю ему и так

дискуссия холиварная, и я буду настаивать на том, что большинству кодеров этих знаний просто не надо

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

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

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

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

а вот в том то и едло, что это нафиг не сдалось многим

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

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

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

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

ну сейчас мы такую грань ещё проведём. Очень тонко идём

Тогда может посоветуете ваши шпаргалки?

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

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

кто-то должен сайтики делать. И это тоже програмисты

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

кто-то должен сайтики делать. И это тоже програмисты

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

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

ну тогда прдумай своё разграничение. Вскоре, вангую, таки разграничат. Но пока что мы имеем то, что имеем

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

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

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

Так это уже вроде не квиксорт, а разновидность, где pivot выбирается случайно?

Или я туплю? О.о

ну тогда прдумай своё разграничение. Вскоре, вангую, таки разграничат. Но пока что мы имеем то, что имеем

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

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

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

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

А все, понял

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

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

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

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

Имеется ввиду дерево построенное на основе случайных данных

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

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

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

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

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

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

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

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

Имеется ввиду дерево построенное на основе случайных данных

Я прав? Просвятите новичка в алгоритмах)

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

... tree generated from a random insertion order.

Понял

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

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

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

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

А в чём заключается проблема? Compile error или в ран тайме чудит?

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

А в чём заключается проблема? Compile error или в ран тайме чудит?

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

Как вариант можно попробовать скомпилировать разными компиляторами и проверить реузультат.

https://godbolt.org

ERROR: S client not available

gcc?

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

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

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

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

А если этот код отдельно взять? Если отрубить оптимизации?

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

This

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

А если этот код отдельно взять? Если отрубить оптимизации?

Для начала так попробуй.

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

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

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

ок, спасибо

ок, спасибо

valgrind-ом ещё прочекай

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

Может где-то выходишь за пределы массива и т.п., memory corruption вообщем

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

Впервые слышу

https://github.com/google/sanitizers/blob/master/README.md круто

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

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

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

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

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

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

Что ещё интересного есть? Помимо asan

Что ещё интересного есть? Помимо asan

Tsan, ubsan

asan + valgrind/dr memory теюе хватит. Есть ещё heaptrack

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

Ну охренеть, давайте ещё!

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

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

Разберусь.

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

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

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

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

в общем случае валгринд шумнее и больше false positives

@berkus я про гитхаб вчера говорил

если асан совсем не ловит, тогда можно провалгриндить

@berkus я про гитхаб вчера говорил

а ок