Все потоки
Поиск
Написать публикацию
Обновить
180.06

Алгоритмы *

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

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

256 байт веселья, или как развлечь себя Ассемблером когда скучно

Уровень сложностиСредний
Время на прочтение15 мин
Количество просмотров29K

Это еще одна статья про демосцену, сайзкодинг, ассемблер, MS‑DOS и ретрокодинг. То есть, о том, как ночами напролет добровольно и бесплатно писать бесполезный и очень трудоемкий код, и получать от этого массу удовольствия (и седую бороду). Даже если вы уже пробовали и вам не понравилось, вам все равно стоит почитать. Возможно, вы что‑то делали не так. Например, использовали не те буквы и цифры. А еще тут есть подборка «демок» размером в 256 байт!

Читать далее

Сортировка «Милосердный Сталин»

Уровень сложностиСредний
Время на прочтение7 мин
Количество просмотров26K

Merciful Stalin Sort (сортировка «Милосердный Сталин») — это новый алгоритм сортировки, вдохновлённый пресловутым Stalin Sort (сталинской сортировкой). В ходе развлекательного эксперимента со сталинской сортировкой возникла интригующая идея: что, если вместо удаления выбивающихся элементов, сохранить те, которые идут по порядку, и рекурсивно упорядочить остальные? Логика заключалась в том, чтобы добиться повышения производительности за счёт уменьшения массива, требующего сортировки, особенно в случае частично упорядоченных массивов. Это и привело к разработке сортировки «Милосердный Сталин».
Читать дальше →

Как линейная алгебра помогла мне в разработке интерактивного редактора диаграмм

Уровень сложностиПростой
Время на прочтение9 мин
Количество просмотров12K

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

Читать далее

Элегантная математика фильтров Блума

Уровень сложностиСредний
Время на прочтение7 мин
Количество просмотров15K

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

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

Разбор регулярного выражения, проверяющего простоту чисел

Уровень сложностиПростой
Время на прочтение16 мин
Количество просмотров11K

Как-то я исследовал способы наиболее эффективного определения простоты числа и наткнулся на показанный выше код.

Он меня заинтриговал. Хоть это, возможно, и не самый эффективный способ, но определённо один из наименее очевидных, поэтому мне стало любопытно. Каким образом соответствие регулярному выражению .?|(..+?)\1+ должно показать, что число непростое (после его преобразования в унарную систему счисления)?

Если вы заинтересовались, продолжайте чтение, я проанализирую это регулярное выражение и объясню, что же в нём происходит. Объяснение не зависит от языка программирования, однако я приведу версии показанного выше Java-кода на PythonJavaScript и Perl  и объясню, почему они немного различаются.

Я объясню, как регулярное выражение ^.?$|^(..+?)\1+$ способно отфильтровывать все простые числа. Почему это выражение, а не .?|(..+?)\1+ (использованное в примере кода на Java)? Это связано с тем, как работает String.matches(), о чём я расскажу ниже.

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

Читать далее

Почему я не готовлюсь к алгоритмическому интервью

Уровень сложностиПростой
Время на прочтение7 мин
Количество просмотров50K

Почему я не готовлюсь к алгоритмическому интервью

И не очень люблю людей, которые к нему готовы. Когда я провожу интервью, то главное - это понять как человек думает и как решает проблемы.

К собеседованию

Записываем PNG без мам, пап и внешних библиотек

Время на прочтение9 мин
Количество просмотров18K

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

Формат изображения PNG известен с 1996 года, а на Хабре опубликовано несколько статей о декодировании этого формата. И ни одной — о кодировании. Я расскажу, как сохранить PNG своими руками на случай, если вам тоже придется это делать. Например, в академических целях.

Под катом вас ждет подробный разбор каждого байта на множестве иллюстраций.
Читать дальше →

Анализ задачи с собеседования в Google: конь и телефонные кнопки

Уровень сложностиСредний
Время на прочтение13 мин
Количество просмотров27K

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

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

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

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

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

Время на прочтение11 мин
Количество просмотров52K

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

Время на прочтение11 мин
Количество просмотров18K

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

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

Читать далее

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

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

Время на прочтение15 мин
Количество просмотров32K

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

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

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

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

Поехали!

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

Время на прочтение8 мин
Количество просмотров8.7K

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

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

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

Читать далее

Решаем загадку Джиндоша из Dishonored 2 на SQL перебором с возвратом

Уровень сложностиСредний
Время на прочтение18 мин
Количество просмотров16K


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

Сегодня мы рассмотрим решение непростой загадки Джиндоша из замечательной игры Dishonored 2 с помощью SQL.
SQL Может Многое!

Как мы французскому ПО ценности добавляли, но нас не оценили

Уровень сложностиПростой
Время на прочтение16 мин
Количество просмотров18K

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

Эта история произошла после того, как я вернулся из США в 2008 году, где благополучно потратил все свои деньги, полученные от разграбления советских заводов бандой прихатизаторов, во главе с Кахой Бендукидзе. В США я пытался запустить свой стартап, но не преуспел, но это история для мамкиных стартаперов с сайта VC. Здесь же расскажу, что было потом, поскольку это касается разработки и продвижения ПО. И бесплатно дам несколько бизнес-советов, которые за большие деньги можно получить только на курсах Тони Робинсона.

В России, как и во всем мире, в это время, кроме кризиса 2008 года, разворачивалась менее заметная, но не менее эпическая и трогательная история освобождения евреев от пленения фараоном.  Для тех, кто не читал библию, напомню, что Моисей своих евреев, отпущенных из египетского плена, водил 40 лет по пустыне, (навигаторов и Яндекс-карт тогда не было, и назад никто свалить не мог). Ведомые плевались, плакали, матюкались, ругались, но шли по пустыне за Моисеем. Тот же самый библейский сюжет разворачивался в области разработки софта, cо специалистами из французской фирмы-разработчика, той-которую-нельзя-называть, и которая проектирует боевые самолеты Рафал. В недрах этой конторы была разработана система 3D-проектирования CATIA.

Читать далее

Поделить нельзя — умножить или алгоритм быстрого деления по методу Ньютона-Рафсона

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


Все мы в школе проходили деление «столбиком» — простой алгоритм, который несложно реализовать, вот только не очень быстрый. В прошлый раз мы рассматривали, как компилятор оптимизирует деление в случаях, когда делитель известен во время компиляции, но применение его напрямую, чтоб оптимизировать деление для делителей, определямых в run-time, невозможно: вычисление констант сдвига и умножения само по себе требует деления.

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

Как я ускорила парсинг строк в serde_json на 20%

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

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

serde — основной фреймворк для сериализации и десериализации в Rust. Его используют как крейт по умолчанию во всей экосистеме. serde_json — это официальный serde-миксин для JSON, так что каждый раз, когда нужно что-то парсить, люди обращаются именно к нему. Конечно, есть и другие библиотеки, специализующиеся на парсинге JSON, например simd-json, но популярность у них, мягко говоря, удручающая. serde_json значительно популярнее: на момент написания от него зависят аж целых 26916 крейта, а от simd-json — всего 66.

Это делает serde_json хорошей мишенью (не как у Jia Tan) для оптимизаций. Велик шанс того, что многим из тысяч пользователей переход на simd-json позволил бы добиться ускорения, но, пока они этого не делают, более мелкие оптимизации — лучше, чем совсем ничего, и такие улучшения — глобальный выигрыш для экосистемы.

Читать далее

strlcpy, или как CPU противоречат здравому смыслу

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

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

«В общем случае, когда исходная строка умещается в конечный буфер, strlcpy будет обходить строку только один раз, а strlen + memcpy будут обходить её дважды».

Под этим аргументом скрывается допущение о том, что однократный обход строки выполняется быстрее. И, честно говоря, это вполне разумное допущение. Но справедливо ли оно? Об этом мы и поговорим в статье.

Читать далее

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