Алгоритмы *

Продолжим нашу «антологию матричных расширений» текстом про независимое матричное расширение RISC-V от компании T-Head. 

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

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

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

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

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

Привет, меня зовут Надежда и я Backend-разработчик в HiFi-стриминге Звук! Занимаюсь всем, что связано с подкастами и немузыкальным контентом (а вы знаете, что в Звуке есть аудиокниги? Разработка нашей команды! PodcaTS, привет!). Какое-то время я также техлидила сервисы, которые отвечали за отдачу мета-информации и всего, что связано с аудио (артисты, релизы, треки, подкасты, аудиокниги) в Звуке.

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

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

Наткнулась на leetcode на задачку с нахождением квадратного корня из неотрицального числа.

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

Итак, условие задачи здесь: https://leetcode.com/problems/sqrtx/description/

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

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

Акцентирую внимание еще раз: массив должен быть отсортирован по возрастанию.

Если массив не отсортирован, то сортировка потребует минимум O(log n * n) временной сложности, что нужно учитывать.

Поэтому, если массив небольшой и неупорядоченный, то, скорее всего, лучше будет линейный поиск со сложностью O(n).

Итак, теперь вернемся к нашей задачке. Нужно найти квадратный корень из неотрицательного числа, где само число может быть любым от 0 до 2³¹ - 1. Если корень из числа извлекается с остатком, например, корень из 8 это 2.82842…, то нужно округлить в меньшую сторону до целого, т.е. в данном случае до 2.

Начнем, по порядку, ограничив краевые случаи. Так, если х = 0, то можно сразу вернуть 0.

Хабр, привет! Меня зовут Александр Никулин, я аспирант МФТИ и один из исследователей научной группы «Адаптивные агенты» в Институте AIRI.

Как можно понять из названия, наша группа заинтересована в создании адаптивных агентов, способных обобщаться на новые задачи после обучения. Направление это относительно новое и в литературе именуется как контекстное обучение с подкреплением (далее in‑context RL). И мы активно двигаем его вперед! Совсем недавно выпустили две статьи, обе приняты на ICML 2024, а ещё среду на JAX со множеством задач для мета‑обучения. Мы обязательно расскажем о них чуть позже (подписывайтесь!), а в этой статье хочется затронуть наш недавний препринт. В нем мы представили и выложили в open‑source огромный (по меркам RL) и пока единственный датасет для in‑context RL. На сбор траекторий для 40к задач и 130B транзиций потребовалось 50 000 GPU‑часов. Эту работу мы проделали совместно с коллегами из лаборатории T-Bank AI Research.

Датасетом уже можно пользоваться, так что рассказываем и надеемся на будущий акцепт статьи! Ну а начнем чуть издалека, расскажу что такое in‑context learning, как он появился в RL и почему нам понадобился собственный датасет.

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

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

Всем салют! Давайте решим задачу "Fruit Into Baskets"

Нужно собрать как можно больше фруктов на ферме, но с учетом правил, которые установил владелец фермы

Всем салют! Давайте решим задачу "Longest Substring Without Repeating Characters"

Дана строка s, нужно найти длину самой длинной подстроки без повторяющихся символов.

Всем привет! Меня зовут Денис Бобков, я сейчас обучаюсь на совместной магистерской программе ВШЭ и ШАД под названием «Современные компьютерные науки», а также работаю исследователем в AIRI в команде Controllable Generative AI лаборатории FusionBrain. Область моих исследований касается методов редактирования изображений.

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

Совсем недавно нашу статью приняли на одну из топ‑конференций по компьютерному зрению CVPR 2024 (эта конференция недавно стала самой цитируемой!). Наша статья про то, как можно редактировать лица в высоком качестве с помощью генеративной модели StyleGAN. Почитать её целиком можно на архиве, а здесь же я хотел кратко рассказать о том, что именно мы сделали.

Доброго времени суток, харбачитатель.

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

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

Алгоритм Хорспула используется для нахождения подстроки в строке. Например, у нас есть строка «The game is over» и подстрока «over». Алгоритм Хорспула вернет значение первого вхождения подстроки «over» в строку «The game is over», а именно 12. 

Фактически, данный алгоритм является упрощенным алгоритмом Бойера-Мура, который, считается работает лучше, чем стандартный алгоритм на случайных текстах, но в худшем случае его скорость равна |needle| * |haystack| вместо 3 х |haystack|. 

Тем не менее, для восприятия, на мой взгляд, он гораздо проще.

Итак, погнали.

Условие задачи с leetcode: https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/description/

Как работает алгоритм?

Строка и подстрока совмещаются по первому символу, и начинаются сравниваться от последнего символа к первому.

Для примера возьмем строку: «aabcdadbc» и подстроку «adb»

Совмещаются строки следующим образом (слева направо):

Привет, меня зовут Рома. Я работаю в отделе спецпроектов KTS на позиции Python backend-разработчика. 

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

TLDR

В этой статье мы научим авто самостоятельно парковаться с помощью генетического алгоритма.

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

Примерно на сороковом поколении авто начнут понимать, что такое авто-парковка, и начнут приближаться к парковочному месту:

Блокчейну приписывают три свойства: неизменяемость, распределенность и консенсус. Разберём, что обеспечивает ему эти свойства и как работает. Объясняет эксперт по машинному обучению и AI — дотошно и подробно, заглянем под капот.

Мы живём в эпоху LLM — компании применяют на практике всё более крупные модели с миллиардами параметров. Это здорово, потом что большие модели открывают пользователям сервисов новые возможности, но не всё так просто. Размер накладывает ограничения — запускать такие модели очень дорого, а на пользовательских компьютерах — ещё дороже и сложнее. Поэтому часто исследователи и инженеры сначала обучают большую модель, а потом придумывают, как сжать её с минимальными потерями качества, чтобы сделать доступнее. 

Модели выкладываются в формате float16, где на один вес выделяется 16 бит. Два года назад человечество научилось хорошо сжимать нейросети до 4 бит с помощью таких методов, как GPTQ. Но на этом исследователи не остановились, и сейчас актуальная задача — сжатие моделей до 2 бит, то есть в 8 раз. 

Недавно исследователи Yandex Research совместно с коллегами из IST Austria и KAUST предложили новый способ сжатия моделей в 8 раз с помощью комбинации методов AQLM и PV-tuning, который уже доступен разработчикам и исследователям по всему миру — код опубликован в репозитории GitHub. Специалисты также могут скачать сжатые с помощью наших методов популярные опенсорс-модели. Кроме того, мы выложили обучающие материалы, которые помогут разработчикам дообучить уменьшенные нейросети под свои сценарии.

О том, как исследователи пришли к сегодняшним результатам, мы расскажем на примере двух «конкурирующих» команд и их state-of-the-art алгоритмов сжатия — QuIP и AQLM. Это короткая, но увлекательная история «противостояния» исследователей, в которой каждые пару месяцев случаются новые повороты, появляются оптимизации и оригинальные подходы к решению проблем.

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

Рекурсивные методы в Java — это методы, которые вызывают сами себя и требуют осторожности с их обращением.

Чтобы не увидеть «StackOverflowError» на экране, нужно помнить о двух штуках: базисе и шаге рекурсии.

Базис — это условие выхода из рекурсии, а шаг — это вызов методом самого себя с измененными параметрами.

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

Поисковые системы — без них не представить сегодняшний мир, они облегчают доступ к информации и улучшают пользовательский опыт. Однако, чтобы поисковая система работала эффективно, необходимы некоторые алгоритмы для обработки строк. Одни из них — Knuth-Morris-Pratt и Boyer-Moore.

Их мы и рассмотрим в сегодняшней статье, начнем с первого.