Привет, коллеги! Сегодня будем говорить о паттерне «Мост» (Bridge).

Простыми словами, «Мост» позволяет разделить две иерархии: одну — абстракций, другую — реализаций. Паттерн становится полезен, когда есть несколько способов реализации функционала, и хочется сохранить возможность гибкой замены одной реализации на другую.

Недавно я столкнулся с забавными головоломками, связанными с простейшими двухчашечными весами. Как правило, в большей части таких задач используются монеты. Сегодня я расскажу о решении одного типа таких головоломок.

Итак, как найти одну фальшивую монету среди нескольких, сравнивая вес различных наборов монет и используя наименьшее возможное количество сравнений?

Для начала проведём анализ проблемы.

Приветствую, уважаемый читатель!

В первой части мы реализовали простейший аллокатор с минимальным оверхедом. Конечно же на самом деле все сложнее. Так реализация дефрагментации была наивной и не могла сливать блоки даже когда не было распределенных блоков после нескольких вызовов mem_free. Для того, что бы получить исходную картинку где будет только 2 служебных блока и один свободный нужно было бы вызвать mem_alloc с размером большим чем доступно памяти что бы искусственно запустить дефрагментацию. В этой части мы это исправим и напишем юнит тест для нашего аллокатора что бы убедится что он работает правильно.

Это вторая часть серии статей, посвящённой построению числовых систем, основанных на упорядоченных парах. В предыдущей статье мы рассмотрели как строится кольцо целых чисел из пары натуральных, освоившись с понятиями классов эквивалентности и факторизацией. В этой построим ещё одну знакомую числовую систему: поле рациональных чисел.

Как объяснить правила сложения, умножения и сравнения для дробей? Откуда взялись общие знаменатели, деление многоэтажных дробей, всевозможные «методы бабочки» и прочие премудрости, подстерегающие человека классе в шестом?

Материал расчитан на тех, кто учит старшеклассников или младшекурсников

Этой мини-серией статей я хочу объединить свои заметки для математического кружка о различных необычных, но полезных числовых системах, основанных на парах чисел. План знакомства с числовыми системами будет такой:

1. В этой статье мы (признаюсь, достаточно занудно) построим из натуральных чисел целые, при этом познакомимся с важнейшими инструментами математики: упорядоченной парой, эквивалентностью и факторизацией.

2. Во второй части от целых мы перейдём к рациональным числам, которые тоже можно представить в виде пары — рациональной дроби. Главный вопрос на который мы постараемся ответить: «А чего у дробей всё так сложно-то?»

3. В третьей части мы сконструируем Гауссовы числа и порассуждаем над более общим вопросом: «Что такое число?». В этой части мы перейдём от пар к матричным представлениям чисел, что позволит нам ввести их классификацию.

4. Четвёртая часть будет посвящена эллиптическим арифметикам: комплексным числам и числам Эйзенштейна. Здесь мы порассуждаем над сакраментальным вопросом: «Реальная ли мнимая единица?»

5. В пятой части мы рассмотрим гиперболические арифметики и познакомимся с двойными числами, и немного используем их на практике, чтобы понять «Как работает формула Бине?»

6. Шестая часть завершит эту серию. Она расскажет о параболических арифметиках, в частности, о дуальных числах, которые позволят арифметике быть неточной. Кроме того, мы порассуждаем о том как вписать в нашу классификацию рациональные дроби.

Впрочем, поскольку материал рассчитан на старшеклассников или младшекурсников, изложение будет неспешным и основательным. В духе туториала или методического пособия.

Третья часть (не заключительная) интервью 2001 года Ф. Франы с Э. Дейкстрой.

Продолжаем вспоминать историю программирования, которая помогает ответить на вопрос, почему оно получилось таким, а не другим. Был бы этот путь другим, если бы не политика? Теперь мы уже не сможем ответить на этот вопрос, но можем посмотреть, какая царила в то время атмосфера.

Доброго времени суток.

При разработке ОС на с++ мы сталкиваемся с рядом трудностей, таких как отсутствие стандартной библиотеки и ABI с++ и прочее в этом духе. При чем перед реализацией PageAllocator и прочих аппаратных механизмов хотелось бы иметь какую то стандартную библиотеку позволяющую делать хоть что то. Об этом и пойдет речь.

Далее я расскажу о своем опыте разработки таких алгоритмов для своей ОС и о том, как их тестировать у себя на системе с юнит тестами и прочим прикручивая в итоговую демку проверенный тестами код, и начну я с аллокатора.

Речь пойдет о немного переделанном алгоритме Кнута "неявный список блоков с граничными тегами" который описан в конце третьего тома в разделе "Распределение памяти". Его идея предельно проста:

Мы берем некоторый отрезок памяти, назовем его кучей и разбиваем его на блоки такого вида:

Если вас всё ещё преследует вопрос о том, что бы почитать в жанрах протокиберпанк, киберпанк и посткиберпанк, гляньте одним глазком в мой библиографический обзор. Почти уверен, там есть книги, которые вы ещё не прочли. Не верите? Проверьте!

Ещё статья про ассемблер для тех кто с ним не знаком. В предыдущей про 5 ассемблеров последний примерчик вызвал критику за "упрощенизм". А давайте посмотрим вместе как его улучшить и немножко нарастить - в качестве "продолжения знакомства".

Заодно полюбуемся на несовместимость Linux и BSD, а также на различие 32 и 64-битной версии обеих ОС - и подумаем как с этим бороться.

Автор не претендует на непогрешимость, поэтому приглашаем умудрённых коллег делиться идеями и подсказками в комментариях если что упущено.

Определение. Алгоритм – некоторая конечная последовательность предписаний (правил, инструкций и т.п.), однозначно определяющая процесс преобразования исходных P и промежуточных данных в результат Q решения задачи.

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

Абстракция потенциальной осуществимости. Как уже отмечалось, алгоритмический процесс при выработке результата Q из исходных данных P совершает несколько отдельных шагов. Число таких шагов может быть настолько велико, что достижение результата Q является практически неосуществимым. Однако в теории алгоритмов мы не учитываем практическую неосуществимость и считаем возможным выполнить любое конечное число шагов. Это положение называется абстракцией потенциальной осуществимости. Это же положение предполагает, что мы можем оперировать со сколь угодно большими объектами, например, сколь угодно длинными словами и т.п.

Описание алгоритмов и формулирование используемых правил могут осуществляться различными математическими средствами. Каждый способ задания алгоритма характеризуется абстрактным алфавитом и математическим формализмом. При этом вводится понятие алгоритмической системы, как общего способа задания алгоритмов

Цель проекта Boson — это разработка встроенного движка базы данных документов JSON, написанный на C++. Основные возможности: стандартное хранилище JSON-документов в формате ключ/значениями с постоянным хранением на диске. Размер документов до 4Gb. Быстрый поиск документов по ID с использованием индекса B+ дерева. Поддержка курсоров для линейного обхода записей. База данных в одном файле, без временных файлов. Простое, чистое и легкое в использовании API. Самодостаточный и не требующий настройки.

В предыдущих двух статьях мы прошли шаги от кэширования файлового ввода/вода (часть I) до построенного на его базе хранилища записей произвольной длины (часть II) с проверкой целостности, возможностью получения записей списком и повторным использованием свободного места. Теперь мы переходим к завершающей части и "сердцу" СУБД - индексу.

Зачем нужен индекс: предположим, что в базе есть 1 млрд не отсортированных записей документов, тогда поиск конкретного документа по ID потребует O(n) операций, то есть до 1 млрд операций в худшем случае. Однако, если бы документы в базе были бы отсортированы по ID, то поиск в сортированной базе, тем же бинарным поиском занял бы O(log n) занял бы 30 операций. Что, теоретически, на базе в 1 млрд записей будет в 33.3 млн раз быстрее.

Волновой алгоритм — алгоритм поиска пути, алгоритм поиска кратчайшего пути. Принадлежит к алгоритмам, основанным на методах поиска в ширину.

Волновой алгоритм — это алгоритм поиска пути, который использует волновое распространение для определения кратчайшего пути от начальной вершины до целевой вершины.

В этой статье мы не будем рассматривать основной принцип данного алгоритма (поиск кратчайшего пути), а лишь обратимся к идее волнового алгоритма. Название алгоритма происходит от способа распространения, напоминающего распространение волн.

Привет, я Антон Полухин из Техплатформы Екома и Райдтеха Яндекса. Моя команда разрабатывает userver — современный опенсорсный асинхронный фреймворк с богатым набором абстракций для быстрого и комфортного создания микросервисов, сервисов и утилит на C++.

Когда мы пишем какой‑то код для userver и для таких сложных проектов, как Boost, периодически мы сталкиваемся с нестандартными проблемами. И эти нестандартные проблемы требуют нестандартных решений. Вот о таких решениях мы сегодня и поговорим.

А именно:

— Посмотрим, как работают исключения на платформе Linux x86, и сделаем с ними что‑то интересное.

— Залезем ещё глубже под капот исключений и сделаем их ещё быстрее.

— Сделаем висячую ссылку на невалидный объект, и всё будет хорошо.

— А под конец то, что все любим, — погрузимся в шаблонное метапрограммирование.

Мышление – это процесс, т.е. протекающий и изменяющийся во времени поток состояний головного мозга (коры больших полушарий). Внешние и внутренние рецепторы организма, испытывая водействия среды, преобразуют их в электрические импульсы, направляемые в мозг. Это физиологический взгляд – по нервным волокнам «бегут» импульсы, вещества клеток (мембран) вступают в химические реакции. В сознании возникают образы, слова, высказывания. Вспоминается высказывание академика Н. Бехтеревой (директор института Мозга) о том, что ей многое понятно в механизмах мозга, в его деятельности, но у нее нет никаких гипотез о том, как в мозге возникают мысли.

Тем не менее, мысли возникают в головах людей (в сознании), обрабатываются и порой приводят к весьма замечательным результатам. Как все в окружающей нас природе, все наши мысли (в состоянии «нормы»), высказывания управляются какими-то законами и им подчинены. Возможно, часть важных законов еще до сих пор не открыта.

Многие разработчики хоть раз задумывались о том, чтобы создать свою собственную операционную систему (ОС). Это может показаться сложной задачей, но, если разбить процесс на этапы, создание минимальной ОС становится более реалистичным. В этой статье мы рассмотрим основные шаги создания простой операционной системы с нуля, а также инструменты и знания, которые могут вам понадобиться.

Несмотря на то, что программирование прочно вошло в нашу жизнь, многим оно до сих пор кажется какой-то совершенно непонятной магией. Что уж говорить о прежних временах, когда даже простой процесс хакинга в кино изображали с разными психоделическими спецэффектами, чтобы достичь «вау-эффекта».

Но в IT всегда были люди, которым мало «обычного» хардкорного кода, и они начали изобретать собственные, иногда совершенно безумные и оригинальные эзотерические языки программирования. О них мы сегодня и поговорим.