Реактивность
Этот пост я бы хотел посвятить понятию реактивности в программировании. Как и многие другие понятия, оно основано на устоявшихся процессах в природе и других областях человеческой жизни, например, в медицине.
«Реактивность – (от латинского reactia – противодействие) – свойство организма реагировать изменениями жизнедеятельности на воздействие различных факторов окружающей среды» - учебно-методическое пособие по медицине.
Реактивное программирование - парадигма, ориентированная на потоки данных и автоматическое распространение изменений от нижестоящих моделей к вышестоящим.
Рассмотрим пример:
1.
2.
3.
4.
В императивном программировании ожидается, что
В реактивном программировании ожидается, что значения выражений будут равны:
Лучше понять этот пример можно, если представить что в качестве значения каждой переменной используются не просто числа, а лямбда-функции: https://compiler-explorer.com/z/Ge589afdW
Давайте подумаем, какие преимущества дает данное свойство реактивности:
1. Удобное распространение изменений
Разработчику не нужно проверять изменения каждой переменной, т.к. в механизм изменений заложено предсказуемое поведение.
2. Высокая отзывчивость
Изменения распространяются сразу, как только было сделано изменение, а результат вычислений будет вычислен тогда, когда он понадобится (в отличие от каких-то механизмов пересчета изменений).
3. Масштабируемость
Достаточно изменить лишь какую-то часть алгоритма, чтобы добавить новую функциональность.
4. Удобное создание сложных алгоритмов обработки
Алгоритм обработки не требует полного пересоздания с нуля, а может усложняться там, где это удобнее всего сделать.
Конечно, использование функций, это не самый эффективный способ, но он наглядно демонстрирует идею реактивности. Это понимание мне понадобится, чтобы обосновать некоторые другие идеи, о которых я хочу рассказать в следующих постах.
#howitworks #fun
Этот пост я бы хотел посвятить понятию реактивности в программировании. Как и многие другие понятия, оно основано на устоявшихся процессах в природе и других областях человеческой жизни, например, в медицине.
«Реактивность – (от латинского reactia – противодействие) – свойство организма реагировать изменениями жизнедеятельности на воздействие различных факторов окружающей среды» - учебно-методическое пособие по медицине.
Реактивное программирование - парадигма, ориентированная на потоки данных и автоматическое распространение изменений от нижестоящих моделей к вышестоящим.
Рассмотрим пример:
1.
b = 3; c = 5;2.
a = b + c;3.
b = c;4.
c = 2;В императивном программировании ожидается, что
a = 8; b = 5; c = 2;, т.к. при вычислении результата каждой операции используется значение переменной на текущий момент исполнения.В реактивном программировании ожидается, что значения выражений будут равны:
a = 4; b = 2; c = 2;, т.е. изменения, примененные к нижестоящим моделям (в данном контексте, переменные b и c), автоматически распространят свои изменения на вышестоящие модели (переменные a и b). Получаются такие цепочки зависимостей c -> a и c -> b -> a. Лучше понять этот пример можно, если представить что в качестве значения каждой переменной используются не просто числа, а лямбда-функции: https://compiler-explorer.com/z/Ge589afdW
Давайте подумаем, какие преимущества дает данное свойство реактивности:
1. Удобное распространение изменений
Разработчику не нужно проверять изменения каждой переменной, т.к. в механизм изменений заложено предсказуемое поведение.
2. Высокая отзывчивость
Изменения распространяются сразу, как только было сделано изменение, а результат вычислений будет вычислен тогда, когда он понадобится (в отличие от каких-то механизмов пересчета изменений).
3. Масштабируемость
Достаточно изменить лишь какую-то часть алгоритма, чтобы добавить новую функциональность.
4. Удобное создание сложных алгоритмов обработки
Алгоритм обработки не требует полного пересоздания с нуля, а может усложняться там, где это удобнее всего сделать.
Конечно, использование функций, это не самый эффективный способ, но он наглядно демонстрирует идею реактивности. Это понимание мне понадобится, чтобы обосновать некоторые другие идеи, о которых я хочу рассказать в следующих постах.
#howitworks #fun
Копаемся в маллоке
Короче. Попробуем новый формат на канале - статьи. Вот пожалуйста ссылочка https://telegra.ph/Nahodim-razmer-bloka-malloc-11-30. Это продолжение песни, начатой здесь. Инфы там многовато, поэтому пришлось в немного более длинном формате ее упаковать.
Было прикольно немного поисследовать вопрос, лично я кайфанул во время писания статьи.
Пишите свои мысли по поводу вопроса. Буду рад пообсуждать в комментах.
You are the best.
#fun #howitworks #memory #goodoldc #hardcore
Короче. Попробуем новый формат на канале - статьи. Вот пожалуйста ссылочка https://telegra.ph/Nahodim-razmer-bloka-malloc-11-30. Это продолжение песни, начатой здесь. Инфы там многовато, поэтому пришлось в немного более длинном формате ее упаковать.
Было прикольно немного поисследовать вопрос, лично я кайфанул во время писания статьи.
Пишите свои мысли по поводу вопроса. Буду рад пообсуждать в комментах.
You are the best.
#fun #howitworks #memory #goodoldc #hardcore
Telegraph
Находим размер блока malloc
Недавно рассказывал в общих чертах про то, как malloc на самом деле аллоцирует память. Попробуем теперь самостоятельно найти нужную циферку. Почти очевидно, что размер должен храниться с отрицательным смещением от указателя на начало блока. Размер ведь динамический…
Как обмануть nodiscard?
В комментах к предыдущему посту Евгений правильно заметил, что аттрибут nodiscard можно заигнорировать. Правда непонятны кейсы, в которых это нужно делать и которые еще не притянутые были бы за уши. Думаю, что при корректном использовании атрибута, такой надобности не возникнет. Ну да ладно. Об этом мы поговорим попозже. Сейчас я перечислю некоторые способы обхода nodiscard, чисто из научного интереса. Предупреждаю сразу. Уберите маленьких детей от экрана и ни в коем случае не повторять дома. За последствия не отвечаю.
std::ignore. На этот вариант и ссылался Евгений. Суть в том, что этому безтиповому можно присвоить любое значение и не использовать его. Тогда и возвращаемое значение типа было использовано для преобразования в ignore, и мы потом этот ignore можем игнорировать. Подробнее тут. А для любителей покопаться в костях динозавров есть функция boost::ignore_unused.
Скастовать возвращаемое значение в void. Типа вот так: (void)someFunction(). Или более по-плюсовому co static_cast.
Присвоить возращаемое значение какому-то объекту. Но не использовать его.
Тогда появится варнинг, что переменная, которой мы присвоили возвращаемое значение, не используется нигде. А вот чтобы это обойти, нужно пометить эту переменную другим атрибутом [[maybe_unused]]. Например так: [[maybe_unused]] int i = foo ();
Сделать красивую шаблонную обертку над предыдущим пунктом, с variadic-templates и прочими радостями. И назвать ее discard.
Отличные новости для пользователей clang! Можно обернуть вызов функции в
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Weverything"
#endif
func_with_result();
#pragma clang diagnostic pop
#endif
Тогда и никаких варнингов генерироваться не будет. Для gcc есть что-то подобное, но там нельзя вроде все сразу отключить.
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-result"
func_with_result();
#pragma GCC diagnostic pop
На этом моя фантазия кончилась. Но получилось все равно солидно)
Повторю, что в большинстве случаев вы этим будете стрелять себе в лицо, и это скорее всего признак того, что вы что-то делаете не так или система спроектирована плохо.
Возможно вы знаете какие-нибудь еще способы? Обязательно делитесь ими в комментариях)
Stay dangerous. Stay cool.
#fun #cpp17 #compiler
В комментах к предыдущему посту Евгений правильно заметил, что аттрибут nodiscard можно заигнорировать. Правда непонятны кейсы, в которых это нужно делать и которые еще не притянутые были бы за уши. Думаю, что при корректном использовании атрибута, такой надобности не возникнет. Ну да ладно. Об этом мы поговорим попозже. Сейчас я перечислю некоторые способы обхода nodiscard, чисто из научного интереса. Предупреждаю сразу. Уберите маленьких детей от экрана и ни в коем случае не повторять дома. За последствия не отвечаю.
std::ignore. На этот вариант и ссылался Евгений. Суть в том, что этому безтиповому можно присвоить любое значение и не использовать его. Тогда и возвращаемое значение типа было использовано для преобразования в ignore, и мы потом этот ignore можем игнорировать. Подробнее тут. А для любителей покопаться в костях динозавров есть функция boost::ignore_unused.
Скастовать возвращаемое значение в void. Типа вот так: (void)someFunction(). Или более по-плюсовому co static_cast.
Присвоить возращаемое значение какому-то объекту. Но не использовать его.
Тогда появится варнинг, что переменная, которой мы присвоили возвращаемое значение, не используется нигде. А вот чтобы это обойти, нужно пометить эту переменную другим атрибутом [[maybe_unused]]. Например так: [[maybe_unused]] int i = foo ();
Сделать красивую шаблонную обертку над предыдущим пунктом, с variadic-templates и прочими радостями. И назвать ее discard.
Отличные новости для пользователей clang! Можно обернуть вызов функции в
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Weverything"
#endif
func_with_result();
#pragma clang diagnostic pop
#endif
Тогда и никаких варнингов генерироваться не будет. Для gcc есть что-то подобное, но там нельзя вроде все сразу отключить.
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-result"
func_with_result();
#pragma GCC diagnostic pop
На этом моя фантазия кончилась. Но получилось все равно солидно)
Повторю, что в большинстве случаев вы этим будете стрелять себе в лицо, и это скорее всего признак того, что вы что-то делаете не так или система спроектирована плохо.
Возможно вы знаете какие-нибудь еще способы? Обязательно делитесь ими в комментариях)
Stay dangerous. Stay cool.
#fun #cpp17 #compiler
Терминал
Вот иногда живешь-живешь, учишь иностранный язык или в какую-то другую сферу погружаешься, и в какой-то момент тебе приходит озарение по поводу ориджина простых вещей, которые мы все принимаем как данность. Например, слово банкнота. Для нас это одна единица бумажных денег. И мы не задумываемся, почему это слово обозначает одну деньгу. А все просто. Записка из банка. Bank note. Взорвало мозг? Если нет, то вы либо очень умный, либо потеряли энтузиазм к жизни.
Хочу поделиться с вами похожим приколом только из мира computer science. Думаю, что все мы хоть раз в жизни открывали графический терминал на своих Unix системах(реальных или виртуальных), ну или хотя бы подключались удалённо к ним. Все-таки, знание команд для unix - это маст хэв и де факто стандарт для сферы разработки. Если вы хоть раз разрабатывали не локально, то с 99% вероятности вы подключались к Линукс системе и ей надо бы уметь управлять.
Ну дак вот. Помните, какие раньше были компьютеры? Я вот тоже не помню, потому застал время уже полностью персональных компьютеров, где все было соединено вместе. А лет 50 назад нормальной практикой в компании было иметь один здоровый ЭВМ, размером с самомнение веганов, и много-много отдельных «терминалов», через которые сотрудники могли общаться с эвм. Они имели клавиатуру, дисплей, печатающее устройство, динамик и ещё пару простых прибамбасов. Пользователь вводит команду, команда по проводам попадает в эвм, обрабатывается и передаётся в виде текстовой или графической информации на терминал.
Мы сейчас делаем тоже самое, только виртуально. Открываем окошко, через которое управляем системой. Правда все мы воспринимаем это как данность и как обыкновенный, так и задуманный способ взаимодействия с компьютером. Терминал - это симулякр в чистом виде.
Надеюсь, что вас удивило мое недавнее открытие и это сделало ваш день немного приятнее.
Stay surprised. Stay cool.
#fun #tools #OS
Вот иногда живешь-живешь, учишь иностранный язык или в какую-то другую сферу погружаешься, и в какой-то момент тебе приходит озарение по поводу ориджина простых вещей, которые мы все принимаем как данность. Например, слово банкнота. Для нас это одна единица бумажных денег. И мы не задумываемся, почему это слово обозначает одну деньгу. А все просто. Записка из банка. Bank note. Взорвало мозг? Если нет, то вы либо очень умный, либо потеряли энтузиазм к жизни.
Хочу поделиться с вами похожим приколом только из мира computer science. Думаю, что все мы хоть раз в жизни открывали графический терминал на своих Unix системах(реальных или виртуальных), ну или хотя бы подключались удалённо к ним. Все-таки, знание команд для unix - это маст хэв и де факто стандарт для сферы разработки. Если вы хоть раз разрабатывали не локально, то с 99% вероятности вы подключались к Линукс системе и ей надо бы уметь управлять.
Ну дак вот. Помните, какие раньше были компьютеры? Я вот тоже не помню, потому застал время уже полностью персональных компьютеров, где все было соединено вместе. А лет 50 назад нормальной практикой в компании было иметь один здоровый ЭВМ, размером с самомнение веганов, и много-много отдельных «терминалов», через которые сотрудники могли общаться с эвм. Они имели клавиатуру, дисплей, печатающее устройство, динамик и ещё пару простых прибамбасов. Пользователь вводит команду, команда по проводам попадает в эвм, обрабатывается и передаётся в виде текстовой или графической информации на терминал.
Мы сейчас делаем тоже самое, только виртуально. Открываем окошко, через которое управляем системой. Правда все мы воспринимаем это как данность и как обыкновенный, так и задуманный способ взаимодействия с компьютером. Терминал - это симулякр в чистом виде.
Надеюсь, что вас удивило мое недавнее открытие и это сделало ваш день немного приятнее.
Stay surprised. Stay cool.
#fun #tools #OS
Вызываем метод класса через указатель
Настоящего плюсовика не должны пугать указатели на функции. И хоть в С++ есть нормальная обертка над всеми сущностями, которые можно исполнить - std::function - она довольно тяжеловесная и медленная. Да и с сишным апи с ней не поработаешь. К чему это я. Да. Указатели на функции. С ними, в целом, все просто.
int func() {
return 1;
}
using func_ptr = int (*) ();
func_ptr ptr = func;
std::cout << ptr();
Этот код со всеми обертками должен написать единичку на экран. С более сложными функциями сделать что-то похожее не составит труда. Но вот как насчет методов класса? Можно ли вызвать метод класса через указатель на него, а не через объект?
Ответ - можно. Но прежде чем посмотреть на рабочий код, попробуйте сами это сделать. Уверяю, что это не так тривиально)
Если читаете с телефона или нет времени, лучше вернитесь к этому посту после того, как попробуете сами. Эмоции будут совершенно другие)
Ну а для тех, кто уже попробовал или для ленивых дяденек, продолжаю.
Первое, что приходит на ум - такой же подход, как и с функциями.
auto ptr = RandomType::MemberFunction;
И тут же гцц плюнет вам в лицо с фразой error: invalid use of non-static member function ‘void RandomType::MemberFunction()’
auto ptr = RandomType::MemberFunction;
На этом я и закончил пробовать и пошел ресерчить. А снизу код, который у меня получился по итогам моих поисков. Все в духе С, ничего не понятно, одни указатели. Выглядит как фокус и по факту им и является. В следующий раз объясню, почему все так.
Stay hardcore. Stay cool.
#fun #hardcore #memory #cppcore
Настоящего плюсовика не должны пугать указатели на функции. И хоть в С++ есть нормальная обертка над всеми сущностями, которые можно исполнить - std::function - она довольно тяжеловесная и медленная. Да и с сишным апи с ней не поработаешь. К чему это я. Да. Указатели на функции. С ними, в целом, все просто.
int func() {
return 1;
}
using func_ptr = int (*) ();
func_ptr ptr = func;
std::cout << ptr();
Этот код со всеми обертками должен написать единичку на экран. С более сложными функциями сделать что-то похожее не составит труда. Но вот как насчет методов класса? Можно ли вызвать метод класса через указатель на него, а не через объект?
Ответ - можно. Но прежде чем посмотреть на рабочий код, попробуйте сами это сделать. Уверяю, что это не так тривиально)
Если читаете с телефона или нет времени, лучше вернитесь к этому посту после того, как попробуете сами. Эмоции будут совершенно другие)
Ну а для тех, кто уже попробовал или для ленивых дяденек, продолжаю.
Первое, что приходит на ум - такой же подход, как и с функциями.
auto ptr = RandomType::MemberFunction;
И тут же гцц плюнет вам в лицо с фразой error: invalid use of non-static member function ‘void RandomType::MemberFunction()’
auto ptr = RandomType::MemberFunction;
На этом я и закончил пробовать и пошел ресерчить. А снизу код, который у меня получился по итогам моих поисков. Все в духе С, ничего не понятно, одни указатели. Выглядит как фокус и по факту им и является. В следующий раз объясню, почему все так.
Stay hardcore. Stay cool.
#fun #hardcore #memory #cppcore
Продолжение про вызов метода через указатель
В прошлом мы выяснили, как можно вызвать нестатический метод класса через указатель. Пост с кодом находится здесь. Для удобства, прикреплю его и к сюда. Сегодня мы попробуем разобраться, почему код такой и он еще и рабочий? Пойдем по порядку. Совсем тривиальные вещи затрагиваться не будут, будут только важные в контексте объяснения.
18 строка - Объявляется синоним к типу указателя на функцию, которая ничего не возвращает и принимает указатель на тип RandomType. Позже будет понятно, зачем это нужно.
19 строка - Есть 2 возможных синтаксиса для получения указателя на функцию: с амперсантом(сюрприз, кто не знал) и без. Без амперсанта не работает, потому такой синтаксис уже используется для вызова статических методов и будет путаница. Итак, мы получили какого-то неизвестного нам типа указатель на функцию. Идем дальше.
20 строка - Это трюк, который позволяет превратить указатель на функцию в указатель на число. Это необходимо для того, чтобы скастовать указатель _ptr из 19 строки к указателю на функцию типа func_ptr. Такого рода касты очень опасные и ведут к неопределенному поведению. Поэтому компиляторы просто их запрещают. Поэтому и нужно какое-то прокси состояние. Только компиляторы также запрещают кастовать указатель на функцию к указателю на число. Поэтому в ход идет наращивание индирекции указателя.
Мы можем посмотреть не на сам указатель, а на ячейку памяти, которая хранит наш указатель. И сказать, что по этому адресу лежит не указатель на функцию, а указатель на число. Вот так сделать можно. А потом кастуем указатель на число к указателю на функцию. Так тоже можно сделать.
И, наконец, важнейший пункт. Помните в книжках всегда говорили, что в методы скрытно передается указатель на вызывающий его объект this? Так вот сейчас вам скорее всего впервые понадобится это знание на практике!
Методы неполиморфных классов - те же самые обычные функции(кто не знал). От остальных их отличает лишь этот параметр this, который скрытно передается первым аргументом. Именно поэтому, чтобы вызвать нестатический метод, нам нужен объект. Чтобы передать его первым параметром в функцию. Иначе вызов будет не соответствовать сигнатуре.
Поэтому мы берем созданный на стеке объект, находим адрес первого байта и передаем его в метод в качестве аргумента.
И вуаля. Все работает. Выводится пятёрочка.
Кто понял, тот понял. Кто не понял - сорян, я сделал, что мог. Но есть хорошая новость - эту задачу можно решить и более щедящим способом, хоть и не таким элегантным с точки зрения важности первого аргумента. В будущем разберем его.
Из этого поста надо вынести главное: ООП - лишь абстракция над более примитивными и низкоуровневыми конструкциями. Уметь оперировать абстракциями - полезнейший навык в нашем мире. Чем более сложные абстракции ты обрабатываешь, тем больше понимаешь мир и эффективнее решаешь задачи. Однако знать те самые кирпичики, на которых строятся сложные конструкции - не менее важная вещь. Только полная картина мира дает полное понимание происходящего.
Конструируй абстракции и погружайся в детали. Stay cool.
#fun #memory #howitworks #cppcore #hardcore
В прошлом мы выяснили, как можно вызвать нестатический метод класса через указатель. Пост с кодом находится здесь. Для удобства, прикреплю его и к сюда. Сегодня мы попробуем разобраться, почему код такой и он еще и рабочий? Пойдем по порядку. Совсем тривиальные вещи затрагиваться не будут, будут только важные в контексте объяснения.
18 строка - Объявляется синоним к типу указателя на функцию, которая ничего не возвращает и принимает указатель на тип RandomType. Позже будет понятно, зачем это нужно.
19 строка - Есть 2 возможных синтаксиса для получения указателя на функцию: с амперсантом(сюрприз, кто не знал) и без. Без амперсанта не работает, потому такой синтаксис уже используется для вызова статических методов и будет путаница. Итак, мы получили какого-то неизвестного нам типа указатель на функцию. Идем дальше.
20 строка - Это трюк, который позволяет превратить указатель на функцию в указатель на число. Это необходимо для того, чтобы скастовать указатель _ptr из 19 строки к указателю на функцию типа func_ptr. Такого рода касты очень опасные и ведут к неопределенному поведению. Поэтому компиляторы просто их запрещают. Поэтому и нужно какое-то прокси состояние. Только компиляторы также запрещают кастовать указатель на функцию к указателю на число. Поэтому в ход идет наращивание индирекции указателя.
Мы можем посмотреть не на сам указатель, а на ячейку памяти, которая хранит наш указатель. И сказать, что по этому адресу лежит не указатель на функцию, а указатель на число. Вот так сделать можно. А потом кастуем указатель на число к указателю на функцию. Так тоже можно сделать.
И, наконец, важнейший пункт. Помните в книжках всегда говорили, что в методы скрытно передается указатель на вызывающий его объект this? Так вот сейчас вам скорее всего впервые понадобится это знание на практике!
Методы неполиморфных классов - те же самые обычные функции(кто не знал). От остальных их отличает лишь этот параметр this, который скрытно передается первым аргументом. Именно поэтому, чтобы вызвать нестатический метод, нам нужен объект. Чтобы передать его первым параметром в функцию. Иначе вызов будет не соответствовать сигнатуре.
Поэтому мы берем созданный на стеке объект, находим адрес первого байта и передаем его в метод в качестве аргумента.
И вуаля. Все работает. Выводится пятёрочка.
Кто понял, тот понял. Кто не понял - сорян, я сделал, что мог. Но есть хорошая новость - эту задачу можно решить и более щедящим способом, хоть и не таким элегантным с точки зрения важности первого аргумента. В будущем разберем его.
Из этого поста надо вынести главное: ООП - лишь абстракция над более примитивными и низкоуровневыми конструкциями. Уметь оперировать абстракциями - полезнейший навык в нашем мире. Чем более сложные абстракции ты обрабатываешь, тем больше понимаешь мир и эффективнее решаешь задачи. Однако знать те самые кирпичики, на которых строятся сложные конструкции - не менее важная вещь. Только полная картина мира дает полное понимание происходящего.
Конструируй абстракции и погружайся в детали. Stay cool.
#fun #memory #howitworks #cppcore #hardcore
Вызов метода через указатель на метод
В прошлых постах тут и тут мы поговорили о том, как можно вызвать публичный метод класса, используя указатель на функцию.
Я обещал упомянуть еще один способ вызова метода через указатель. Более элегантный, но менее хардкорный.
И его на самом деле уже проспойлерил Александр, причем сразу же во время публикации первого поста из серии. Все-таки в нашем канале сидят крутые спецы)
Суть в том, что есть специальный синтаксис для определения именно что указателя на метод. Делается это так:
using fnptr = void (RandomType::*)();
В этом объявлении синонима явно указывается, что это указатель на метод конкретного класса RandomType. И вызывается конкретный экземпляр этого метода через объект и оператор точка. И все. Никаких танцев с бабнами и прочих шалостей. В общем, все можете посмотреть в коде на картинке.
Почему я думаю, что метод менее хардкорный? Потому что здесь указатель подразумевается именно как указатель на метод и вызывается он похожим образом. В прошлых постах я хотел показать, что под капотом зашито и что на самом деле представляют из себя методы классов.
Stay versatile. Stay cool.
#fun #cppcore
В прошлых постах тут и тут мы поговорили о том, как можно вызвать публичный метод класса, используя указатель на функцию.
Я обещал упомянуть еще один способ вызова метода через указатель. Более элегантный, но менее хардкорный.
И его на самом деле уже проспойлерил Александр, причем сразу же во время публикации первого поста из серии. Все-таки в нашем канале сидят крутые спецы)
Суть в том, что есть специальный синтаксис для определения именно что указателя на метод. Делается это так:
using fnptr = void (RandomType::*)();
В этом объявлении синонима явно указывается, что это указатель на метод конкретного класса RandomType. И вызывается конкретный экземпляр этого метода через объект и оператор точка. И все. Никаких танцев с бабнами и прочих шалостей. В общем, все можете посмотреть в коде на картинке.
Почему я думаю, что метод менее хардкорный? Потому что здесь указатель подразумевается именно как указатель на метод и вызывается он похожим образом. В прошлых постах я хотел показать, что под капотом зашито и что на самом деле представляют из себя методы классов.
Stay versatile. Stay cool.
#fun #cppcore
Удобное представление чисел
Всем привет! Хочу рассказать про небольшую подсказку, которая сделает ваш код понятнее как для себя, так и для других.
Часто замечаю, что когда пишется длинная численная константа, она выглядит как куча-мала и требует внимательного прочтения:
При беглом чтении кода преимущественно хочется хотя бы быстро определить порядок этого числа.
При программировании, например, FPGA приходится использовать задокументированные численные константы к конкретной железке. Очень часто их пишут в двоичной или шестнадцатеричной СИ:
Начиная с C++14 появилась поддержка бинарных литералов, которые позволяют делать вот так:
На мой взгляд, группировка на порядки или байты позволяет быстро и легко воспринимать код. Как говорится, разделяй и властвуй 😉
#cpp14 #goodpractice #fun
Всем привет! Хочу рассказать про небольшую подсказку, которая сделает ваш код понятнее как для себя, так и для других.
Часто замечаю, что когда пишется длинная численная константа, она выглядит как куча-мала и требует внимательного прочтения:
uint64_t speed = 299792458;
double size = 0.4315973;
При беглом чтении кода преимущественно хочется хотя бы быстро определить порядок этого числа.
При программировании, например, FPGA приходится использовать задокументированные численные константы к конкретной железке. Очень часто их пишут в двоичной или шестнадцатеричной СИ:
uint32_t SPI_hex_code = 0x374F0FB4;
uint16_t SPI_bin_code = 0b1000111110110100;
Начиная с C++14 появилась поддержка бинарных литералов, которые позволяют делать вот так:
// Binary literals since C++14
// Разделение на порядки
uint64_t speed = 299'792'458;
double size = 0.431'597'3;
// Разделение на октеты (байты)
uint32_t SPI_hex_code = 0x37'4F'0F'B4;
uint16_t SPI_bin_code = 0b10001111'10110100;
На мой взгляд, группировка на порядки или байты позволяет быстро и легко воспринимать код. Как говорится, разделяй и властвуй 😉
#cpp14 #goodpractice #fun
Можно ли явно вызывать деструктор объекта?
Вопрос скорее из категории "А что если?" и скорее всего большинство разработчиков не столкнуться с надобностью это делать. Однако менее интересным этот вопрос не становится, если немного глубже копнуть. А копаться в плюсах всегда интересно)
В целом, любой публичный метод может быть вызван снаружи. Поэтому ответ на вопрос - да, можно. Но вот какие у этого будут последствия?
Возьмем простую структурку
struct SomeDefaultDestructedType
{
SomeDefaultDestructedType(int b): a{b} {}
~SomeDefaultDestructedType() = default;
int getNumber() {return a;}
int a;
};
Как видим, у нее дефолтовый деструктор, то есть отдает генерацию кода для него в руки компилятора. А компилятор в этих вопросах тупой и прямолинейный. Для нетривиальных полей он вызывает деструкторы, а для тривиальных типов - ничего не делает. И все. Поэтому для нашего класса вызывали мы деструктор для объекта, не вызывали, значения не имеет. Даже можно вызвать метод getNumber после явного вызова деструктора и он вернет валидное значение. Семантически объект уничтожен, а на самом деле живее всех живых. Память для него на стеке есть, данные в этой области лежат, поэтому мы и можем оперировать им как полноценным объектом. И хорошо, если у класса все его поля будут рекурсивно default deconstructed, тогда мы ничего не сломает. Проблемы начинаются, когда класс имеет нетривиальный деструктор. Посмотрим на следующую структурку:
struct SomeNonTrivialDestructedType
{
SomeNonTrivialDestructedType(int b): a{new int(b)} {}
~SomeNonTrivialDestructedType() { delete a;}
int getNumber() {return *a;}
int * a;
};
Простенькое выделение и освобождение памяти в куче. Что будет сейчас при явном вызове деструктора? Ресурс освободится, а объект останется лежать на стеке. А что происходит с объектами, которые выделяются в автоматической области, при выходе из области их создания? У них вызывается деструктор. Поэтому будет двойное освобождение памяти. А если этот объект еще использовать как-то, например вызвать у него метод getNumber, это еще и неопределенное поведение, так как обращаемся к освобожденной памяти.
Для объектов, созданных в куче через new, проблема остается такой же. Потому что хорошей практикой разработки является вызывать delete на каждый выделенный с помощью new объект. А delete вызывает деструктор.
Да и вообще для любого класса с нетривиальным деструктором, явный вызов этого самого деструктора будет сопровождаться приведением объекта в неконсистентное состояние, когда объект семантически мертв, а на деле им можно еще пользоваться и его придется умертвить еще раз(самостоятельно через delete или автоматически при выходе из скоупа). Это может приводить к ошибкам самого широкого спектра, в зависимости от логики работы объекта.
Есть случаи, когда явный вызов деструктора оправдан, но это всегда связано с работой с памятью на низком уровне. Об этом поговорим как-нибудь в другой раз. А пока, если вам всерьез не приходила в голову мысль явно вызывать деструктор - и не нужно этого делать)
Stay safe. Stay cool.
#cppcore #fun #memory
Вопрос скорее из категории "А что если?" и скорее всего большинство разработчиков не столкнуться с надобностью это делать. Однако менее интересным этот вопрос не становится, если немного глубже копнуть. А копаться в плюсах всегда интересно)
В целом, любой публичный метод может быть вызван снаружи. Поэтому ответ на вопрос - да, можно. Но вот какие у этого будут последствия?
Возьмем простую структурку
struct SomeDefaultDestructedType
{
SomeDefaultDestructedType(int b): a{b} {}
~SomeDefaultDestructedType() = default;
int getNumber() {return a;}
int a;
};
Как видим, у нее дефолтовый деструктор, то есть отдает генерацию кода для него в руки компилятора. А компилятор в этих вопросах тупой и прямолинейный. Для нетривиальных полей он вызывает деструкторы, а для тривиальных типов - ничего не делает. И все. Поэтому для нашего класса вызывали мы деструктор для объекта, не вызывали, значения не имеет. Даже можно вызвать метод getNumber после явного вызова деструктора и он вернет валидное значение. Семантически объект уничтожен, а на самом деле живее всех живых. Память для него на стеке есть, данные в этой области лежат, поэтому мы и можем оперировать им как полноценным объектом. И хорошо, если у класса все его поля будут рекурсивно default deconstructed, тогда мы ничего не сломает. Проблемы начинаются, когда класс имеет нетривиальный деструктор. Посмотрим на следующую структурку:
struct SomeNonTrivialDestructedType
{
SomeNonTrivialDestructedType(int b): a{new int(b)} {}
~SomeNonTrivialDestructedType() { delete a;}
int getNumber() {return *a;}
int * a;
};
Простенькое выделение и освобождение памяти в куче. Что будет сейчас при явном вызове деструктора? Ресурс освободится, а объект останется лежать на стеке. А что происходит с объектами, которые выделяются в автоматической области, при выходе из области их создания? У них вызывается деструктор. Поэтому будет двойное освобождение памяти. А если этот объект еще использовать как-то, например вызвать у него метод getNumber, это еще и неопределенное поведение, так как обращаемся к освобожденной памяти.
Для объектов, созданных в куче через new, проблема остается такой же. Потому что хорошей практикой разработки является вызывать delete на каждый выделенный с помощью new объект. А delete вызывает деструктор.
Да и вообще для любого класса с нетривиальным деструктором, явный вызов этого самого деструктора будет сопровождаться приведением объекта в неконсистентное состояние, когда объект семантически мертв, а на деле им можно еще пользоваться и его придется умертвить еще раз(самостоятельно через delete или автоматически при выходе из скоупа). Это может приводить к ошибкам самого широкого спектра, в зависимости от логики работы объекта.
Есть случаи, когда явный вызов деструктора оправдан, но это всегда связано с работой с памятью на низком уровне. Об этом поговорим как-нибудь в другой раз. А пока, если вам всерьез не приходила в голову мысль явно вызывать деструктор - и не нужно этого делать)
Stay safe. Stay cool.
#cppcore #fun #memory
Сколько памяти вы можете аллоцировать?
Пару месяцев назад мы обсуждали, что будет, если маллокнуть 100 Гб памяти. Идея эксперимента мне понравилась, поэтому решил сделать что-то похожее. На этот раз я попробую в цикле на каждой итерации выделять по одному гигабайту памяти.
На этом месте я предлагаю вам задуматься, на какой итерации остановится цикл? Ну то есть, сколько всего памяти с смогу выделить таким образом?
Для конкретики определимся, что у меня на машине 64-битная Ubuntu c 21111872 кбайт оперативной памяти или ~21 Гб. И выделяю я, просто вызывая маллок, ничего больше. Память я также не освобождаю (ждал бы завершения эксперимента уже в гробу😵).
Тут есть несколько вариантов:
1️⃣ Система нам выделить 21 Гб и скажет гуляй хлопец дальше без меня.
2️⃣ У операционной системы есть какой-то внутренний лимит, больше или меньше реального количества доступной памяти, который зависит от количества доступной RAM, и при достижении вот этого лимита ОС откажется выдавать больше памяти.
3️⃣ Мы каким-то образом сможем использовать тот факт, что процессы оперируют с виртуальной памятью, которая по размерам намного больше доступной, и сможем выделить больше памяти, чем есть на самом деле.
В целом, все варианты имеют место быть. Но давайте перейдем уже к результатам. Они на картинке под постом.
Система смогла выделить 131 террабайт памяти для нас. 131 ТЕРРАБАЙТ, КАРЛ. Вы в шоке? Я в шоке. Все в шоке.
Это примерно в 2^12 раза больше, чем доступно на машине. Кто офигел - ставим лайкосик.
What the fuck is going on и откуда такие цифры взялись, разберем в следующих постах.
Stay in touch. Stay cool.
#fun #memory #hardcore
Пару месяцев назад мы обсуждали, что будет, если маллокнуть 100 Гб памяти. Идея эксперимента мне понравилась, поэтому решил сделать что-то похожее. На этот раз я попробую в цикле на каждой итерации выделять по одному гигабайту памяти.
На этом месте я предлагаю вам задуматься, на какой итерации остановится цикл? Ну то есть, сколько всего памяти с смогу выделить таким образом?
Для конкретики определимся, что у меня на машине 64-битная Ubuntu c 21111872 кбайт оперативной памяти или ~21 Гб. И выделяю я, просто вызывая маллок, ничего больше. Память я также не освобождаю (ждал бы завершения эксперимента уже в гробу😵).
Тут есть несколько вариантов:
1️⃣ Система нам выделить 21 Гб и скажет гуляй хлопец дальше без меня.
2️⃣ У операционной системы есть какой-то внутренний лимит, больше или меньше реального количества доступной памяти, который зависит от количества доступной RAM, и при достижении вот этого лимита ОС откажется выдавать больше памяти.
3️⃣ Мы каким-то образом сможем использовать тот факт, что процессы оперируют с виртуальной памятью, которая по размерам намного больше доступной, и сможем выделить больше памяти, чем есть на самом деле.
В целом, все варианты имеют место быть. Но давайте перейдем уже к результатам. Они на картинке под постом.
Система смогла выделить 131 террабайт памяти для нас. 131 ТЕРРАБАЙТ, КАРЛ. Вы в шоке? Я в шоке. Все в шоке.
Это примерно в 2^12 раза больше, чем доступно на машине. Кто офигел - ставим лайкосик.
What the fuck is going on и откуда такие цифры взялись, разберем в следующих постах.
Stay in touch. Stay cool.
#fun #memory #hardcore
Как система может выделить 131 Терабайт оперативы?
Здесь мы выясняли, сколько же памяти может нам выдать система. И ответ для многих оказался неожиданным. 131 тарабайт - в дохренальен раз больше, чем реальный объем RAM на тестовой машине. Понятное дело, что это фейковые терабайты, потому что их просто негде расположить. И если бы было хотя бы RAMx2, можно было бы еще поговорить про такие штуки, как файлы подкачки. Но здесь прям совсем ничего не сходится, поэтому погнали разбираться, что к чему. Повторю ремарку, что здесь я говорю про 64-битные системы.
Первая подсказка к ответу для вас - практически в точности такой же результат я получил на других своих машинах. Да и под тем постом @dtbeaver оставил скрин, что у него такие же цифры +- 2 Гб от того, что получил я. Значит этот предел - общий для, по крайней мере, большой группы линуксоидов с 64-битными системами. Это наводит на вопрос: а сколько вообще можно адресовать памяти? Может 131 Тб и есть это количество?
Вторая подсказка - выделилось на самом деле не 131(ох уж это эти десятичные приставки в двоичном мире...), а 128. До боли знакомое число...
Однажды на собесе меня спросили: сколько байт я могу адресовать в программе? И я ответил: 2^64 байт. Ну вот у нас есть указатель. Он занимает 8 байт или 64-бит памяти. Минимально адресуемый размер памяти - 1 байт. И получается, что 8 байт памяти могут хранить 2^64 уникальных чисел и, соответственно, именно столько байт и могут быть адресованы. У меня этот ответ приняли, типа я ответил правильно. Но я ошибался....
Для начала вспомним, как вообще данные программы маппятся на физическую память. Напрямую использовать физические адреса мы не можем, потому что тогда каждый процесс должен был знать о том, какие ячейки уже используются, чтобы не нарваться на конфликт. Поэтому придумали такую абстракцию - виртуальная память. Теперь каждый процесс думает, что он пуп вселенной и ему одному принадлежит вся память компьютера. Теперь процессу ничего не нужно знать, он просто кайфует и оперирует всем адресным пространством единолично. А грязной работой занимается ОС. А раз процессу "принадлежит" вся память компьютера, то в теории ему и доступны все те 2^64 байта для размещения своих данных.
Но на самом деле в современных системах для адресации используются только 48 бит адреса. Почему не все 64? 48-бит - это 256 Тб оперативной памяти. Нет таких промышленных систем, которые бы обладали таким объемом оперативной+swap памяти. Сейчас уже конечно стали появляться, поэтому появляются системы с 52/57 адресными битами, но сегодня не об этом. Представим, что их нет. Тогда введение возможности адресовать все 2^64 байта виртуальной памяти будет увеличивать сложность и нагрузку на преобразование виртуального адреса в физический. Зачем платить за то, чем не пользуешься? Да и 64-битная адресация потребовала бы больший размер страниц, больший размер таблиц страниц или большую глубину страничной структуры. Это все увеличивает стоимость кеш промаха в буфере ассоциативной трансляции (TLB). В общем, накладные расходы были бы больше. А никому этого не надо, пока у нас нет столько памяти.
Но вы спросите у меня: 128 терабайт - это 2^47, а ты нам говоришь, что 48 бит адресуются. Куда делся еще один бит, ааа?
Операционная система, как главный дерижер всех процессов в системе, может вмешиваться в их работу по самым разным причинам. Ну например, через системные вызовы. Поэтому в ОС нужно иметь возможность в адресном пространстве конкретного процесса адресовать свой код и свои данные. Поэтому операционка делает свою виртуальную память видимой в адресном пространстве каждого процесса. Это значит, что 2^48 байт делятся между адресным пространством пользователя (user space) и ядра (kernel space). История встречала разные отношения в этом разделении. Но сейчас более-менее все остановились на соотношении 1:1. То есть 256 терабайт делятся поровну между пользовательским процессом и системой. Положительную часть берет себе система, а отрицательную - процесс. Так и получаются те самые 128 Тб.
Продолжение в комментариях
#memory #OS #fun #hardcore
Здесь мы выясняли, сколько же памяти может нам выдать система. И ответ для многих оказался неожиданным. 131 тарабайт - в дохренальен раз больше, чем реальный объем RAM на тестовой машине. Понятное дело, что это фейковые терабайты, потому что их просто негде расположить. И если бы было хотя бы RAMx2, можно было бы еще поговорить про такие штуки, как файлы подкачки. Но здесь прям совсем ничего не сходится, поэтому погнали разбираться, что к чему. Повторю ремарку, что здесь я говорю про 64-битные системы.
Первая подсказка к ответу для вас - практически в точности такой же результат я получил на других своих машинах. Да и под тем постом @dtbeaver оставил скрин, что у него такие же цифры +- 2 Гб от того, что получил я. Значит этот предел - общий для, по крайней мере, большой группы линуксоидов с 64-битными системами. Это наводит на вопрос: а сколько вообще можно адресовать памяти? Может 131 Тб и есть это количество?
Вторая подсказка - выделилось на самом деле не 131(ох уж это эти десятичные приставки в двоичном мире...), а 128. До боли знакомое число...
Однажды на собесе меня спросили: сколько байт я могу адресовать в программе? И я ответил: 2^64 байт. Ну вот у нас есть указатель. Он занимает 8 байт или 64-бит памяти. Минимально адресуемый размер памяти - 1 байт. И получается, что 8 байт памяти могут хранить 2^64 уникальных чисел и, соответственно, именно столько байт и могут быть адресованы. У меня этот ответ приняли, типа я ответил правильно. Но я ошибался....
Для начала вспомним, как вообще данные программы маппятся на физическую память. Напрямую использовать физические адреса мы не можем, потому что тогда каждый процесс должен был знать о том, какие ячейки уже используются, чтобы не нарваться на конфликт. Поэтому придумали такую абстракцию - виртуальная память. Теперь каждый процесс думает, что он пуп вселенной и ему одному принадлежит вся память компьютера. Теперь процессу ничего не нужно знать, он просто кайфует и оперирует всем адресным пространством единолично. А грязной работой занимается ОС. А раз процессу "принадлежит" вся память компьютера, то в теории ему и доступны все те 2^64 байта для размещения своих данных.
Но на самом деле в современных системах для адресации используются только 48 бит адреса. Почему не все 64? 48-бит - это 256 Тб оперативной памяти. Нет таких промышленных систем, которые бы обладали таким объемом оперативной+swap памяти. Сейчас уже конечно стали появляться, поэтому появляются системы с 52/57 адресными битами, но сегодня не об этом. Представим, что их нет. Тогда введение возможности адресовать все 2^64 байта виртуальной памяти будет увеличивать сложность и нагрузку на преобразование виртуального адреса в физический. Зачем платить за то, чем не пользуешься? Да и 64-битная адресация потребовала бы больший размер страниц, больший размер таблиц страниц или большую глубину страничной структуры. Это все увеличивает стоимость кеш промаха в буфере ассоциативной трансляции (TLB). В общем, накладные расходы были бы больше. А никому этого не надо, пока у нас нет столько памяти.
Но вы спросите у меня: 128 терабайт - это 2^47, а ты нам говоришь, что 48 бит адресуются. Куда делся еще один бит, ааа?
Операционная система, как главный дерижер всех процессов в системе, может вмешиваться в их работу по самым разным причинам. Ну например, через системные вызовы. Поэтому в ОС нужно иметь возможность в адресном пространстве конкретного процесса адресовать свой код и свои данные. Поэтому операционка делает свою виртуальную память видимой в адресном пространстве каждого процесса. Это значит, что 2^48 байт делятся между адресным пространством пользователя (user space) и ядра (kernel space). История встречала разные отношения в этом разделении. Но сейчас более-менее все остановились на соотношении 1:1. То есть 256 терабайт делятся поровну между пользовательским процессом и системой. Положительную часть берет себе система, а отрицательную - процесс. Так и получаются те самые 128 Тб.
Продолжение в комментариях
#memory #OS #fun #hardcore
STL vs stdlib
Откопаем один из популярнейших холиваров по С++, о котором вы даже могли и не слышать. Из-за того, что мы с вами не носители, то плохо понимаем ориджин терминов, которые сами используем. Ну типа всю нашу жизнь вокруг нас на туалетах написано WC и мы даже не понимаем, а что это значит на самом деле. Но продолжаем в новых заведениях помечать туалет именно этими буквами и просто принимаем это, как данность. Water closet. Так давно в Англии начали назывались маленькие приватные комнатки с подачей воды для смыва.
Так и мы с вами употребляем термин STL скорее в каком-то нашем интуитивном понимании, чем в реальном его значении. Ну вот например, в вакансиях плюсовиков в требованиях часто пишут, что необходимо знание буста и STL. Думаю, что и HR'ы и соискатели удивятся, что 99.9% плюсовиков никогда не пользовались STL....
Утверждение громкое и для кого-то может быть обидное, поэтому погнали разбираться, пока меня тухлыми помидорами не закидали.
С 1979 года, когда мастер-Бьёрн создал С с классами, пройдет почти 20 лет прежде, чем С++ будет стандартизирован в 1998 году. Процесс стандартизации шел долго и люди со временем вносили свои пропоузалы в будущий стандарт. В принципе и сейчас так делают. Так вот. Жил, был и работал в HP один русский эмигрант - Александр Степанов. У него давно были мысли по созданию обобщенной библиотеки, в которой данные и алгоритмы над ними находились бы отдельно друг от друга. Он пытался воплотить свои мысли в жизнь даже в других языках, типа Ada, потому что на тот момент С++ не обладал необходимой функциональностью. Но язык развивался, появились необходимые фичи и Александр начал думать над реализацией своих идей в С++. В конце 1993 года он рассказал о своих наработках бывшему коллеге - Эндрю Кёнингу, который на тот момент работал в ISO комитете С++. Эндрю восхитился замыслом Александра и организовал ему встречу с комитетом. Комитет тоже охал и ахал от гениальности идей и включил их в драфт страндарта С++. Но не полностью. Что-то пришлось удалить и что-то пришлось подкорректировать в сотрудничестве со Степановым. Именно так были созданы стандартные библиотеки алгоритмов, итераторов и контейнеров.
В 1995 году Александр перешел в компанию Silicon Graphics, доработал и релизнул окончательную версию своего видения STL. Ее даже вроде можно скачать тут. То есть это вообще отдельная библиотека, которую надо отдельно подключать к своему проекту. И с почти стопроцентной вероятностью, вы ей никогда не пользовались.
То есть STL никогда не была частью стандарта, хотя и сильно повлияло на него. В тексте стандарта нет ни одного упоминания STL! Но Степанов сам называл включения своей библиотеки в стандартную библиотеку как STL. И авторы многих книг по С++ называли эти включения STL. Даже Страуструп называет стандартные библиотеки алгоритмов, итераторов и контейнеров STL. Поэтому в умах закрепилась эта ассоциация и, в целом, сейчас легитимно называть так этот набор библиотек.
Но мозг людей склонен к обобщениям, поэтому под STL со временем многие начали понимать в принципе всю стандартную библотеку. Масла в огонь подливает еще, что STL можно расшифровать, как STandard Library. Да и другие части stdlib сугубо шаблонизированы. Типа тех же умных указателей или работы со случайными числами. Для многих STL стала уже симулякром в чистом виде, потому что люди забыли изначальное значение этого акронима.
Я не против использования термина STL в качестве референса к либам алгоритмов, итераторов и контейнеров. Даже для stdlib не против. Потому что не понимаю, как это может вредить программисту. Но считаю важным, чтобы люди понимали настоящий смысл слов, которые они употребляют. Используя в жизни ситулякры, мы отдаляемся от реальных вещей и переходим в мир выдуманный, нереальный. А настоящий мир будет продолжать влиять на нас по прежнему и это противоречие может вылиться в проблемы.
А к какому лагерю вы относитесь? Только stdlib и больше ничего или STL, но в правильном контексте? Напишите свои мысли в комментариях)
Stay in reality. Stay cool.
#fun #commercial #STL
Откопаем один из популярнейших холиваров по С++, о котором вы даже могли и не слышать. Из-за того, что мы с вами не носители, то плохо понимаем ориджин терминов, которые сами используем. Ну типа всю нашу жизнь вокруг нас на туалетах написано WC и мы даже не понимаем, а что это значит на самом деле. Но продолжаем в новых заведениях помечать туалет именно этими буквами и просто принимаем это, как данность. Water closet. Так давно в Англии начали назывались маленькие приватные комнатки с подачей воды для смыва.
Так и мы с вами употребляем термин STL скорее в каком-то нашем интуитивном понимании, чем в реальном его значении. Ну вот например, в вакансиях плюсовиков в требованиях часто пишут, что необходимо знание буста и STL. Думаю, что и HR'ы и соискатели удивятся, что 99.9% плюсовиков никогда не пользовались STL....
Утверждение громкое и для кого-то может быть обидное, поэтому погнали разбираться, пока меня тухлыми помидорами не закидали.
С 1979 года, когда мастер-Бьёрн создал С с классами, пройдет почти 20 лет прежде, чем С++ будет стандартизирован в 1998 году. Процесс стандартизации шел долго и люди со временем вносили свои пропоузалы в будущий стандарт. В принципе и сейчас так делают. Так вот. Жил, был и работал в HP один русский эмигрант - Александр Степанов. У него давно были мысли по созданию обобщенной библиотеки, в которой данные и алгоритмы над ними находились бы отдельно друг от друга. Он пытался воплотить свои мысли в жизнь даже в других языках, типа Ada, потому что на тот момент С++ не обладал необходимой функциональностью. Но язык развивался, появились необходимые фичи и Александр начал думать над реализацией своих идей в С++. В конце 1993 года он рассказал о своих наработках бывшему коллеге - Эндрю Кёнингу, который на тот момент работал в ISO комитете С++. Эндрю восхитился замыслом Александра и организовал ему встречу с комитетом. Комитет тоже охал и ахал от гениальности идей и включил их в драфт страндарта С++. Но не полностью. Что-то пришлось удалить и что-то пришлось подкорректировать в сотрудничестве со Степановым. Именно так были созданы стандартные библиотеки алгоритмов, итераторов и контейнеров.
В 1995 году Александр перешел в компанию Silicon Graphics, доработал и релизнул окончательную версию своего видения STL. Ее даже вроде можно скачать тут. То есть это вообще отдельная библиотека, которую надо отдельно подключать к своему проекту. И с почти стопроцентной вероятностью, вы ей никогда не пользовались.
То есть STL никогда не была частью стандарта, хотя и сильно повлияло на него. В тексте стандарта нет ни одного упоминания STL! Но Степанов сам называл включения своей библиотеки в стандартную библиотеку как STL. И авторы многих книг по С++ называли эти включения STL. Даже Страуструп называет стандартные библиотеки алгоритмов, итераторов и контейнеров STL. Поэтому в умах закрепилась эта ассоциация и, в целом, сейчас легитимно называть так этот набор библиотек.
Но мозг людей склонен к обобщениям, поэтому под STL со временем многие начали понимать в принципе всю стандартную библотеку. Масла в огонь подливает еще, что STL можно расшифровать, как STandard Library. Да и другие части stdlib сугубо шаблонизированы. Типа тех же умных указателей или работы со случайными числами. Для многих STL стала уже симулякром в чистом виде, потому что люди забыли изначальное значение этого акронима.
Я не против использования термина STL в качестве референса к либам алгоритмов, итераторов и контейнеров. Даже для stdlib не против. Потому что не понимаю, как это может вредить программисту. Но считаю важным, чтобы люди понимали настоящий смысл слов, которые они употребляют. Используя в жизни ситулякры, мы отдаляемся от реальных вещей и переходим в мир выдуманный, нереальный. А настоящий мир будет продолжать влиять на нас по прежнему и это противоречие может вылиться в проблемы.
А к какому лагерю вы относитесь? Только stdlib и больше ничего или STL, но в правильном контексте? Напишите свои мысли в комментариях)
Stay in reality. Stay cool.
#fun #commercial #STL
Сравниваем циклы
Пришла в голову такая незамысловатая идея сравнить время работы разных видов циклов, в которых будут выполняться простая операция - инкремент элемента массива. Операция простая и сравнимая по затратам с затратами на само итерирование. Поэтому разница в затратах на итерирование должна сыграть весомую роль в различиях итоговых значений. Если конечно, такие различия будут.
Берем довольно солидный массивчик на 1кк элементов и в циклах будем просто инкрементировать его элементы. Если вам 1кк кажется небольшим числом и результаты будут неточными, вы правы. Результаты в любом случае будут неточные, потому что моя тачка не заточена под перформанс тестирование. Однако флуктуации можно убрать: надо запустить изменение времени много-много раз и затем усреднить результаты. При достаточном количестве запусков, результатам можно будет верить. Я выбрал его равным 100 000. Просто имперически. Не хотел ждать больше 10 мин выполнения кода)
Дальше дело техники. Шаблонная функция для измерения времени, по циклу на сбор статистики и вывод результатов.
Шо по цифрам. В целом, все довольно ожидаемо. С++-like циклы прикурили у старых-добрых Си-style циклов. За комфорт, лаконичность и объектно-ориентированность приходится платить самым дорогим, что у программиста есть - процессорными клоками. Однако не совсем ожидаемо, что разница будет ~50%. Эт довольно много, поэтому все мы на заметочку себе взяли.
Не зря в критичных узких местах все до сих пор используют сишечку. С++ хорош при описании сущностей, способе работы с ними и удобстве работы с ними. Но С - гарант качественного перформанса.
Ну и соболезнования для for_each. Им как бы и так никто не пользуется, еще и здесь унизили.
Тема сравнения производительности кажется мне интересной и в будущем думаю, что затестим еще много чего.
Measure your performance. Stay cool.
#performance #fun #goodoldc
Пришла в голову такая незамысловатая идея сравнить время работы разных видов циклов, в которых будут выполняться простая операция - инкремент элемента массива. Операция простая и сравнимая по затратам с затратами на само итерирование. Поэтому разница в затратах на итерирование должна сыграть весомую роль в различиях итоговых значений. Если конечно, такие различия будут.
Берем довольно солидный массивчик на 1кк элементов и в циклах будем просто инкрементировать его элементы. Если вам 1кк кажется небольшим числом и результаты будут неточными, вы правы. Результаты в любом случае будут неточные, потому что моя тачка не заточена под перформанс тестирование. Однако флуктуации можно убрать: надо запустить изменение времени много-много раз и затем усреднить результаты. При достаточном количестве запусков, результатам можно будет верить. Я выбрал его равным 100 000. Просто имперически. Не хотел ждать больше 10 мин выполнения кода)
Дальше дело техники. Шаблонная функция для измерения времени, по циклу на сбор статистики и вывод результатов.
Шо по цифрам. В целом, все довольно ожидаемо. С++-like циклы прикурили у старых-добрых Си-style циклов. За комфорт, лаконичность и объектно-ориентированность приходится платить самым дорогим, что у программиста есть - процессорными клоками. Однако не совсем ожидаемо, что разница будет ~50%. Эт довольно много, поэтому все мы на заметочку себе взяли.
Не зря в критичных узких местах все до сих пор используют сишечку. С++ хорош при описании сущностей, способе работы с ними и удобстве работы с ними. Но С - гарант качественного перформанса.
Ну и соболезнования для for_each. Им как бы и так никто не пользуется, еще и здесь унизили.
Тема сравнения производительности кажется мне интересной и в будущем думаю, что затестим еще много чего.
Measure your performance. Stay cool.
#performance #fun #goodoldc
Самая программистская математическая задачка
Есть одна задачка, которая вскружила мне голову элегантностью своего решения. Сформулирована она как обычная задачка на логику, но по сути своей очень программистская. Для людей с очень «низкоуровневым мышлением». Поэтому и решил с вами ей поделиться. Кажется плюсовый канал - подходящее место для таких задачек. Может я преувеличиваю, но я художник, я так чувствую.
Собсна формулировка. Жил был король. Хорошо король правил своей страной, богатая она была. И король соответственно тоже жил в большой роскоши. Появился у этого короля завистник среди придворной интеллигенции и захотел он убить короля. Думал про разные способы убийства и вспомнил одну деталь. Король очень любит вино и в погребе дворца есть 1000 бутылок его самого любимого вина, которое он пьет каждый день. И решил завистник отравить вино. Послал вместо себя убийцу в погреб, чтобы он отравил бутылки. Однако убийцу быстро нашли и поймали до того, как он отравил все бутылки. По правде говоря, он успел только одну из них отравить.
И теперь перед королем стоит задача - определить отравленное вино, потому что убийца не сознается.
Чтобы не травить людей, король приказал принести ему 10 кроликов. По задумке кролики будут пить вина из каждой бутылки и рано и поздно, найдется отравленная. Каждый кролик может пить неограниченное количество вина. То что он будет вдрызг пьяный, не значит, что он мертвый 😁
Чтобы убить живое существо, яду нужно примерно 24 часа.
Имея 10 кроликов и 1000 бутылок, королю нужно за минимальное время определить, какая из бутылок отравленная, чтобы продолжить пить свое любимое вино.
Решением задачи будет стратегия, придерживаясь которой гарантированно определяется нужная бутылка за минимальное количество времени.
Кидайте свои варианты в комменты. Если знаете реальное решение, то прошу не писать его, чтобы другие могли хорошенько подумать.
Кажется, что тут даже можно что-то пообсуждать, поэтому оставлю вас без решения пока. Ответ напишу в комментах к завтрашнему посту. Не гуглите решение, чтобы не испортить себе впечатление. Так что подрубаем уведомления, скорее всего вы сильно удивитесь решению.
Solve problems. Stay cool.
#fun
Есть одна задачка, которая вскружила мне голову элегантностью своего решения. Сформулирована она как обычная задачка на логику, но по сути своей очень программистская. Для людей с очень «низкоуровневым мышлением». Поэтому и решил с вами ей поделиться. Кажется плюсовый канал - подходящее место для таких задачек. Может я преувеличиваю, но я художник, я так чувствую.
Собсна формулировка. Жил был король. Хорошо король правил своей страной, богатая она была. И король соответственно тоже жил в большой роскоши. Появился у этого короля завистник среди придворной интеллигенции и захотел он убить короля. Думал про разные способы убийства и вспомнил одну деталь. Король очень любит вино и в погребе дворца есть 1000 бутылок его самого любимого вина, которое он пьет каждый день. И решил завистник отравить вино. Послал вместо себя убийцу в погреб, чтобы он отравил бутылки. Однако убийцу быстро нашли и поймали до того, как он отравил все бутылки. По правде говоря, он успел только одну из них отравить.
И теперь перед королем стоит задача - определить отравленное вино, потому что убийца не сознается.
Чтобы не травить людей, король приказал принести ему 10 кроликов. По задумке кролики будут пить вина из каждой бутылки и рано и поздно, найдется отравленная. Каждый кролик может пить неограниченное количество вина. То что он будет вдрызг пьяный, не значит, что он мертвый 😁
Чтобы убить живое существо, яду нужно примерно 24 часа.
Имея 10 кроликов и 1000 бутылок, королю нужно за минимальное время определить, какая из бутылок отравленная, чтобы продолжить пить свое любимое вино.
Решением задачи будет стратегия, придерживаясь которой гарантированно определяется нужная бутылка за минимальное количество времени.
Кидайте свои варианты в комменты. Если знаете реальное решение, то прошу не писать его, чтобы другие могли хорошенько подумать.
Кажется, что тут даже можно что-то пообсуждать, поэтому оставлю вас без решения пока. Ответ напишу в комментах к завтрашнему посту. Не гуглите решение, чтобы не испортить себе впечатление. Так что подрубаем уведомления, скорее всего вы сильно удивитесь решению.
Solve problems. Stay cool.
#fun
Cамая популярная задачка с собеседований
Это вообще отдельный жанр в собеседованиях - логические задачки. Есть те, кто любит задавать их каждому кандидату. Но большинство обходит не используют их при найме людей. Оно и понятно, на собесах люди в довольно стрессовом состоянии находятся. Им бы вспомнить, чем вектор от листа отличается, не говоря уже о том, чтобы сказать, как засунуть слона в холодильник.
На моем пути у меня 2 раза спрашивали логические задачки и оба раза спрашивали одну и ту же. Поэтому название поста в стиле ошибки выжившего. Но, думаю, что она реально такая популярная, поэтому будет полезно подготовиться к ней.
Формулировка.
Вы находитесь в кольцевом поезде. То есть как будто бы 2 конца одного поезда соединили и можно бесконечно теперь в нем гулять. Количество вагонов вам неизвестно. В каждом вагоне есть всего одна лампочка. Она имеет 2 состояния: вкл и выкл. По дефолту они в рандомном порядке включены во всех вагонах, то есть вы заранее не знаете, в каком порядке в вагонах зажжены лампочки. И у каждой лампочки есть выключатель, который исправно работает.
Вас телепортируют в какой-то из вагонов поезда. Ваша задача - найти длину поезда аля количество вагонов. Естественно, вы можете переходить из вагона в вагон.
Такая вот незамысловатая задачка. Рассуждая логически, можно довольно быстро прийти к ответу. Главное - правильно себе вопросы ставить.
Знающих прошу не спойлерить в комментах и не подсказывать. Обсуждения как всегда поощряются. Если вы допетрили до решения, то лучше его при себе оставить.
Решение сброшу завтра в комментах к отдельному посту, посвященному ответу.
Всем удачи!
Train your logic. Stay cool.
#fun
Это вообще отдельный жанр в собеседованиях - логические задачки. Есть те, кто любит задавать их каждому кандидату. Но большинство обходит не используют их при найме людей. Оно и понятно, на собесах люди в довольно стрессовом состоянии находятся. Им бы вспомнить, чем вектор от листа отличается, не говоря уже о том, чтобы сказать, как засунуть слона в холодильник.
На моем пути у меня 2 раза спрашивали логические задачки и оба раза спрашивали одну и ту же. Поэтому название поста в стиле ошибки выжившего. Но, думаю, что она реально такая популярная, поэтому будет полезно подготовиться к ней.
Формулировка.
Вы находитесь в кольцевом поезде. То есть как будто бы 2 конца одного поезда соединили и можно бесконечно теперь в нем гулять. Количество вагонов вам неизвестно. В каждом вагоне есть всего одна лампочка. Она имеет 2 состояния: вкл и выкл. По дефолту они в рандомном порядке включены во всех вагонах, то есть вы заранее не знаете, в каком порядке в вагонах зажжены лампочки. И у каждой лампочки есть выключатель, который исправно работает.
Вас телепортируют в какой-то из вагонов поезда. Ваша задача - найти длину поезда аля количество вагонов. Естественно, вы можете переходить из вагона в вагон.
Такая вот незамысловатая задачка. Рассуждая логически, можно довольно быстро прийти к ответу. Главное - правильно себе вопросы ставить.
Знающих прошу не спойлерить в комментах и не подсказывать. Обсуждения как всегда поощряются. Если вы допетрили до решения, то лучше его при себе оставить.
Решение сброшу завтра в комментах к отдельному посту, посвященному ответу.
Всем удачи!
Train your logic. Stay cool.
#fun
Снова сравниваем решения задачи с поездами
Кто забыл или не в теме, вот эта задача. В прошлом мы уже сравнивали два решения: условный маятник и спидометр. Лучше освежить в памяти контекст, чтобы понятнее был предмет разговора. Однако наша подписчица @tigrisVD сделала несколько улучшений алгоритма спидометра. Вот ее сообщение с пояснениями и кодом.
Первое - базовое улучшение. Вместо того, чтобы возвращаться назад на каждом шаге(что очень расточительно), мы возвращаемся назад, только, если встретили единичку и поменяли ее на ноль. Только в этом случае мы могли поменять самую первую лампочку.
Это уже улучшение уполовинило количество шагов. И сравняло его с маятником.
Но она пошла дальше и придумала следующую оптимизацию: пусть мы встретили единичку, когда шли вправо. Тогда разрешим себе поменять ее на нолик и идти дальше на еще столько же шагов, сколько мы сделали до этой единички. Но если мы встретим еще одну единичку, то возвращаемся обратно и чекаем нулевую ячейку. Таким образом мы сэкономим себе проход до первой ячейки и обратно. А если мы за этот удвоенный период не нашли ее одну единичку, то мы просто обязаны обратно вернуться, чтобы проверить была ли первая новая единичка на нашем пути - тем самым началом.
Там есть некоторые проблемы с тем, что оптимизированные алгоритмы спидометра зависят от входных данных. И в худшем случае, когда в поезде включены все лампочки, последний оптимизированный алгоритм работает лишь в 2 раза лучше базового спидометра. В лучшем случае, когда все лампочки выключены - сложность алгоритмов линейно зависит от количества вагонов, а не квадратично, как у базового спидометра. Базовое улучшение - нужно пройти всего х2 от количества вагонов. А оптимизированный вариант- х4(я там одну ошибочку нашел в коде при подсчете пройденных вагонов, поэтому не в 3, а в 4). Но в рандомных случаях оптимизированный вариант примерно в 2 раза быстрее базового улучшенного и в 4 раза быстрее оригинального спидометра.
Позапускать ее код и посмотреть на цифры можно тут
Спасибо вам, @tigrisVD, за такие интересные решения!
Но ваши улучшения натолкнули и меня на размышления и улучшения, о которых я расскажу завтра.
Impove yourself. Stay cool.
#fun #optimization
Кто забыл или не в теме, вот эта задача. В прошлом мы уже сравнивали два решения: условный маятник и спидометр. Лучше освежить в памяти контекст, чтобы понятнее был предмет разговора. Однако наша подписчица @tigrisVD сделала несколько улучшений алгоритма спидометра. Вот ее сообщение с пояснениями и кодом.
Первое - базовое улучшение. Вместо того, чтобы возвращаться назад на каждом шаге(что очень расточительно), мы возвращаемся назад, только, если встретили единичку и поменяли ее на ноль. Только в этом случае мы могли поменять самую первую лампочку.
Это уже улучшение уполовинило количество шагов. И сравняло его с маятником.
Но она пошла дальше и придумала следующую оптимизацию: пусть мы встретили единичку, когда шли вправо. Тогда разрешим себе поменять ее на нолик и идти дальше на еще столько же шагов, сколько мы сделали до этой единички. Но если мы встретим еще одну единичку, то возвращаемся обратно и чекаем нулевую ячейку. Таким образом мы сэкономим себе проход до первой ячейки и обратно. А если мы за этот удвоенный период не нашли ее одну единичку, то мы просто обязаны обратно вернуться, чтобы проверить была ли первая новая единичка на нашем пути - тем самым началом.
Там есть некоторые проблемы с тем, что оптимизированные алгоритмы спидометра зависят от входных данных. И в худшем случае, когда в поезде включены все лампочки, последний оптимизированный алгоритм работает лишь в 2 раза лучше базового спидометра. В лучшем случае, когда все лампочки выключены - сложность алгоритмов линейно зависит от количества вагонов, а не квадратично, как у базового спидометра. Базовое улучшение - нужно пройти всего х2 от количества вагонов. А оптимизированный вариант- х4(я там одну ошибочку нашел в коде при подсчете пройденных вагонов, поэтому не в 3, а в 4). Но в рандомных случаях оптимизированный вариант примерно в 2 раза быстрее базового улучшенного и в 4 раза быстрее оригинального спидометра.
Позапускать ее код и посмотреть на цифры можно тут
Спасибо вам, @tigrisVD, за такие интересные решения!
Но ваши улучшения натолкнули и меня на размышления и улучшения, о которых я расскажу завтра.
Impove yourself. Stay cool.
#fun #optimization
Telegram
Грокаем C++
Cамая популярная задачка с собеседований
Это вообще отдельный жанр в собеседованиях - логические задачки. Есть те, кто любит задавать их каждому кандидату. Но большинство обходит не используют их при найме людей. Оно и понятно, на собесах люди в довольно…
Это вообще отдельный жанр в собеседованиях - логические задачки. Есть те, кто любит задавать их каждому кандидату. Но большинство обходит не используют их при найме людей. Оно и понятно, на собесах люди в довольно…
Линейное решение задачи с поездами
По поводу моих улучшений. Немного поразмыслив, первая моя мысль - что с маятником тоже можно сделать маленькое улучшение такое же, как и базовое улучшение спидометра. Мы не каждый раз поворачиваем и идем в обратную сторону, а только тогда, когда меняем состояние встретившейся лампочки.
Во всех особых случаях, когда все лампочки либо включены, либо выключены, такое улучшение работает за время х2 от количества вагонов. И в среднем работает в 2 раза быстрее, чем оригинальный маятник, и примерно наравне с оптимизированным спидометром(чуточку хуже).
Но! Кажется на основе оптимизированного спидометра я придумал линейный алгоритм, дающий стабильно O(4n) для совершенно рандомных случаев и во всех особых случаях, когда все лампочки либо включены, либо выключены. И где-то О(8n) в худшем случае для конкретно этого алгоритма.
В чем суть. Для оптимизированного спидометра мы разрешали себе идти дальше, когда на очередном проходе на пути от начального вагона мы в первый раз встретили зажженную лампочку, но только до тех пор, пока не встретим еще одну единичку или не закончатся наши разрешенные шаги. А что если пойти дальше, даже после второй зажженной лампочки? Что если каждый раз когда мы встречаем такую лампочку, то разрешаем себе идти еще в 2 раза дальше? Прям каждый раз. Встретили зажженную лампочку - погасили и может идти дальше на столько же вагонов, сколько мы прошли от начала до только что погашенной нами лампочки. По факту, мы идем вперед всегда, пока нам встречаются зажженные лампочки и мы не уходим слишком далеко от последней погашенной нами. Тогда существует всего 2 варианта - рано или поздно мы погасим начальную лампочку или последняя погашенная не была начальной, но мы так и не дошли до следующей зажженной до того, как истекли наши разрешенные вагоны.
В первом случае мы просто пройдем лишний круг и вернемся обратно. Таким образом пройдя 2 лишних круга.
Во втором случае мы идем обратно и проверяем, была ли последняя выключенная нами лампочка той самой начальной. Если не была, то снова начинаем идти вправо, пока не наткнемся на зажженную лампочку.
Таким образом, если зажженные лампочки достаточно часто встречаются, то мы идем в один проход до конца поезда, потом еще удвоенную его длину и обратно. Получается, что нам понадобится 4 длины поезда, чтобы посчитать количество вагонов.
Но есть у такого алгоритма худший случай. Тогда, когда зажженные лампочки стоят ровно на один вагон дальше, чем нам разрешено пройти. Пример: зажженная лампочка находится в 3-м вагоне. После того, как мы ее погасили, нам разрешается идти еще 2 вагона и искать там зажженные лампочки. То есть последний вагон, который мы можем посмотреть на этой итерации - 5-ый. А вот следующая зажженная лампочка будет в шестом. И мы могли бы всего на один вагончик вперед пройти и встретить ее, но согласно алгоритму мы должны вернуться к изначальному вагону. Если после шестого вагона лампочка будет в 12-м, то мы обязаны будем вернуться назад и снова пройти вперед до 12-ого. И так далее. Думаю, суть вы уловили.
Так вот на таких данных сложность повышается до примерно О(8n). Эту чиселку вывел совершенно экспериментально. Возможно знатоки математики и теории алгоритмов выведут более точную зависимость. Чему я очень буду рад)
Вроде бы звучит разумно и тесты все проходятся прекрасно. И сложность на первый взгляд линейная во всех случаях, что не может не радовать.
Прикреплю в комменты полный файл со всеми сравнениями. Но вот ссылка на годболт кому будет так удобнее.
Критика и замечания приветствуются.
Improve yourself. Stay cool.
#fun #optimization
По поводу моих улучшений. Немного поразмыслив, первая моя мысль - что с маятником тоже можно сделать маленькое улучшение такое же, как и базовое улучшение спидометра. Мы не каждый раз поворачиваем и идем в обратную сторону, а только тогда, когда меняем состояние встретившейся лампочки.
Во всех особых случаях, когда все лампочки либо включены, либо выключены, такое улучшение работает за время х2 от количества вагонов. И в среднем работает в 2 раза быстрее, чем оригинальный маятник, и примерно наравне с оптимизированным спидометром(чуточку хуже).
Но! Кажется на основе оптимизированного спидометра я придумал линейный алгоритм, дающий стабильно O(4n) для совершенно рандомных случаев и во всех особых случаях, когда все лампочки либо включены, либо выключены. И где-то О(8n) в худшем случае для конкретно этого алгоритма.
В чем суть. Для оптимизированного спидометра мы разрешали себе идти дальше, когда на очередном проходе на пути от начального вагона мы в первый раз встретили зажженную лампочку, но только до тех пор, пока не встретим еще одну единичку или не закончатся наши разрешенные шаги. А что если пойти дальше, даже после второй зажженной лампочки? Что если каждый раз когда мы встречаем такую лампочку, то разрешаем себе идти еще в 2 раза дальше? Прям каждый раз. Встретили зажженную лампочку - погасили и может идти дальше на столько же вагонов, сколько мы прошли от начала до только что погашенной нами лампочки. По факту, мы идем вперед всегда, пока нам встречаются зажженные лампочки и мы не уходим слишком далеко от последней погашенной нами. Тогда существует всего 2 варианта - рано или поздно мы погасим начальную лампочку или последняя погашенная не была начальной, но мы так и не дошли до следующей зажженной до того, как истекли наши разрешенные вагоны.
В первом случае мы просто пройдем лишний круг и вернемся обратно. Таким образом пройдя 2 лишних круга.
Во втором случае мы идем обратно и проверяем, была ли последняя выключенная нами лампочка той самой начальной. Если не была, то снова начинаем идти вправо, пока не наткнемся на зажженную лампочку.
Таким образом, если зажженные лампочки достаточно часто встречаются, то мы идем в один проход до конца поезда, потом еще удвоенную его длину и обратно. Получается, что нам понадобится 4 длины поезда, чтобы посчитать количество вагонов.
Но есть у такого алгоритма худший случай. Тогда, когда зажженные лампочки стоят ровно на один вагон дальше, чем нам разрешено пройти. Пример: зажженная лампочка находится в 3-м вагоне. После того, как мы ее погасили, нам разрешается идти еще 2 вагона и искать там зажженные лампочки. То есть последний вагон, который мы можем посмотреть на этой итерации - 5-ый. А вот следующая зажженная лампочка будет в шестом. И мы могли бы всего на один вагончик вперед пройти и встретить ее, но согласно алгоритму мы должны вернуться к изначальному вагону. Если после шестого вагона лампочка будет в 12-м, то мы обязаны будем вернуться назад и снова пройти вперед до 12-ого. И так далее. Думаю, суть вы уловили.
Так вот на таких данных сложность повышается до примерно О(8n). Эту чиселку вывел совершенно экспериментально. Возможно знатоки математики и теории алгоритмов выведут более точную зависимость. Чему я очень буду рад)
Вроде бы звучит разумно и тесты все проходятся прекрасно. И сложность на первый взгляд линейная во всех случаях, что не может не радовать.
Прикреплю в комменты полный файл со всеми сравнениями. Но вот ссылка на годболт кому будет так удобнее.
Критика и замечания приветствуются.
Improve yourself. Stay cool.
#fun #optimization
Способы узнать знак целого числа
Иногда появляется необходимость узнать, является ли данное число отрицательным или нет. За примером далеко ходить не будем. В одной из наших задачек про переворачивание десятичных цифр числа один из подходов к решению может быть таким: узнать, является ли число отрицательным, если да, то домножить его на -1 и оперировать им как положительным числом. После всех действий и проверок домножить число обратно на -1.
И вот мне стало интересно. Сколько способов есть, чтобы узнать является ли число отрицательным? Давайте же узнаем! Я вот что надумал:
💥 Как в прошлом посте сдвинуть число вправо на 31/63 бита и привести все к инту. Если получился 0 - число положительное. Если 1 - отрицательное.
💥 bool is_signed = number < 0. Один из самых очевидных и прямолинейных подходов. Просто проверяем число оператором меньше и все на этом. Скучно, попсово, но зато понятно и эффективно.
💥 Использовать битовую маску. bool is_signed = number & 0x80000000. Здесь мы оставляем только знаковый бит на его месте. Затем приводим число к булевому значению. Положительное число превратится в нолик, а значит в true, а отрицательное - в false. Размер маски естественно меняется в зависимости от типа знакового числа.
💥 std::signbit(number). Эта шаблонная функция вернет вам true, если number - отрицательное, и false в обратном случае. На мой взгляд, это больше по плюсовому и функция имеет человеческое название, поэтому читаться такой код будет намного проще, чем в предыдущих случаях.
На этом я застопорился. Никак больше не могу придумать других способов, которые бы не включали в себя предыдущие. Тут скорее мне интересно, какие вы варианты придумаете. Обязательно отпишитесь к комментах!
Generate a dozens of different solutions. Stay cool.
#fun #cppcore
Иногда появляется необходимость узнать, является ли данное число отрицательным или нет. За примером далеко ходить не будем. В одной из наших задачек про переворачивание десятичных цифр числа один из подходов к решению может быть таким: узнать, является ли число отрицательным, если да, то домножить его на -1 и оперировать им как положительным числом. После всех действий и проверок домножить число обратно на -1.
И вот мне стало интересно. Сколько способов есть, чтобы узнать является ли число отрицательным? Давайте же узнаем! Я вот что надумал:
💥 Как в прошлом посте сдвинуть число вправо на 31/63 бита и привести все к инту. Если получился 0 - число положительное. Если 1 - отрицательное.
💥 bool is_signed = number < 0. Один из самых очевидных и прямолинейных подходов. Просто проверяем число оператором меньше и все на этом. Скучно, попсово, но зато понятно и эффективно.
💥 Использовать битовую маску. bool is_signed = number & 0x80000000. Здесь мы оставляем только знаковый бит на его месте. Затем приводим число к булевому значению. Положительное число превратится в нолик, а значит в true, а отрицательное - в false. Размер маски естественно меняется в зависимости от типа знакового числа.
💥 std::signbit(number). Эта шаблонная функция вернет вам true, если number - отрицательное, и false в обратном случае. На мой взгляд, это больше по плюсовому и функция имеет человеческое название, поэтому читаться такой код будет намного проще, чем в предыдущих случаях.
На этом я застопорился. Никак больше не могу придумать других способов, которые бы не включали в себя предыдущие. Тут скорее мне интересно, какие вы варианты придумаете. Обязательно отпишитесь к комментах!
Generate a dozens of different solutions. Stay cool.
#fun #cppcore
Как работает dynamic_cast? RTTI!
#опытным #fun
Продолжаем серию! В прошлой статье мы познакомились с таблицей виртуальных методов. Помимо этой таблицы, в этой же области памяти скрывается еще одна структура.
Как мы видели ранее, для полиморфных объектов существует специальный оператор dynamic_cast. Стандарт не регламентирует его реализацию, но чаще всего, для работы требуется дополнительная информация о типе полиморфного объекта RTTI (Run Time Type Information). Посмотреть эту структуру можно с помощью оператора
Содержимое RTTI зависит от компилятора, но как минимум там хранится
Операторы
Как же нам найти начало объекта RTTI? Не боги горшки обжигают, есть просто специальный указатель, который расположен прямо перед началом таблицы виртуальных методов. Он и ведёт к объекту RTTI:
Получив доступ к дополнительной информации остаётся выполнить приведение типа: upcast, downcast, sidecast/crosscast. Эта задача требует совершить поиск в ориентированном ациклическом графе (DAG, directed acyclic graph), что в рамках этой операции может быть трудоёмким, но необходимым для обработки общего случая. Теперь мы можем даже ответить, почему
Можем ли мы как-то ускорить работу? Мы можем просто запретить использовать
И такое ограничение будет автоматически подталкивать к пересмотру полученной архитектуры решения или разработке собственного механизма приведения типов.
На счет последнего надо много и долго думать. На стыке двух динамических библиотек, которые могут ничего не знать друг о друге, придется как-то проверять, что лежит в динамическом типе. Так же необходимо учитывать особенности множественного и виртуального наследования. От них можно и в принципе отказаться, но как запретить вышеупомянутые виды наследования в коде? Меня бы в первую очередь интересовала автономная и независимая жизнь проекта без пристального надзора хранителей знаний. Это задача, которая имеет много подводных камней или требует введения в проект ограничений, дополнительного контроля.
Если
#cppcore #howitworks
#опытным #fun
Продолжаем серию! В прошлой статье мы познакомились с таблицей виртуальных методов. Помимо этой таблицы, в этой же области памяти скрывается еще одна структура.
Как мы видели ранее, для полиморфных объектов существует специальный оператор dynamic_cast. Стандарт не регламентирует его реализацию, но чаще всего, для работы требуется дополнительная информация о типе полиморфного объекта RTTI (Run Time Type Information). Посмотреть эту структуру можно с помощью оператора
typeid:cppОбратите внимание,
const auto &RTTI = typeid(object);
typeid возвращает read-only ссылку на объект std::type_info, т.к. эту область памяти нельзя изменять — она была сгенерирована компилятором на этапе компиляции.Содержимое RTTI зависит от компилятора, но как минимум там хранится
hash полиморфного класса и его имя, которые доступны из std::type_info. Маловероятно, что вам на этом потребуется построить какую-то логику приложения, но эта штука могла бы быть вам полезна при отладке / подсчёте статистики и т.д. Операторы
dynamic_cast и typeid получают доступ к этой структуре так же через скрытый виртуальный указатель, который подшивается к объектам полиморфного класса. Как мы знаем, этот указатель смотрит на начало таблицы виртуальных методов, коих может быть бесчисленное множество и варьироваться от наследника к наследнику.Как же нам найти начало объекта RTTI? Не боги горшки обжигают, есть просто специальный указатель, который расположен прямо перед началом таблицы виртуальных методов. Он и ведёт к объекту RTTI:
┌-─| ptr to RTTI | vtable pointer
| |----------------| <- looks here
| | vtable methods |
| |----------------|
└─>| RTTI object |
Получив доступ к дополнительной информации остаётся выполнить приведение типа: upcast, downcast, sidecast/crosscast. Эта задача требует совершить поиск в ориентированном ациклическом графе (DAG, directed acyclic graph), что в рамках этой операции может быть трудоёмким, но необходимым для обработки общего случая. Теперь мы можем даже ответить, почему
dynamic_cast такой медленный.Можем ли мы как-то ускорить работу? Мы можем просто запретить использовать
dynamic_cast 😄 Это можно сделать, отключив RTTI с помощью флага компиляции:-fno-rtti
И такое ограничение будет автоматически подталкивать к пересмотру полученной архитектуры решения или разработке собственного механизма приведения типов.
На счет последнего надо много и долго думать. На стыке двух динамических библиотек, которые могут ничего не знать друг о друге, придется как-то проверять, что лежит в динамическом типе. Так же необходимо учитывать особенности множественного и виртуального наследования. От них можно и в принципе отказаться, но как запретить вышеупомянутые виды наследования в коде? Меня бы в первую очередь интересовала автономная и независимая жизнь проекта без пристального надзора хранителей знаний. Это задача, которая имеет много подводных камней или требует введения в проект ограничений, дополнительного контроля.
Если
dynamic_cast становится бутылочным горлышком, то в первую очередь стоит пересмотреть именно архитектуру решения, а оптимизации оставить на крайний случай.#cppcore #howitworks
XOR Swap
Есть такая интересная техника для свопинга содержимого двух переменных без надобности во временной третьей! Стандартный подход выглядит примерно так:
Все мы с программистких пеленок уже выучили это. И примерно так и реализована функция std::swap из стандартной библиотеки. Однако вот вам задали на собесе вопрос: "вот у вас есть 2 числа, но я хочу, чтобы вы обменяли их значения без временной переменной?". Какие мысли? Подумайте пару секунд.
Как всегда, на помощь приходит магия математики и битовых операций. Можно использовать 3 подряд операции xor над этими числами и мы получим нужный результат.
Доказывать сие утверждения я, конечно, не буду. Однако можете почитать в английской вики, там все подробно выводится из свойств Исключающего ИЛИ.
Тут есть один интересный момент, что в случае подачи на вход функции одной и той же переменной, то произойдет эффект зануления. Первый же xor занулит x, а значит и y. Поэтому в самом начале стоит условие на проверку одинакового адреса.
При подаче на вход просто одинаковых значений, все работает и без условия.
Ну и работает это дело только с целочисленными параметрами.
Но предостерегаю вас - не используйте эту технику в современных программах! Результаты этих трех ксоров напрямую зависят друг от друга по цепочке. А значит параллелизма на уровне инструкций можно не ждать.
Современные компиляторы вполне могут и соптимизировать третью переменную и вы ее вовсе не увидите в ассемблере. Да и еще и вариант с доп переменной тупо быстрее работает. Всего 2 store'а и 2 load'а, которые еще и распараллелить можно, против 3 затратных ксоров. Да и даже довольно тяжеловесная XCHG работает быстрее, чем 3 xor'а.
Зачем я это все рассказываю тогда, если эта техника уже никому не уперлась? Для ретроспективы событий. Дело в том, что раньше люди писали программы без компиляторов, напрямую на ассемблере. Плюс в то время компьютеры имели такое маленькое количество памяти, что биться приходилось буквально за каждый байт. А используя операции xor, мы экономим 33% памяти на эту операцию. Довольно неплохо. В стародавние времена как только не извращались люди, чтобы выжимать все из железа. Эх, были времена...
Понимание тонкостей операции xor и ее возможных приложений делают ее довольно мощным инструментом в низкоуровневых вычислениях. А в некоторых задачах вы и вовсе никогда даже не подумаете, что они могут наиболее эффективным образом решаться с помощью xor.
Learn technics from the past. Stay cool.
#cppcore #fun #algorithms
Есть такая интересная техника для свопинга содержимого двух переменных без надобности во временной третьей! Стандартный подход выглядит примерно так:
template <class T>
void swap(T& lhs, T& rhs) {
T tmp = std::move(lhs);
lhs = std::move(rhs);
rhs = std::move(tmp);
}
Все мы с программистких пеленок уже выучили это. И примерно так и реализована функция std::swap из стандартной библиотеки. Однако вот вам задали на собесе вопрос: "вот у вас есть 2 числа, но я хочу, чтобы вы обменяли их значения без временной переменной?". Какие мысли? Подумайте пару секунд.
Как всегда, на помощь приходит магия математики и битовых операций. Можно использовать 3 подряд операции xor над этими числами и мы получим нужный результат.
template <class T, typename std::enable_if_t<std::is_integral_v<T>> = 0>
void swap(T& x, T& y) {
if (&x == &y)
return;
x = x ^ y;
y = x ^ y;
x = x ^ y;
}
Доказывать сие утверждения я, конечно, не буду. Однако можете почитать в английской вики, там все подробно выводится из свойств Исключающего ИЛИ.
Тут есть один интересный момент, что в случае подачи на вход функции одной и той же переменной, то произойдет эффект зануления. Первый же xor занулит x, а значит и y. Поэтому в самом начале стоит условие на проверку одинакового адреса.
При подаче на вход просто одинаковых значений, все работает и без условия.
Ну и работает это дело только с целочисленными параметрами.
Но предостерегаю вас - не используйте эту технику в современных программах! Результаты этих трех ксоров напрямую зависят друг от друга по цепочке. А значит параллелизма на уровне инструкций можно не ждать.
Современные компиляторы вполне могут и соптимизировать третью переменную и вы ее вовсе не увидите в ассемблере. Да и еще и вариант с доп переменной тупо быстрее работает. Всего 2 store'а и 2 load'а, которые еще и распараллелить можно, против 3 затратных ксоров. Да и даже довольно тяжеловесная XCHG работает быстрее, чем 3 xor'а.
Зачем я это все рассказываю тогда, если эта техника уже никому не уперлась? Для ретроспективы событий. Дело в том, что раньше люди писали программы без компиляторов, напрямую на ассемблере. Плюс в то время компьютеры имели такое маленькое количество памяти, что биться приходилось буквально за каждый байт. А используя операции xor, мы экономим 33% памяти на эту операцию. Довольно неплохо. В стародавние времена как только не извращались люди, чтобы выжимать все из железа. Эх, были времена...
Понимание тонкостей операции xor и ее возможных приложений делают ее довольно мощным инструментом в низкоуровневых вычислениях. А в некоторых задачах вы и вовсе никогда даже не подумаете, что они могут наиболее эффективным образом решаться с помощью xor.
Learn technics from the past. Stay cool.
#cppcore #fun #algorithms
