Алгоритмы *

Привет всем любителям size coding, сегодня я расскажу о чём-то потрясающем: крошечном движке трассировки лучей (raycasting) и генераторе города, умещающихся в автономном файле HTML размером 256 байтов.

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

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

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

▍ Зачем ограничивать частоту?

Хабр, привет! Это снова Антон Разжигаев, аспирант Сколтеха и научный сотрудник лаборатории Fusion Brain в Институте AIRI, где мы продолжаем углубляться в изучение языковых моделей. В прошлый раз мы выяснили, что эмбеддинги трансформеров-декодеров сильно анизотропны. На этот раз я бы хотел рассказать об их удивительной линейности, ведь нашу статью про обнаруженный эффект («Your Transformer is Secretly Linear») несколько дней назад приняли на международную конференцию ACL!

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

Учёные, занимающиеся информатикой, — это требовательная группа. Им недостаточно получить правильный ответ — цель почти всегда состоит в том, чтобы получить ответ как можно эффективнее.

Возьмем, к примеру, умножение матриц или массивов чисел. В 1812 году французский математик Жак Филипп Мари Бине разработал базовый набор правил, которым мы до сих пор обучаем студентов. Это работает прекрасно, но другие математики нашли способы упростить и ускорить процесс умножения матриц.

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

Внимание! В статье много картинок.

Шёл 2022 год. Я обратил внимание на новый интересный проект CUTLASS, отличающийся очень высокой скоростью выполнения операций умножения матриц. Я взял большую задачу по умножению матриц — 8192 x 8192 x 8192, и померял производительность в PyTorch, где используется библиотека cuBLAS.

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

Почему собственный? Я искал подобное решение, но не нашел, возможно, оно уже было реализовано, просто плохо поискал. Жду Нобелевскую премию =)

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

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

Меня зовут Андрей Сюткин, и я отвечаю за ML-трек в Нейро. В этой статье покажу, как выглядит архитектура Нейро и как формируются ответы на технологическом уровне. Ну и, конечно же, поговорим о нейросетях, в том числе о YandexGPT 3, без обучения которых новый сервис просто не увидел бы свет.

У каждого разработчика есть набор инструментов для решения различных задач. Однако со временем возникает необходимость расширять этот набор, чтобы эффективно справляться с более сложными задачами. В этой статье я хочу познакомить вас с инструментом, которым вы, скорее всего, раньше не пользовались. И хотя он подходит для решения узкого спектра задач, его использование может оказаться весьма полезным. Знакомьтесь — "фильтр Блума" (Bloom filter).

Привет, я создатель известного в узких кругах приложения 15 Puzzle для Android.

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

С момента выхода первой статьи «Attention is All You Need» я с жадностью и любопытством, присущими любому исследователю, пытаюсь углубиться во все особенности и свойства моделей на базе архитектуры трансформер. Но, если честно, я до сих пор не понимаю, как они работают и почему так хорошо обучаются. Очень хочу разобраться, в чём же причина такой эффективности этих моделей, и есть ли предел их возможностей?

Такому изучению трансформеров «под микроскопом» и посвящена наша научная работа, только что представленная на конференции EACL 2024, которая проходила на Мальте — «The Shape of Learning: Anisotropy and Intrinsic Dimensions in Transformer-Based Models». В этой работе мы сфокусировались на наблюдении за пространством эмбеддингов (активаций) на промежуточных слоях по мере обучения больших и маленьких языковых моделей (LM).

На сайте hackerrank.com есть отличная задача. По заданному массиву short[] A; найти максимальное количество его подмассивов, xor элементов которых будет одинаковым. Сам этот xor тоже нужно найти.

Максимальная длина массива равна 10⁵, так что квадратичный алгоритм не укладывается в лимит по времени исполнения. Я в своё время с этой задачей не справился и сдался, решив подсмотреть авторское решение. И в этот момент я понял почему не справился — автор предлагал решать задачу через дискретное преобразование Фурье.

Привет! Меня зовут Василий Землянов, я занимаюсь разработкой ML-инфраструктуры. Несколько лет я проработал в команде, которая делает споттер — специальную маленькую нейросетевую модельку, которая живёт в умных колонках Яндекса и ждёт от пользователя слова «Алиса». Одной из моих задач в этой команде была квантизация моделей. На пользовательских устройствах мало ресурсов, и мы решили, что за счёт квантизации сможем их сэкономить — так в итоге и вышло.

Потом я перешёл в команду YandexGPT. Вместо маленьких моделей я стал работать с очень крупными. Мне стало интересно, как устроена квантизация больших языковых моделей (LLM). Ещё меня очень впечатляли истории, где люди берут гигантские нейросети, квантизируют в 4 бита и умудряются запускать их на ноутбуках. Я решил разобраться, как это делается, и собрал материал на доклад для коллег и друзей. А потом пришла мысль поделиться знаниями с более широкой аудиторией, оформив их в статью. Так я и оказался на Хабре :)

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

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

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

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

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

Я немного опоздал, соревнования проводились в январе. И на Java. Меня не особо интересует Java, зато давно интересует оптимизация кода на Go.

Этот челлендж был очень прост: обработать текстовый файл названий метеорологических станций и температур, и для каждой станции вывести минимальное, среднее и максимальное значение. Чтобы упростить задачу, было ещё несколько ограничений, однако я проигнорировал те, что относятся только к Java.

Здравствуйте!

Расскажу о серии задач, которая случайно возникла в процессе решения другой задачи. Мне на глаза попалось равенство:

81 * 27 = 2187

– Интересно, – подумал я. – А бывают ли ещё такие числа, чтобы цифры слева и справа повторялись?

Это история про то, как не довести дело до конца, но получить уйму опыта, и вообще ни разу не обломаться.

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

Осторожно, очень много картинок!