Алгоритмы *

Полезный алгоритм построения плоскости по облаку точек МНК. Я проверял этот алгоритм на устойчивость к самым разным наборам входных данных.

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

Всё это звучит здорово, но стоять на месте никак нельзя. Поэтому мы постоянно работаем над всякого рода улучшениями и оптимизациями. Зачастую новые фичи хранят под капотом не самую тривиальную идею. И сегодня я хочу рассказать о нескольких таких улучшениях, которые мы затащили в виде новых фич в последнем релизе. 

В этой статье разберёмся, как работает xor-фильтр, в чём особенность чанкового хеш-индекса и как overload controller повышает стабильность работы. Все примеры разберём на примере YTsaurus, но они будут полезны любому разработчику СУБД.

Прошлый год в Computer Vision запомнился тем, что появилось множество больших претрейненных сетей (Fondation Models). Самая известная - GPT4v (ChatGPT с обработкой изображений).
В статье я попробую простым языком объяснить что это такое (для тех кто пропустил), как меняет индустрию. Какие задачи стало проще решать. Какие продукты появились в последнее время и появятся в будущем.
И можно ли уже выгнать на мороз лишних "ресерчеров"?!

• О чем на самом деле спрашивают на собеседовании по System Design в МО и почему (инсайдерская информация!).
• 7 основных шагов для решения любой задачи МО, предлагаемой на собеседовании.
• 10 вопросов из реальных собеседований по System Design в МО с подробным разбором ответов.
• 211 диаграмм, которые наглядно объясняют, как работают различные системы.

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

Привет, Хабр! Меня зовут Ричард, я работаю в команде kPHP в VK, занимаюсь разработкой kPHP, плагинов для IDE, а также другого инструментария, делая жизнь разработчиков проще. В своей работе мне приходится иметь дело с PSI деревьями, AST, самописными структурами данных и их модификациями, и даже QuickSelect (и более сложные алгоритмы) мне доводилось реализовывать. Хочу немного поговорить про один из краеугольных, пожалуй, камней в IT, а именно про «алгоритмы и структуры данных» — тема не теряет актуальности со времен появления Хабра. Заранее оговорюсь, мой пост на 90% состоит из личного опыта во время обучения, работы и преподавания.

Задание: необходимо прочитать Micro QR Code версии М3, содержащий кодовое слово, на примере закодированных слов – АБВГДЕ, абвгде, АБВГ и абвг (почему именно такое количество символов будет расшифровано далее), на основе алгоритмов, приведенных в ГОСТ Р ИСО/МЭК 18004-2015 (п. 7.4, алфавитно-цифровой и/или байтовый режим). Аналогично версий М1 и М2 данный режим невозможно прочитать стандартными ресурсами мобильных устройств, производимых GAFAM (Ассоциация отказалась и от этого режима).

Примечание: здесь и далее будет использоваться информация ГОСТ Р ИСО/МЭК
18004-2015, в оригинале ISO/IEC 18004:2015 кодовой таблицы кириллицы не существует...

В конце прошлого года я писал о том, как с помощью Algopack можно вытащить справочную информацию о всех акциях Мосбиржи. Приводил пример моего первого скрипта на python, использующего библиотеку moexalgo для Algopack и обозначил планы дописать его с целью добычи всех исторических данных.

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

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

Cитуация, когда недостаток производительности пытаются покрыть новым железом, не редка. Важно понимать, однако, что железо, которое мы использовали и используем сегодня, содержит в себе множество механизмов, способных актуализировать наш код на года вперед. В моем понимании программист, умеющий грамотно оперировать этими механизмами(в частности в терминах бизнес процессов, требующих 'Здесь и Сейчас', терминах поиска золотой середины между Скоростью и Дизайном) - профессионал. В этой статье речь пойдет про довольно изъезженную и, казалось бы, понятную тему - тему сортировок, но с одним небольшим дополнением - SIMD. Эту тему я выбрал не случайно: в процессе решения довольно важной для индустрии задачи возникла следующая подзадача: есть входное множество целых чисел. Каждому множеству сопоставлено свое уникальное значение. При этом множества элементов, которые отличаются между собой только порядком следования элементов, а не их значениями, считаются одинаковыми и должны возвращать одно и тоже значение. Одно из решений - посортировать множества, а затем использовать результат как ключ в Хеш Таблице. Одно из важных ограничений - количество элементов в множестве не превышает 128 элементов. Под катом рассказываю о том, как сортировать такие множества быстро.

Продолжаем публикацию лекций Олега Степановича Козлова с кафедры Ядерные Энергетические Установки МГТУ им. Баумана. Вторая часть лекции про качество САР и модель реактора как бонус.

В предыдущих сериях:

1. Введение в теорию автоматического управления.
2. Математическое описание систем автоматического управления 2.1 — 2.3, 2.3 — 2.8, 2.9 — 2.13.
3. ЧАСТОТНЫЕ ХАРАКТЕРИСТИКИ ЗВЕНЬЕВ И СИСТЕМ АВТОМАТИЧЕСКОГО УПРАВЛЕНИЯ РЕГУЛИРОВАНИЯ. 3.1  Амплитудно-фазовая частотная характеристика: годограф, АФЧХ, ЛАХ, ФЧХ. 3.2 Типовые звенья систем автоматического управления регулирования. Классификация типовых звеньев. Простейшие типовые звенья. 3.3 Апериодическое звено 1–го порядка инерционное звено. На примере входной камеры ядерного реактора. 3.4 Апериодическое звено 2-го порядка. 3.5 Колебательное звено. 3.6 Инерционно-дифференцирующее звено. 3.7 Форсирующее звено. 3.8 Инерционно-интегрирующее звено (интегрирующее звено с замедлением). 3.9 Изодромное звено (изодром). 3.10 Минимально-фазовые и не минимально-фазовые звенья. 3.11 Математическая модель кинетики нейтронов в «точечном» реакторе «нулевой» мощности. 
4. Структурные преобразования систем автоматического регулирования.
5. Передаточные функции и уравнения динамики замкнутых систем автоматического регулирования (САР).
6. Устойчивость систем автоматического регулирования. 6.1 Понятие об устойчивости САР. Теорема Ляпунова. 6.2 Необходимые условия устойчивости линейных и линеаризованных САР. 6.3 Алгебраический критерий устойчивости Гурвица. 6.4 Частотный критерий устойчивости Михайлова. 6.5 Критерий Найквиста.
7. Точность систем автоматического управления. Часть 1 и Часть 2
8. Качество переходного процесса. Часть 1 

Вам когда-нибудь приходилось задаваться вопросом, как работает компилятор, но так руки и не дошли разобраться? Тогда этот текст для вас. Мне тоже не доводилось заглядывать под капот, но тут так случилось, что мне нужно прочитать курс лекций о компиляторах местным третьекурсникам. Кто встречался с некомпетентными преподавателями? Здравствуйте, это я :)

Итак, чтобы самому разобраться в теме, я собираюсь написать транслятор с эзотерического языка программирования wend (сокращение от week-end), который я только что сам придумал, в обычный ассемблер. Задача уложиться в несколько сотен строк питоновского кода. Основной репозиторий живёт на гитхабе (не забудьте заглянуть в мой профиль и посмотреть другие tiny* репозитории).

Формализация бизнес-процессов алгебраическими выражениями полвека будоражит умы математиков и методологов BPM (Business Process Management, ранее называемое CASE). Однако появление разнообразных алгебр процессов не добавили в практику BPM алгебраического формализма.

Алгебра алгоритмов (алгоритмическая алгебра Глушкова [GLU78], включая формализацию параллелизма), Алгебра \ исчисление процессов (CCS \ pi-calculus, CSP, ACP и др.), «Исчисление функций» (УФО, [UFO14]) не позволяют говорить о формальной (математической) теории BPM, а также инструменте, применимым бизнес-аналитиком на практике, т.е. об Алгебрах \ исчислениях бизнес-процессов - как математических абстракциях, формализующих workflow \ docflow и другие составляющие бизнес-процессов (Алгебре \ исчислении workflow).

Всем салют!

Хочу рассказать вам историю о том, как я начинал с уровня — «не могу решить даже 1 easy задачу из 10» до уровня — «могу решить каждую вторую medium задачу» и прошел несколько coding сессий в таких компаниях как Meta, Booking, Careem, Avito...

Цель статьи осветить state of the art методы сжатия целых чисел, чтобы сэкономить в будущем время исследования алгоритмов и терминологии. При этом описание части алгоритмов может быть упрощено для понимания. Сравнение алгоритмов тоже находится вне рамках этой статьи. Подробнее можно почитать в ссылках.

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

Кратко о правилах: игроки поочерёдно ставят точки двух цветов в перекрестия линий. Цель — окружить точки соперника замыканием вокруг них непрерывной цепи своих точек.

Пример реализации метода быстрого марша(Fast Marching Method) для создания полей расстояний(Distance FIeld) и поиска кратчайшего пути.

Привет, Хабр!

Сейчас, когда вы слышите про ИИ в шахматах, наверняка первое, что приходит в голову – это AlphaZero, который "научился" играть в шахматы, превзойдя чемпионов мира, не имея никакого предварительного знания об игре. Но позвольте, это же только верхушка айсберга!

Не будем тратить время на объяснение того, как двигаются фигуры – это вы и так знаете. В сегодняшней статьи мы разберем алогоритм Minimax.

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

Стоит ли использовать специальные алгоритмы?

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

Если у нас хайлоад и метод находится в горячей секции, там самописные алгоритмы могут быть очень полезны, и использование более сложного в поддержке кода вполне оправдано.
В других случаях, я бы не стал торопиться добавлять алгоритмы, во всяком случае до проведения нагрузочных тестов, просмотра метрик системы и прочего.
В этой статье я постараюсь показать почему использование самописного алгоритма не всегда оправдано, даже если он работает значительно быстрее. А также предложу некоторый компромиссный вариант оптимизации.

Задание: необходимо создать кодовое слово (сокращенный вариант собственной фамилии и инициалов) по алгоритму А.С. Пушкина. Затем создать для полученного сокращения Micro QR Code вер. М2. Данный режим невозможно прочитать стандартными ресурсами мобильных устройств, производимых GAFAM (как оказалось, свободно распространяемые библиотеки просто страшно глючат, поэтому Ассоциация отказалась и от этого режима)