#algo and some #math
https://hbfs.wordpress.com/2021/07/20/binary-trees-are-optimal-except-when-theyre-not/
https://hbfs.wordpress.com/2021/07/20/binary-trees-are-optimal-except-when-theyre-not/
Harder, Better, Faster, Stronger
Binary Trees are optimal… except when they’re not.
The best case depth for a search tree is $latex O(\log_b n)$, if $latex b$ is the arity (or branching) of the tree. Intuitively, we know that if we increase $latex b$, the depth goes down, but is t…
[неожиданно] #math #algo
Делюсь небольшой задачей из начала универа. Сильно мне тогда понравилась.
https://telegra.ph/Zadacha-iz-molodosti-05-30
Единственное что пришлось приложить немалые усилия (и попросить помощь у друзей), чтобы восстановить картинку в голове, потому что математик из меня так себе.
Делюсь небольшой задачей из начала универа. Сильно мне тогда понравилась.
https://telegra.ph/Zadacha-iz-molodosti-05-30
Единственное что пришлось приложить немалые усилия (и попросить помощь у друзей), чтобы восстановить картинку в голове, потому что математик из меня так себе.
Telegraph
Задача из молодости
Когда-то на первом курсе (уже 5 лет назад, ого!) мне показали очередную задачу на codeforces. Я её довольно сильно запомнил, потому что она не очень сложная с точки зрения математических рассуждений и красиво сворачивается в понятный ответ (который ещё и…
👍7❤4💅4
#common #math
Наткнулся на статью про то, как быстро и корректно складывать числа с плавающей запятой (ссылка будет в конце).
Общая проблема в том, что из-за того, что дробные числа хранятся в примитивных типах не точно, может возникать некоторая потеря точности (сорян за тавтологию) при арифметических операциях. Например когда складываешь большое число с маленьким, маленькое вполне может никак не изменить ответ, т.к. оно с точки зрения хранения чисел "пренебрежимо мало" (ну или нужное число не может быть представлено дробным число) Вопрос в том, как наиболее точно сложить какое-то множество чисел.
Пусть у вас есть какой-то массив числе с плавающей запятой. Конечно мы можем сложить числа просто подряд:
Но тогда у вас в какой-то момент может получится огромное число и следующее добавление маленького легко потеряется из-за погрешности.
А можем отсортировать вектор чисел перед суммой! Тогда мы будем накапливать сумму и при добавлении следующего числа по возрастанию оно может быть сравнимо с текущей суммой (хотя конечно зависит от данных, т.к. если все ваши числа это 1 + x_i, где x_i -- последовательность очень маленьких возрастающих чисел, то в какой-то момент большая сумма скушает этот 1 + eps).
Можно сделать лучше. Например закинуть все числа в кучу и попарно складывать два самых маленьких числа, возвращая результат обратно. Это может работать лучше, т.к. теперь мы ни в какой момент не будем складывать сумму большого количества элементов с одним небольшим.
Дальше развивать не буду. Прочитаете в статье: оригинал и перевод.
Кстати когда-то у студентов на пару лет младше в унике видел фановый контест в рамках одной из дисциплин, где нужно было найти сумму чисел наиболее точно (авторское решение, естественно, на длинке python). Первое место забрал чувак с суммой Кэхена.
Ну и мем из молодости: плавающая запятая.
Наткнулся на статью про то, как быстро и корректно складывать числа с плавающей запятой (ссылка будет в конце).
Общая проблема в том, что из-за того, что дробные числа хранятся в примитивных типах не точно, может возникать некоторая потеря точности (сорян за тавтологию) при арифметических операциях. Например когда складываешь большое число с маленьким, маленькое вполне может никак не изменить ответ, т.к. оно с точки зрения хранения чисел "пренебрежимо мало" (ну или нужное число не может быть представлено дробным число) Вопрос в том, как наиболее точно сложить какое-то множество чисел.
Пусть у вас есть какой-то массив числе с плавающей запятой. Конечно мы можем сложить числа просто подряд:
std::vector<float> v = Get();
float ans = 0.0;
for (int i = 0; i < v.size(); ++i) {
ans += v[i];
}
Но тогда у вас в какой-то момент может получится огромное число и следующее добавление маленького легко потеряется из-за погрешности.
А можем отсортировать вектор чисел перед суммой! Тогда мы будем накапливать сумму и при добавлении следующего числа по возрастанию оно может быть сравнимо с текущей суммой (хотя конечно зависит от данных, т.к. если все ваши числа это 1 + x_i, где x_i -- последовательность очень маленьких возрастающих чисел, то в какой-то момент большая сумма скушает этот 1 + eps).
Можно сделать лучше. Например закинуть все числа в кучу и попарно складывать два самых маленьких числа, возвращая результат обратно. Это может работать лучше, т.к. теперь мы ни в какой момент не будем складывать сумму большого количества элементов с одним небольшим.
Дальше развивать не буду. Прочитаете в статье: оригинал и перевод.
Кстати когда-то у студентов на пару лет младше в унике видел фановый контест в рамках одной из дисциплин, где нужно было найти сумму чисел наиболее точно (авторское решение, естественно, на длинке python). Первое место забрал чувак с суммой Кэхена.
Ну и мем из молодости: плавающая запятая.
❤23👍4
#cpp #common #math
1. [talk] C++ Reflection Is Not Contemplation.
Доклад Andrei Alexandrescu с CppCon 2024 про рефлексию. Чуть-чуть посмотрели на базу, посмотрели на несколько последних пропозалов и ушли в сторону в какие-то абстрактные рассуждения. В классической свободной заводной манере. Лайкнул.
2. [talk] Building Cppcheck - What We Learned from 17 Years of Development.
Автор cppcheck рассказывает про то, как развивался проект и про разные вехи на этом пути. Не прям технический доклад. Интересно посмотреть на историю известной тулзы.
3. [article] Preferring throwaway code over design docs.
Автор предлагает почаще кодить прототипы перед тем, как писать дизайн доки/писать финальное решение. Так вы получаете некоторые знания о потенциальных проблемах заранее. А ещё позиционирует смерженные pull request'ы как хорошую "документацию", т.к. они всегда актуальны для какой-то точки в истории. Со вторым я согласен. Но с первым нет. В условиях постоянной гонки и нехватки ресурсов нет времени садиться писать код для большинства фичей. А там, где ошибка стоит дороже всего (большие проекты с жёсткими дедлайнами) такой подход может сильно скушать время, т.к. для большой фичи -- большой прототип.
4. [article] Probability and Games: Damage Rolls.
В статье рассказывают про то, как из рандома делать разные распределения, чтобы потом это можно было использовать в различных игровых механиках. Начинают с базовых бросков кубика и заканчивают произвольным распределением значений. Заодно можно потыкаться во всякое интерактивное, чтобы лучше понять, как что работает.
В дополнение закину вам баянистую таску с собеседований в тему (правда не знаю, куда конкретно; мне её рассказывали много-много лет назад).
У вас есть функция
- rand2?
- rand36?
- rand5?
- rand10?
Все они должны строиться поверх rand6 и производных и должны возращать числа равновероятно.
1. [talk] C++ Reflection Is Not Contemplation.
Доклад Andrei Alexandrescu с CppCon 2024 про рефлексию. Чуть-чуть посмотрели на базу, посмотрели на несколько последних пропозалов и ушли в сторону в какие-то абстрактные рассуждения. В классической свободной заводной манере. Лайкнул.
2. [talk] Building Cppcheck - What We Learned from 17 Years of Development.
Автор cppcheck рассказывает про то, как развивался проект и про разные вехи на этом пути. Не прям технический доклад. Интересно посмотреть на историю известной тулзы.
3. [article] Preferring throwaway code over design docs.
Автор предлагает почаще кодить прототипы перед тем, как писать дизайн доки/писать финальное решение. Так вы получаете некоторые знания о потенциальных проблемах заранее. А ещё позиционирует смерженные pull request'ы как хорошую "документацию", т.к. они всегда актуальны для какой-то точки в истории. Со вторым я согласен. Но с первым нет. В условиях постоянной гонки и нехватки ресурсов нет времени садиться писать код для большинства фичей. А там, где ошибка стоит дороже всего (большие проекты с жёсткими дедлайнами) такой подход может сильно скушать время, т.к. для большой фичи -- большой прототип.
4. [article] Probability and Games: Damage Rolls.
В статье рассказывают про то, как из рандома делать разные распределения, чтобы потом это можно было использовать в различных игровых механиках. Начинают с базовых бросков кубика и заканчивают произвольным распределением значений. Заодно можно потыкаться во всякое интерактивное, чтобы лучше понять, как что работает.
В дополнение закину вам баянистую таску с собеседований в тему (правда не знаю, куда конкретно; мне её рассказывали много-много лет назад).
У вас есть функция
rand6(), которая равновероятно возращает целое число из отрезка [0; 5]. Как из неё сделать:- rand2?
- rand36?
- rand5?
- rand10?
Все они должны строиться поверх rand6 и производных и должны возращать числа равновероятно.
🤔1
#math #cpp #highload #common
0. [talk] YouTube Scalability.
Доклад про то, как скейлился youtube. Чувак рассказывает про основные проблемы, с которыми столкнулась [тогда ещё] небольшая команда, вплоть до невозможности загружать видео на платформу. Между делом бывают забавные вставки. Несмотря на то, что информация не везде знакомая, рассказывают очень понятно.
1. [article] 2D Visibility.
Статья рассказывает базу про то, как работает видимость в 2D пространствах. Хотя контента прям тут не прям много, внутри очень много ссылок на разные доп материалы, так что если вам такое интересно, можно зависнуть.
2. [article] Cognitive load is what matters.
Автор пишет про то, что такое когнитивная нагрузка в программировании, приводит примеры от кода до архитектуры и вбрасывает некоторые рекомендации, как же сделать лучше.
Статья большая, но полезная (хотя там есть short версия).
3. [article] End-to-end Шифрование.
Вастрик написал пост про End-to-end шифрование. В своём классикал стиле и как для тупых.
4. [article] 4 billion if statements.
Автор увидел тик-ток, где кто-то ифал каждое число, чтобы определить чётное оно или нет. И автор решил посмотреть, насколько сложно вообще такое написать. Он начал с простого ифания нескольких чисел, потом пошёл генерить код, после чего пошёл генерить asm. И после некоторых манипуляций всё заработало! Такой минизабавыч в конце.
0. [talk] YouTube Scalability.
Доклад про то, как скейлился youtube. Чувак рассказывает про основные проблемы, с которыми столкнулась [тогда ещё] небольшая команда, вплоть до невозможности загружать видео на платформу. Между делом бывают забавные вставки. Несмотря на то, что информация не везде знакомая, рассказывают очень понятно.
Доклад довольно старый. 2007-ого года. Я в школу в том году пошёл.
1. [article] 2D Visibility.
Статья рассказывает базу про то, как работает видимость в 2D пространствах. Хотя контента прям тут не прям много, внутри очень много ссылок на разные доп материалы, так что если вам такое интересно, можно зависнуть.
2. [article] Cognitive load is what matters.
Автор пишет про то, что такое когнитивная нагрузка в программировании, приводит примеры от кода до архитектуры и вбрасывает некоторые рекомендации, как же сделать лучше.
Статья большая, но полезная (хотя там есть short версия).
3. [article] End-to-end Шифрование.
Вастрик написал пост про End-to-end шифрование. В своём классикал стиле и как для тупых.
4. [article] 4 billion if statements.
Автор увидел тик-ток, где кто-то ифал каждое число, чтобы определить чётное оно или нет. И автор решил посмотреть, насколько сложно вообще такое написать. Он начал с простого ифания нескольких чисел, потом пошёл генерить код, после чего пошёл генерить asm. И после некоторых манипуляций всё заработало! Такой минизабавыч в конце.
❤9🐳2
#common #math
Наткнулся на шортлист статей (499 штук, шорт, ага) для технотекста на habr. Выбрал что-то, что зацепило названием и в итоге оказалось интересным.
0. [article] Алгоритмы манипуляций с битами.
Удаляю ещё одну идею для статьи из беклога. Потому что надо не хранить её 1.5 года, а брать и писать, а то кто-то это сделает вместо тебя.
Зато работы меньше. И сделано лучше, чем я бы сейчас мог.
1. [article] IoT Geofencing: как мы сократили время определения функциональных зон, используя H3-индексы.
Я уже как-то писал про геоиндексинг, а тут очень интересный кейс от Whoosh про то, как они используют H3 с разбором некоторых корнеров, которые меня раньше волновали. Не прям вникал в самокатную embedded специфику, но оно и не мешает.
2. [article] Нелогичные и зарегулированные города: почему нейросети плохо приживаются в городском проектировании.
Очень понятный, чуть ли не разговорный текст, в котором поясняют, почему генерация проектов в масштабах кварталов и городов с помощью любого рода ML сегодня невозможна.
Интересно, собака!
3. [article] Ловушка бесконечно ленивого бассейна.
Небольшое интересное расследование, в конце красивые графики.
Вот такие задачи в работе люблю. От них прям душа поёт.
Ну вот как-то мне больше ничего особо и не зашло. Конечно, прочитал я не всё и что-то мог упустить случайно/не очень привлекательного названия, но среди 25 вычитанных статей выбрал только эти.
Может так и надо.
Результаты тут: https://habr.com/ru/companies/habr/articles/911650/
Наткнулся на шортлист статей (499 штук, шорт, ага) для технотекста на habr. Выбрал что-то, что зацепило названием и в итоге оказалось интересным.
0. [article] Алгоритмы манипуляций с битами.
Удаляю ещё одну идею для статьи из беклога. Потому что надо не хранить её 1.5 года, а брать и писать, а то кто-то это сделает вместо тебя.
Зато работы меньше. И сделано лучше, чем я бы сейчас мог.
1. [article] IoT Geofencing: как мы сократили время определения функциональных зон, используя H3-индексы.
Я уже как-то писал про геоиндексинг, а тут очень интересный кейс от Whoosh про то, как они используют H3 с разбором некоторых корнеров, которые меня раньше волновали. Не прям вникал в самокатную embedded специфику, но оно и не мешает.
2. [article] Нелогичные и зарегулированные города: почему нейросети плохо приживаются в городском проектировании.
Очень понятный, чуть ли не разговорный текст, в котором поясняют, почему генерация проектов в масштабах кварталов и городов с помощью любого рода ML сегодня невозможна.
Интересно, собака!
3. [article] Ловушка бесконечно ленивого бассейна.
Небольшое интересное расследование, в конце красивые графики.
Вот такие задачи в работе люблю. От них прям душа поёт.
Ну вот как-то мне больше ничего особо и не зашло. Конечно, прочитал я не всё и что-то мог упустить случайно/не очень привлекательного названия, но среди 25 вычитанных статей выбрал только эти.
Может так и надо.
Результаты тут: https://habr.com/ru/companies/habr/articles/911650/
🔥5❤3😁2👍1