Обновить
265.04

Алгоритмы *

Все об алгоритмах

Сначала показывать
Порог рейтинга
Уровень сложности

Это база. Алгоритмы сортировки для начинающих

Время на прочтение11 мин
Охват и читатели48K

Привет! В этой статье я расскажу о двух алгоритмах сортировки: Quick Sort и Merge Sort. Объясню, как они работают, как выглядят примеры кода на Python и Java, а также — как выбрать подходящий алгоритм под ваши задачи. Подробности — под катом.
Читать дальше →

Сорок мегабайт простоты

Уровень сложностиПростой
Время на прочтение2 мин
Охват и читатели15K

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

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

Без лишних предисловий - найдено 52-ое известное простое число Мерсенна!

Какое-какое число?

QR-код: улучшение считывания на сложных поверхностях

Время на прочтение13 мин
Охват и читатели1.3K


Одним из направлений, на которое непосредственно влияет технологический прогресс, является передача информации. В каком виде она передается, каким методом, насколько быстро и как считывается — все это зависит от уровня доступных технологий. Ярким примером того является QR-код, появившийся в начале 90-ых в Японии и ставший одним из самых популярных методов передачи небольшой информации. В наши дни QR-код можно встретить и на упаковках различных товаров, и на рекламных буклетах, и на визитках и т. д. Однако, несмотря на свою универсальность и простоту, QR-код может столкнуться с проблемой считывания, связанной с топологией поверхности, на которую он нанесен. Ученые из Барселонского университета (Испания) разработали новую методологию улучшения считывания QR-кодов, основанную на подгонке топографии базовой произвольной поверхности с помощью тонкопластинчатых сплайнов. Как именно ученые пришли к созданию этого метода, и насколько он эффективен? Ответы на эти вопросы мы найдем в докладе ученых.
Читать дальше →

Популярный, но неправильный способ перевода строки в нижний регистр

Уровень сложностиПростой
Время на прочтение3 мин
Охват и читатели4.5K

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

Но он ошибочен по многим причинам.

Во-первых, std::tolower — это неадресуемая функция. Среди прочего, это значит, что мы не можем брать адрес функции, как мы делаем это здесь, когда передаём указатель на функцию std::transform. То есть нам нужно использовать лямбду.

Читать далее

Почему важно оптимизировать формат данных

Уровень сложностиСредний
Время на прочтение21 мин
Охват и читатели12K
image

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

Алгоритмы — важнейшая часть программы: замена «горячего» алгоритма O(n) менее сложным, например, O(log n), обеспечивает практически произвольное увеличение производительности. Однако существенно влияет на производительность и структурированность данных: программы выполняются на физических машинах с физическими свойствами, например, разными задержками чтения/записи данных в кэши, на диски или в ОЗУ. После оптимизации алгоритмов стоит изучить эти свойства, чтобы достичь наибольшей производительности. Оптимизированный формат данных учитывает используемые алгоритмы и паттерны доступа при выборе того, как сохранять структуру данных на физическом носителе. Благодаря этому можно увеличить скорость алгоритмов в несколько раз. В этом посте мы покажем пример, в котором нам удалось достичь четырёхкратного повышения скорости чтения простым изменением формата данных в соответствии с паттерном доступа.

Сравнение хранилищ данных AoS и SoA


Современное оборудование, и, в частности CPU, спроектировано так, чтобы обрабатывать данные определённым образом. Расположение данных в памяти влияет на то, насколько эффективно программа сможет использовать кэш CPU, как часто она сталкивается с промахами кэша и насколько оптимально она сможет задействовать векторные команды (SIMD). Даже при использовании оптимальных алгоритмов выбор неподходящего формата данных может приводить к частым перезагрузкам кэша, простаивающим конвейерам и чрезвычайно большому объёму передач содержимого памяти; всё это снижает производительность.
Читать дальше →

Как готовить EdgeAI в 2024/2025 году

Уровень сложностиСредний
Время на прочтение14 мин
Охват и читатели4.9K

Есть у меня такое развлечение - разные платы для AI тестировать.

Очень много того с чем я работаю - про Computer Vision на Edge. В какой то момент я понял что мне не хватает информации. Нет ничего кроме восторженного пресс-релизов. Дай бог ещё есть видео как официальные примеры запускают. Но обычно без этого.

Так что в какой-то момент начал тестировать всё сам. Просто чтобы понимать какие есть альтернативы, что можно а что нельзя.
Иногда (раз в год-два) я пишу обзорную статью. И это именно она. Тут я попробую рассмотреть критерии, которые можно считать важными для AI плат. А так же кратко рассмотреть основные платы на рынке.

Читать далее

Как извлечь квадратный корень из перестановки чисел?

Уровень сложностиСредний
Время на прочтение4 мин
Охват и читатели5.5K

В этой статье мы исследуем проблему извлечения квадратного корня из перестановки p, иными словами задачу нахождения всех таких перестановок x, что x \cdot x = p. Будет сформулирован критерий возможности извлечения квадратного корня, алгоритм нахождения корней и формула их подсчёта в общем виде.

Читать далее

Учимся читать QR-коды без компьютера

Уровень сложностиСредний
Время на прочтение4 мин
Охват и читатели42K

Задавались ли вы когда-нибудь вопросом, как работают QR-коды? Если да, то эта статья для вас. Здесь вас ждёт интерактивное объяснение*, которое мы составили для семинара, проводившегося в рамках Всемирного конгресса хакеров 37C3, но вы также можете использовать его самостоятельно.

Прочитав статью, вы узнаете:

  • Из чего состоят QR-коды.
  • Как декодировать QR-коды вручную (используя нашу шпаргалку).
Читать дальше →

В поиске собственных значений (матриц)

Уровень сложностиСредний
Время на прочтение10 мин
Охват и читатели7.4K


Как найти собственные числа и собственные значения матрицы? Методы, излагаемые в курсе линейной алгебры, основанные на определении — применимы ли они к реальным данным? Существует ли простой алгоритм поиска этих величин, который можно понять, а не просто поверить?
Об этом мы поговорим под катом

Вычисления на RISC-V: исследуем производительность OpenCL на CPU и совместимых GPU

Уровень сложностиСложный
Время на прочтение12 мин
Охват и читатели3.2K

Привет! Меня зовут Михаил Козлов, я инженер-стажер в группе разработки математических библиотек в YADRO. Эта сфера активно развивается на RISC-V: известные математические библиотеки, такие как OpenBLAS, Eigen и многие другие, портируют и оптимизируют под открытую архитектуру. Большой интерес представляет OpenCL — открытый стандарт разработки программного обеспечения для гетерогенных вычислений. Он используется во многих областях: HPC, AI/ML, AR/VR, линейной алгебре, где он наиболее широко представлен с помощью библиотек clBLAS и CLBlast. 

В линейной алгебре OpenCL наиболее широко представлен с помощью библиотек clBLAS и CLBlast. Первая — более старая, вторая — более современная, со встроенным тюнером для оптимизации под конкретное железо. Далее я расскажу о своем проекте с летней стажировки: исследовании производительности этих библиотек на GPU

Читать далее

Нейронные оптимизаторы запросов в реляционных БД (Часть 2): На пути к продуктивизации

Уровень сложностиСредний
Время на прочтение11 мин
Охват и читатели3.6K

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

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

Читать далее

Графы, растры и море: как школьники создают будущее геоаналитики

Уровень сложностиСредний
Время на прочтение6 мин
Охват и читатели1.9K

Привет, Хабр! Меня зовут Алексей Пустынников, я руководитель команды геоаналитики в банке ВТБ. Сегодня я хочу рассказать вам об интересном проекте, в котором участники конкурса «Большие Вызовы» решали сложные задачи в сфере геоаналитики и машинного обучения.

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

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

Читать далее

VLM в Нейро: как мы создавали мультимодальную нейросеть для поиска по картинкам

Время на прочтение11 мин
Охват и читатели13K

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

Меня зовут Роман Исаченко, я работаю в команде компьютерного зрения Яндекса. В этой статье я расскажу, что такое визуально‑текстовые мультимодальные модели (Visual Language Models или VLM), как у нас в Яндексе организован процесс их обучения и какая у них архитектура. Вы узнаете, как Нейро работал с картинками и текстами раньше, и что изменилось с появлением VLM.

Читать далее

Ближайшие события

Causal Inference: прозрение и практика. Лекция 2. Рандомизированные контролируемые испытания

Уровень сложностиСложный
Время на прочтение8 мин
Охват и читатели1.3K

Предыдущая лекция.

Рандомизированные контролируемые испытания (РКИ) представляют собой наиболее объективную, прозрачную и эффективную методологию для проведения экспериментов. Они пользуются огромной популярностью и применяются в самых разных сферах, включая науку, медицину, маркетинг и технологии. С их помощью учёные и специалисты могут проверять эффективность новых методов лечения, лекарственных препаратов, продуктов или услуг, сравнивая результаты между двумя или более группами. РКИ встречаются гораздо чаще, чем может показаться на первый взгляд. Это невероятно популярный метод исследования причинно‑следственных связей. Хотя они довольно просты в реализации, их точность значительно превосходит все другие методы аппроксимации ATE.

Читать далее

Книга: «Грокаем алгоритмы. 2-е изд.»

Время на прочтение5 мин
Охват и читатели20K
image Хаброжители, привет!

Мы снова возвращаемся с вторым изданием книги “Грокаем алгоритмы”! Красивым, новеньким, актуализированным. От первого тиража всё ещё пахнет типографией, а код примеров обновлен на Python 3!

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

Читать дальше →

Causal Inference: прозрение и практика. Лекция 1. Основные понятия Causal Inference

Уровень сложностиСложный
Время на прочтение11 мин
Охват и читатели4.2K

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

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

Однако со временем стало ясно, что для полного понимания данных необходимо научиться объединять эти два подхода. Здесь на сцену выходит причинно‑следственный вывод (Causal Inference). Эта область Data Science помогает раскрыть причины явлений, объединяя преимущества как машинного обучения, так и эконометрики. Judea Pearl в своей статье 2021 года подчеркивает важность причинно‑следственного вывода как «ключевого элемента для достижения баланса между радикальным эмпиризмом ML и интерпретационным подходом эконометрики».

Таким образом, Causal Inference — это область статистики и научных исследований, направленная на выявление и измерение причинно‑следственных связей между переменными. Она помогает определить, какое воздействие оказывает изменение одной переменной на другую, отличая это воздействие от простых корреляций.

Читать далее

PostgreSQL Antipatterns: устраняем вложенные интервалы

Уровень сложностиПростой
Время на прочтение5 мин
Охват и читатели5.1K

Недавно попался на глаза запрос, которым хотели отобрать в таблице (очевидно, для последующего удаления) все id записей интервалов, которые полностью перекрыты каким-то другим интервалом того же owner'а.

Но self-JOIN показал себя не лучшим образом...

Как сделать эффективнее?

Визуализатор музыки на основе игры Pong

Время на прочтение5 мин
Охват и читатели1.4K

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

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

Также мы сохраним следующие правила классической игры:

  • Точка контакта мяча с ракеткой определяет угол отражения
  • У ракеток нет ограничений по скорости
  • Мяч отскакивает от верха и низа экрана

Такая физика обеспечивает нам необходимое число степеней свободы для перемещения ракеток, чтобы они ударяли по мячу в нужный момент.

Простая стратегия попадания в любой тайминг — это нахождение ракеток близко к центру. Это даёт нам мало места по горизонтали, но вертикальное пространство практически бесконечно, ведь мяч может отскакивать от нижнего и верхнего краёв экрана. Для получения любой нужной длительности удара мы можем замедлять горизонтальную скорость, ударяя по мячу более вертикально. Но хотя это доказывает, что решение существует для любых входных данных, смотреть на него было бы не очень интересно.
Читать дальше →

Как устроен робот-доставщик Яндекса: от восприятия до планирования движения

Время на прочтение15 мин
Охват и читатели26K

Уже пять лет по улицам Москвы колесят роботы‑курьеры Яндекса, доставляя нам еду из любимых ресторанов и магазинов быстрее, чем мы успеваем проголодаться. На пути им встречается много препятствий: от безобидной клумбы, которую можно просто объехать, до восторженных детей (и иногда взрослых), от которых порой не так просто уехать.

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

Привет, меня зовут Тая, и я ML‑разработчик в команде восприятия робота‑доставщика. Сегодня я впервые детально расскажу о технологиях, благодаря которым робот‑доставщик Яндекса успешно доставляет заказы. Разберу ключевые компоненты системы, от сенсоров до алгоритмов принятия решений, и объясню, как они взаимодействуют. Из статьи вы узнаете, что происходит «под капотом» нашего робота во время его путешествий по городу.

Готовы погрузиться в мир автономной доставки?

Поехали!

Знакомьтесь, «Незнакомое». Как мы сделали новый режим для Моей волны

Время на прочтение8 мин
Охват и читатели5.6K

Привет! Меня зовут Савва Степурин, я старший разработчик в группе рекомендательных продуктов в Фантехе Яндекса. Сегодня расскажу вам про то, как мы сделали «Незнакомое» для Моей волны — специальный режим для активного поиска музыкальных открытий.

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

Под катом — техническая эволюция «Незнакомого» от фильтра до отдельного продукта, описание новой модели ранжирования и многое другое.

Читать далее

Вклад авторов