Алгоритмы для работы с большими данными
Всем привет! Для начала давайте разберем что такое вообще Алгоритмы для работы с большими данными, основная суть алгоритмов для работы с большими данными — это эффективная обработка огромных объёмов информации при минимальных вычислительных ресурсах (памяти, CPU, диске). Их суть — жертвовать точностью ради скорости и масштабируемости.
Привет! Сегодня в логистике мы сталкиваемся с множеством вызовов, требующих новых подходов. Глобализация, большие объёмы данных, изменчивость потребительских настроений и стремление к экономии делают традиционные способы управления недостаточно эффективными. Поэтому машинное обучение оказывается как никогда кстати и становится важным инструментом для оптимизации логистических процессов.
Традиционная организация цепочек поставок часто сталкивается с проблемами. Например, прогнозирование и планирование могут быть некорректными из-за отсутствия своевременных и точных данных. Для координации участников цепочек поставок требуются значительные, но не всегда оправданные ресурсы. Непредсказуемые обстоятельства, такие как погодные условия или колебания спроса, тоже могут приводить к сбоям. Работа вручную также повышает вероятность ошибок (человеческий фактор, куда ж без него) и снижает общую эффективность.
В данной статье мы разъясним вопрос, который, находясь в самой основе теоретического программирования, при этом парадоксальным образом очень часто объясняется неправильно или неполно, причём эти неправильные объяснения даже иногда входят в учебные пособия (по крайней мере, известный китайский чатбот не смог мне правильно ответить на вопрос об отличии машины Тьюринга от конечного автомата, хотя, казалось бы, они приходятся чатботу ближайшими родственниками, и он мог бы изучить область деятельности своих создателей в обучающей выборке).
А в конце мы немного пофилософствуем на тему, что же такое программа и что такое семантика.
Привет, Хабр!
Все мы знаем Го — глубокую, медитативную игру на доске 19x19. Камни, пересечения, территории... А что, если выкинуть саму сетку и разрешить ставить камни куда угодно в пределах доски?
Мы в команде YSDA (Yandex School of Data Analysis или Школа Анализа Данных, ШАД) задались этим вопросом и решили проверить. Получилось азартно, хаотично и, что самое главное для нас как разработчиков, — чертовски интересно с точки зрения алгоритмов.
В этой статье я расскажу, как мы реализовали эту идею на Python и Pygame, с какими геометрическими головоломками столкнулись и как Диаграмма Вороного помогает считать очки в реальном времени, превращая статичную доску в живое поле битвы.
А в конце встретим неожиданный твист! Узнаем, что такое такое Суго.
Код AI Flame Graphs теперь открыт, этот проект поддерживает GPU Intel Battlemage. Это значит, что AI Flame Graphs теперь способен генерировать flame-графики (Flame Graph, граф пламени, диаграмма пламени), охватывающие полный стек GPU — это даёт пользователям новые аналитические данные о производительности игр. Особенно полезным AI Flame Graphs выглядит в связке с FlameScope (это — мой опенсорсный проект, созданный несколько лет назад). Вот — пример профилирования игры GZDoom. Тут показаны результаты визуализации использования CPU и GPU, проведённые с помощью FlameScope и снабжённые комментариями.
На рубеже веков SIAM опубликовали список из 10 алгоритмов, оказавших наибольшее влияние на науку и индустрию в 20 веке (по мнению редакции), четверть века спустя по меньшей половина из этого списка до сих пор используется повсеместно. В статье вспомним что это за алгоритмы и за что они получили такое признание. Обсудим и алгоритмы, которые в этот список не вошли, но вполне могли бы, о чем читатели хабра написали в комментариях к статье "10 лучших алгоритмов 20 века". В конце статьи опрос, пожалуйста, не проходите мимо и отметьте или напишите в комментариях, какие алгоритмы на ваш взгляд должны были оказаться в этом списке!
Недавно опубликованная третья редакция спецификации Portable Network Graphics (PNG) 2025 года, разработанная World Wide Web Consortium (W3C), привлекла внимание к эволюции этого формата (W3C PNG Specification (Third Edition, 2025)). Ранее я, как и многие, использовал PNG, не задумываясь о его развитии и различных редакциях. Углубившись в изучение спецификаций PNG (1996, 2003, 2025), я решил подготовить данную статью, чтобы обобщить ключевые изменения и их значение для веб-дизайна, разработки игр и мультимедиа. Статья не претендует на исчерпывающий охват, но стремится предоставить полезный обзор для всех заинтересованных, включая начинающих. Приветствуются любые замечания и предложения по улучшению материала в комментариях к публикации. Весь код, приведённый ниже, выложил в репозиторий. Надеюсь, чтение будет полезным и увлекательным.
Процедурная генерация воксельных рогаликовых уровней с использованием клеточных автоматов и алгоритмов работы с сеткой ячеек на Python. Описана начальная генерация уровней, их упорядочивание, прокладка путей.
Это третья часть моих наработок по решению задачи Винтика и Шпунтика в рамках челленджа @vvvphoenix. В прошлой части мы хорошо так свернули формулу включений-исключений для ускорения вычисления ответа. В этой части мы дополнительно ускорим вычисление, разбив слагаемые формулы на классы эквивалентности, где в каждом классе слагаемые одинаковые и их надо будет вычислять только один раз. В этом нам поможет комбинаторная теория групп и её применение в задачах о раскрасках. По большей части эта статья содержит общую теорию решения подобных задач, так что эта информация может быть полезна и вне контекста задачи про Винтика и Шпунтика.
Задача
Три айтишника — Маша, Вася и Петя — пошли в поход. После ужина они решают, кто будет мыть посуду. Петя дежурит один, а Маша с Васей — вдвоём. Значит, нужно выбрать Петю с вероятностью ⅓, а Машу с Васей — с вероятностью ⅔. Под рукой — только честная монетка. Как с её помощью устроить такой жребий?
Когда мы обсуждали эту задачу со студентами, они предложили такой способ. Бросим монету дважды: если выпали два орла — дежурит Петя; если один орёл и одна решка — Маша с Васей; если две решки — перебрасываем
Чтобы выбрать дежурного так, в среднем уходит 8⁄3 броска (чуть позже мы это докажем). Можно ли сделать это быстрее? Существует ли алгоритм, для которого ожидаемое число бросков меньше?
Оказывается, можно придумать простой, но неочевидный метод, позволяющий смоделировать событие с вероятностью ⅓ — и в среднем требует не больше двух бросков. Он называется алгоритмом Кнута–Яо
В этой статье мы пройдём весь путь к этому алгоритму. Начнём с базовых методов, поймем, сколько бросков они требуют в среднем, и найдём границу, быстрее которой не может работать никакой алгоритм. А затем построим тот, который этой границы достигает — оптимальный для вероятности ⅓
В финале мы обобщим эту идею: научимся моделировать любую вероятность p от 0 до 1 — и любое дискретное распределение. Заодно познакомимся с важным понятием, называемым энтропией
А в самом конце, как всегда — красивая задача
Построить Rate Limiter — легко. Сделать его быстрым, отказоустойчивым и работающим в нескольких дата-центрах — сложнее. Делюсь опытом реализации нашего облачного Rate Limiter в DDoS-Guard: принцип работы, анализ правил и реальные примеры из практики.
Эта идея — основа для понимания моей концепции интеллекта (саморазвивающейся программы). Если интересует создание саморазвивающейся программы, то эта идея не будет лишней. В начале описание идеи, потом описание реализации и описание некоторого дополнительного функционала.
Рассказал идею о создании логики программы динамически. Причём, эта логика не представлена чисто в виде инструкций языка программирования. Она работает на основе конструкций, которые работают на основе инструкций ЯП — это абстракции над ЯП, что-то типа ЯП более высокого уровня, чем python.
В предыдущих статьях мы обосновали отсутствие детерминированной кривой спроса в недвижимости и показали, как застройщики могут использовать данные о продажах для динамического ценообразования (ДЦО) своих проектов. Мы пришли к выводу, что для решения задач ДЦО необходимо определять оптимальный темп продаж вместе с ценой, которая этот темп обеспечит.
В этой статье мы разберём самое интересное: как это сделать, и какие критерии необходимо учесть, чтобы ДЦО действительно приносило прирост ключевых финансовых метрик.
CLL в ISPA — переносимый язык семантических действий для генераторов парсеров. Объявление переменных, условий и циклов, генерация AST и кода на C++ без привязки к языку парсера. Пример, разбор и сравнение с ANTLR, Bison.
Мне очень нравится знаменитая цитата Ричарда Фейнмана:
«То, что я не могу создать, я не понимаю»
Она кажется мне великолепной, и я считаю, что она справедлива для многих областей знания (если немного творчески подойти к значению слова «создать»). Наверно, этому принципу я обязан за всё, в чём по-настоящему хорош. Кто-то скажет, что стоит стараться не изобретать велосипед, но они ошибаются: нужно изобретать собственный велосипед, потому что так вы узнаете о его устройстве больше, чем после прочтения тысячи книг.
Сегодня, в 2025 году, красота и ремесло написания ПО подвергаются разрушению. ИИ угрожает тем, что заменит нас (или, по крайней мере, заберёт все самые приятные аспекты нашего ремесла), а разработка ПО становится всё более стандартизированной, выверенной, упакованной и индустриализированной. Разработке программного обеспечения нужно больше простых удовольствий. Я выяснил, что создание хобби-программ — отличный способ снова напомнить себе, почему вообще я начал работать с компьютерами.
LLM требуют все больше данных для обучения, но обучаться постепенно становится не на чем: аппетиты ИИ-систем превосходят возможности человечества по генерации контента, к тому же использовать реальные данные в одних случаях дорого, в других — не очень-то законно.
Спасти ситуацию может «синтетика», но и с ней не все гладко. Мы в beeline cloud решили разобраться, какие риски несут в себе подобные датасеты, что такое «ML-аутофагия» и как с ней борются разработчики LLM.
Как вычислить экспоненциальную функцию быстро и с минимальной погрешностью? Пишем векторизованный код.
Разработка парсер генератора ISPA: что реализовано и какие планы на будущее.Гибкий парсер нового поколения с теми функциями, которых давно не хватает существующим решениям.
Как вы, наверно, знаете, из-за наличия в компьютере различных кэшей (L1, L2, L3...) и того, что операции с памятью выполняются с линиями кэша размером примерно 64 байт каждая, для обеспечения максимальной производительности мы должны писать программы, обеспечивающие локальность.
(Разумеется, диск здесь не показан)
Но насколько хорошо вы это осознаёте? Допустим, у нас есть массив чисел с плавающей запятой и массив индексов первого массива. Есть программа, складывающая числа из первого массива в порядке, определяемом вторым массивом. То есть в этом примере мы будем складывать ε + α + δ + ζ + β + γ в таком порядке:
Давайте рассмотрим всего два случая: индексы идут в порядке от первого до последнего или в произвольном порядке. До того, как я начал писать этот пост, я не мог ответить ни на один из следующих вопросов:
1. Насколько большим должен быть массив, чтобы разница производительности вычисления в двух порядках стала заметной?
2. Сколько в среднем тратится на каждый элемент в порядке от первого до последнего?
3. Насколько медленнее произвольный порядок последовательного в случае массивов, умещающихся в RAM?
4. Насколько медленнее произвольный порядок последовательного в случае массивов, не умещающихся в RAM?
5. Достаточно ли стандартного тасования Фишера-Йейтса для массивов перемешанных индексов для получения произвольного порядка?
6. Насколько медленнее порядок от первого до последнего в случае массивов, не умещающихся в RAM, при использовании файлов с отображением в память?
7. Максимально ли быстры файлы с отображением в память?
Если вы уже знаете ответы на эти вопросы, то это замечательно! Если же нет, то делайте ваши предположения и проверьте их, прочитав пост.
