Алгоритмы *

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

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

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

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

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

Библиотека функций к Script-fu

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

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

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

Хэш-функции — невероятно красивые математические объекты. Они могут отображать произвольные данные на небольшую область выходных данных фиксированного размера таким образом, что отображение оказывается детерминированным, хоть и кажется случайным. Такая «детерминированная случайность» невероятно полезна для широкого спектра применений, например, для хэш-таблиц, контрольных сумм, алгоритмов Монте-Карло, распределённых алгоритмов без коммуникаций и так далее.

В этой статье мы взглянем на тёмную сторону хэш-функций: ситуации, когда всё идёт не так. К счастью, такое, по сути, в реальной жизни никогда не происходит из-за неудачных входных данных (по крайней мере, в случае хороших хэш-функций). Однако кроме программ существуют и люди, и не все из них настроены миролюбиво, поэтому нам следует обратиться за ответами к сфере компьютерной безопасности. Я вкратце объясню основы безопасности хэш-функций, а затем покажу, насколько легко поломать эту безопасность для некоторых популярных некриптографических хэш-фукнкций.

Для затравки скажу, что в этой статье объясняется, как генерировать за секунду тысячи подобных строк:

cityhash64("orlp-cityhash64-D-:K5yx*zkgaaaaa") == 1337 murmurhash2("orlp-murmurhash64-bkiaaa&JInaNcZ") == 1337 murmurhash3("orlp-murmurhash3_x86_32-haaaPa*+") == 1337 farmhash64("orlp-farmhash64-/v^CqdPvziuheaaa") == 1337

Также я покажу, как можно создавать очень специфичные пары строк, которые можно произвольно конкатенировать таким образом, что при конкатенации k строк любая из 2k комбинаций будет иметь одинаковый хэш вне зависимости от использованного для хэш-функции порождающего значения (seed):

a = "xx0rlpx!xxsXъВ" b = "xxsXъВxx0rlpx!"
murmurhash2(a + a, seed) == murmurhash2(a + b, seed)
murmurhash2(a + a, seed) == murmurhash2(b + a, seed)
murmurhash2(a + a, seed) == murmurhash2(b + b, seed)
a = "!&orlpՓ" b = "yǏglp$X"
murmurhash3(a + a, seed) == murmurhash3(a + b, seed)
murmurhash3(a + a, seed) == murmurhash3(b + a, seed)
murmurhash3(a + a, seed) == murmurhash3(b + b, seed)

Привет, Хабр! Меня зовут Денис Логашов, я инженер-исследователь отдела автоматической обработки результатов моделирования и визуализации YADRO. В этом году мне предложили поучаствовать в соревновании по робототехнике в дисциплине Micromouse, где роботизированной мыши нужно как можно быстрее найти путь в центр лабиринта и понять, что цель достигнута. Такие соревнования проводятся в разных странах уже почти 50 лет, и в 2023 году Micromouse вошел в программу фестиваля РобоФинист в Санкт-Петербурге. В этом году мы заняли там второе место.

Я работал в паре с другим инженером и отвечал за программную часть робота. По моим наблюдениям, меньше половины участников соревнования поняли задачу соревнования, а остальные создали типичный алгоритм прохождения лабиринта, где предусмотрен только один путь от старта до финиша. Поэтому в серии постов я расскажу, какие подходы использовал сам, чтобы решить комплексную задачу Micromouse — исследование лабиринта, построение карты и поиск кратчайшего пути.

Упаковка 2D-прямоугольников в прямоугольники большего фиксированного размера необходима в большинстве мультимедийных проектов. В программировании GPU изменение текстур (binding) — затратный процесс. Поэтому при рендеринге текста не стоит использовать по одной текстуре на глиф, вместо этого желательно упаковать глифы в единую текстуру, называемую атласом. В 2D-играх содержащие спрайты атласы называются листами спрайтов (spritesheet). Листы спрайтов также используются для веб-сайтов, потому что скачивать один большой файл удобнее, чем по одному файлу на каждый значок/логотип.

Поначалу я думал, что это достаточно нишевая проблема, но оказалось, что она влияет и на целые отрасли. Сколько рекламных объявлений можно уместить на этой странице газеты? Сколько фигур можно вырезать из этого куска дерева? Сколько посылок поместится в кузов грузовика? Поэтому задача двухмерной упаковки изучалась и в научных кругах.

Самым ценным ресурсом из найденных мной стал превосходный обзор Юкки Йулянки. В нём описано четыре типа алгоритмов и их практическая оценка. Выделяются из них два:

MAXRECTS если вы знаете заранее, какие прямоугольники будете упаковывать («офлайн-упаковка»)

SKYLINE если не знаете («онлайн-упаковка»)

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

Именно поэтому я остановился на алгоритме skyline. Он применяется в stb_rect_pack.h, fontstash, а значит, и в nanovg.

В этой статье объяснён алгоритм skyline и представлена его реализация. Реализация доступна онлайн и в общественном достоянии (UNLICENSE).

Рассмотрим одну задачу, которая на leetcode маркирована как "medium", хотя на самом деле это невероятно сложная задача. Примечательна она тем, что допускает в разной степени оптимальные решения, самые упрощённые из которых действительно весьма просты, а самые оптимальные ещё не найдены современной наукой. В этой задаче ценно то, что на её примере можно изучать целый ряд техник программирования.

Анализ подходов к решению олимпиадной задачи по программированию, связанной с диатомической числовой последовательностью Штерна. Или как незадачливый программист решил стряхнуть пыль со своих навыков и попробовал решить задачу из разряда простых с сайта https://www.spoj.com/

Этот материал посвящён исследованию восстановления текстов из текстовых эмбеддингов.

Рост популярности векторных баз данных

В последние годы наблюдается стремительное развитие генеративного искусственного интеллекта. Это привело к тому, что многие компании спешат внедрить соответствующие ИИ-инструменты в свои бизнес-процессы. Один из самых распространённых способов это сделать заключается в создании ИИ-систем, которые отвечают на вопросы, имеющие отношение к информации, которую можно найти в некоей базе данных, хранящей документы. Большинство решений этой задачи основано на подходе, называемом «генерация с дополненной выборкой»

Кто бы мог представить, что в современном мире ещё можно встретить языки программирования, в которых нет сортировки как штатной функции языка? Как себе можно вообще представить программирование без этой функции?! Ну что ж знакомьтесь, это язык tinyscheme и его GIMP порт под названием Script-fu.

Алгоритмы — они повсюду. Помните, грызли структуры данных в первую сессию? Или открывали лекции по ИТ и видели, что программирование начинается не с реальных жизненных задач.

Алгорсы — штука крайне полезная. Это быстрый легальный источник дофамина, сравнимый с прохождением хардкорной игры типа Dark Souls.

Я 6 лет преподаю ИТ-дисциплины детям, студентам и очень взрослым коллегам. В статье поделюсь, на каких сайты взбадриваюсь задачами, и как я вижу идеальный план развития алгоритмического мышления (ну вдруг вы растите дома айтишника или преподаёте сами).

Главная задача рекомендательной системы — предоставить пользователю контент, фильм, трек, книгу, товар или информацию, которые могут заинтересовать его в данный момент. Сложность в том, что у нас нет явного запроса пользователя, как в поиске, есть только история его взаимодействий с объектами и наша надежда на то, что мы верно распознали его скрытые желания.

Раньше для такой задачи нужно было строить сложные алгоритмы со множеством написанных вручную эвристик. Теперь с этим помогают ML‑технологии.

Меня зовут Кирилл Хрыльченко, я руковожу командой R&D рекомендательных технологий в Яндексе. Наша команда исследует и разрабатывает новые технологии, а также активно следит за тем, что появляется нового в индустрии. Сегодня я поделюсь трендами развития рекомендательных систем и расскажу, как нейросети продолжают улучшать качество рекомендаций: какие есть нюансы в работе с LLM, чем полезно обучение с подкреплением, что изменилось в плане анализа истории пользователя, а также на что обратить внимание при масштабировании.

Статья о том, что писал сам изобретатель Эдсгер Дейкстра о своём алгоритме поиска кратчайшего пути в первоисточнике. Приведён пример: как найти этот путь между двумя голландскими городами, которые посещал автор алгоритма.

Разбор известного алгоритма для начинающих с разбором моментов, с которыми я столкнулась. Приводится само объяснение механизма, без кода, чтобы лучше понимать саму суть. Да, поисковик выдаст 36 600 результатов при точном запросе. Но, возможно, кому‑то захочется знать историю вопроса и более неформального разбора.

Как писал сам автор алгоритма:

«Слава богу, у нас есть не только серьёзные проблемы, но и нелепые».

Как-то я исследовал способы наиболее эффективного определения простоты числа и наткнулся на показанный выше код.

Он меня заинтриговал. Хоть это, возможно, и не самый эффективный способ, но определённо один из наименее очевидных, поэтому мне стало любопытно. Каким образом соответствие регулярному выражению .?|(..+?)\1+ должно показать, что число непростое (после его преобразования в унарную систему счисления)?

Если вы заинтересовались, продолжайте чтение, я проанализирую это регулярное выражение и объясню, что же в нём происходит. Объяснение не зависит от языка программирования, однако я приведу версии показанного выше Java-кода на Python, JavaScript и Perl  и объясню, почему они немного различаются.

Я объясню, как регулярное выражение ^.?$|^(..+?)\1+$ способно отфильтровывать все простые числа. Почему это выражение, а не .?|(..+?)\1+ (использованное в примере кода на Java)? Это связано с тем, как работает String.matches(), о чём я расскажу ниже.

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

Ранжирование — это уникальная разновидность задач в машинном обучении, обособленная как от классификации, так и регрессии. Заключительная статья по нейрооптимизаторам в РСУБД, как ни странно, связана именно с ней. Бум в развитии подобных моделей произошёл совсем недавно — в 2023 году, что мы с вами подробно разберём. Сначала погрузимся в ранжирование в целом, а затем увидим, как в соответствии с новой постановкой задачи адаптировались методы поиска оптимального плана исполнения запроса.

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

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

Не только в играх вроде "Го" или "Жизнь" - но и в создании фильтров для изображений - часто нужно для клетки или точки (x, y) перечислить её "соседей". Либо только четырех (по горизонтали и вертикали), либо все восемь (с диагоналями).

Можно не задумываясь написать массивчик с 4-мя или 8-ю парами смещений, вроде
[(-1, 0), (0, 1), (1, 0), (0, -1)] - а можно ли вместо него жахнуть какую-нибудь формулу? Давайте попробуем для утренней разминки ума в понедельник :)

В этой статье будет несколько 2-3 строчных примеров кода - уж извините пожалуйста :) зато она довольно короткая.

Почему я не готовлюсь к алгоритмическому интервью

И не очень люблю людей, которые к нему готовы. Когда я провожу интервью, то главное - это понять как человек думает и как решает проблемы.

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

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

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

В этом тексте я показал как конечный автомат может работать ядром для драйвера аппаратного I2C трансивера.

Меня удивляет, что в оригинальном коде от вендоров микроконтроллеров программисты прошли мимо конечных автоматов при написании I2C кода внутри своих официальных uHAL. Непорядок...

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