Алгоритмы *

Привет, Хабр! Эта статья для тех, кто хочет понять, когда стоит использовать sync.Map, а когда достаточно обычной map с мьютексом.

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

Внутреннее устройство sync.Map

sync.Map — это потокобезопасная реализация мапы в Go, оптимизированная для определенных сценариев использования.

Основная структура sync.Map выглядит примерно так:

type Map struct {
    mu Mutex
    read atomic.Value // readOnly
    dirty map[interface{}]*entry
    misses int
}

type readOnly struct {
    m       map[interface{}]*entry
    amended bool
}

type entry struct {
    p unsafe.Pointer // *interface{}
}

Здесь мы видим несколько ключевых полей:

Продолжаем знакомство с моделью числа и ее свойствами, а конкретно, с симметриями на разном уровне представления модели: областей строк, отдельных строк, элементов одной строки и элементов разных строк. Для читателей, ознакомившимися с моими предыдущими статьей 1(О разложении модели числа), статьей 2 (О симметриях...) и др. предлагается продолжить знакомство с проблемой моделирования и исследования чисел. Объект - натуральный ряд чисел (НРЧ) настолько богат известными и совершенно новыми свойствами, что само их перечисление потребовало бы много места и времени.

Рассмотрение же конкретного свойства в деталях ограничивает автора с одной стороны располагаемыми знаниями, а с другой - ограниченным объемом публикации. Тем не менее, есть желание показать читателям развернутую картину проявлений такого свойства НРЧ, как симметрия в поведении элементов этого замечательного объекта.

Например, обращал ли кто-нибудь внимание на последовательности квадратичных вычетов (КВВ) элементов НРЧ по разным модулям, когда модель рассматриваем как фрагмент НРЧ или конечное числовое кольцо вычетов по модулю N. Эти квадраты следуют парами R_о, R₁ и получают вид (21 пара) для N = 1961. Пары КВК 484 = 22²;
529 =23² и 625 = 25²; 676 =26² образованы смежными числами, для N = 1961 они окаймляют в 4-м слое средний вычет r_cсс = 0; и для N = 2501 в 5-м слое средний вычет r_cсс = 0.

Почему во втором случае N = 2501 квадраты следуют вначале с флексиями 0, затем с 1²,
4= 2², 3², 4² ? Эти квадраты лежат в строках за пределами тривиальной области ТКВК и среди них нет кратных d_б.

В табличках приведен порядок следования КВВ = КВК полных квадратов, объединенных в пары (верх\низ), всего 42 квадрата (для N = 1961) и 48 квадратов (для N = 2501). Каждый квадрат получен в некоторой точке х_о и реализует решающий интервал (РИ), обеспечивающий получение решения задачи факторизации большого числа (ЗФБЧ) N, т.е. для вычисления делителей N. На основании закона распределения делителей можно записать соотношение d_i = х_о ±√КВК и при необходимости воспользоваться алгоритмом Евклида НОД.

Привет, Хабр! Я Андрей Соколов, инженер-программист в группе разработки математических библиотек. Месяц назад моя коллега Валерия запустила цикл статей про матричные расширения, ускоряющие операции над матрицами. Вы уже смогли узнать, что они делают и какие существуют, какие из них разрабатываются для открытой архитектуры RISC-V.

В заключительной статье цикла разберем пример использования матричного расширения T-Head под RISC-V для реализации алгоритма матричного умножения. Сначала кратко рассмотрим наивную скалярную реализацию и блочный вариант алгоритма. Затем реализуем аналогичный вариант с использованием матричного расширения — как для квадратных матриц, так и матриц произвольного размера. Второй случай интересен тем, что возникает необходимость обработки так называемых «хвостов» — блоков неправильной конфигурации. В заключение немного расскажу, какие идеи можно использовать для дальнейшей оптимизации матричного умножения, и поделюсь полезными ссылками.

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

Всем привет! Меня зовут Николай Лысенко, я занимаюсь рекомендательными системами в Яндекс Маркете. Сегодня хочу затронуть интересную тему: что делать, если в графе вычислений (aka нейронная сеть) возникает дискретное место, через которое не проходит градиент. Как многие знают, для решения этой проблемы есть такие методы, как REINFORCE и софтмакс Гумбеля (Gumbel-Softmax trick). О последнем и пойдёт речь.

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

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

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

Однажды мы решили, что грамотных инженеров эффективнее всего растить самим. Так 3 года назад родился Route 256 — курсы Ozon для разработчиков и тестировщиков уровней junior и middle.

Во время курса ведущие специалисты Ozon погружают в индустрию e-com, знакомят с актуальным стеком и бизнес-задачами. Самые успешные выпускники получают оффер в команду Ozon.

В статье рассказали, почему для отбора мы используем алгоритмы, и показали разбор задач с контеста.  

Уже много лет, начиная с 1966 года, во всем мире 20 июля отмечают Международный день шахмат. В честь недавно прошедшего праздника мы решили написать статью, в которой поговорим о шахматных задачах из курсов "Поколение Python".

Так получилось, что шахматные задачи являются одной из главных визиток наших курсов. Мы любим эти задачи потому, что они учат строить алгоритмы, находить закономерности, а также позволяют отточить работу с условными (if-else) и логическими (and и or) операторами.

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

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

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

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

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

Привет, Хабр! Меня зовут Дмитрий Крюков, я — научный сотрудник лаборатории «Сильный ИИ в медицине» в AIRI. Недавно мы опубликовали статью на стыке биологии старения и машинного обучения, в которой раскритиковали использование так называемых эпигенетических часов старения для измерения омоложения клеток в процессе клеточного репрограммирования. Тема часов старения уже поднималась на Хабре (раз, два, три) — настолько она стала популярной в современной биологии с приходом в неё методов машинного обучения. А уж тема репрограммирования клеток, которую Юрий Дейгин (кстати, рекомендую его блог на Хабре) с легкой руки назвал «эпиоткатом», так вообще превратилась в гигантское направление клеточной биологии и инженерии тканей. 

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

Привет, друзья!

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

• Первая часть
• Вторая часть
• Четвертая часть
• Пятая часть

Сегодня мы будем говорить о таких структурах данных, как деревья. В этой статье мы рассмотрим двоичное дерево поиска, АВЛ-дерево и красно-черное дерево.

Код, представленный в этой и других статьях серии, можно найти в этом репозитории.

Интересно? Тогда прошу под кат.

Лето — прекрасное время для того, чтобы неспешно заниматься тем, что нам нравится. А что нам нравится? Конечно же, ИИ!

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

1. Coursera “Deep Learning Specialization” (Специализация глубокое обучение)

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

2. Coursera “ChatGPT Prompt Engineering for Developers” (Промт инжиниринг ChatGPT для разработчиков)

Маленький урок, в рамках которого вы научитесь быстро и эффективно создавать новые приложения с использованием LLM. Курс охватывает работу LLM, практики инженерии запросов и использование API LLM для различных задач. Знаете, кто ведет этот курс? Лиза Фулфорд (OpenAI) и Эндрю Нг (DeepLearningAI) —неплохой каст, да?

3. edX “HarvardX: Data Science: Machine Learning” (ГарвардХ: Наука о данных: Машинное обучение)

Крутой бесплатный курс от Гарвардского университета по машинному обучению — надо! Здесь вы пройдетесь по основам машинного обучения; узнаете, как выполнять кросс-валидацию; изучите несколько популярных алгоритмов машинного обучения и др.

4. Harvard University “Machine Learning and AI with Python” (Машинное обучение и ИИ на Python)

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

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

Предлагаю сразу использовать его на примере задачи «Majority Element» с leetcode.

Условие здесь: https://leetcode.com/problems/most-frequent-even-element/description/

Кстати, у меня есть телеграм-канал, где пишу подходы к решениям всяких задачек с LeetCode, там больше разборов конкретных задач, чем здесь, потому что не всегда нужна статья. В общем, если интересно - жду здесь - t.me/crushiteasy :)

Возвращаемся к Муру!

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

Не супер очевидно, но это число занимает больше половины элементов массива, т.е.

Уже много лет IT компании проводят алгоритмические собеседования при найме технических специалистов. Подход введенный в FAANG плавно перетек в большинство крупных компаний. Яндекс, Авито, Т-Банк и многие другие хотят проверить алгоритмические знания кандидатов. Но на практике такое собеседование оказывается бесполезным созвоном на 45 минут, который ничего не говорит о кандидате.

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

Но очень мало можно встретить критики и конкретного разбора проблем алгоритмических собеседований и их внедрения в воронку найма. Эта статья будет первой в цикле “в чем проблема алгоритмов”.

Кто-то может сказать: “О, человека не приняли в компанию из-за алгоритмов и он решил обидеться и сказать всем, что алгоритмы бесполезны”. Отчасти это так и было, но я решил не останавливаться на своем чувстве несправедливости и пошел дальше: адаптировал алгоритмы в компании, прошел все этапы в Google и даже решал алгоритмы на протяжении года.

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

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

Сейчас я просто хочу рассказать свою историю.

Хабр, жаркий июльский привет тебе от отдела компьютерной томографии компании Smart Engines! Раньше мы тебе рассказывали о задаче поиска положения смещенной и наклоненной оси вращения объекта в компьютерной томографии. Мы обещали рассказать о нами разработанном методе решения этой задачи, и вот, мы здесь! Мы вернулись к тебе с опубликованной статьей о нашем методе и с полученным патентом РФ!

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

Всем салют! Давайте решим задачу "Middle of the Linked List"

Дан указатель head на начало односвязного списка, нужно вернуть средний узел списка.

Если средних узлов два, нужно вернуть второй средний узел.

Когда реальность не соответствует ожиданиям — это всегда неприятно. Особенно неприятно, если за ожидаемую реальность заплачены деньги: покупаешь билет одной авиакомпании, но по какой-то причине тебя сажают в самолет совсем другой авиакомпании. Затем делаешь пересадку, а тебя там сажают в самолет какой-то непонятной третьей авиакомпании. Что происходит? Ведь на руках билет авиакомпании, который приобретен как раз потому, что знаешь, чего от нее ожидать, но летишь все равно самолетами совсем других авиакомпаний. Вроде бы покупал билет у крупной и хорошо себя зарекомендовавшей авиакомпании, а уже на борту выясняется, что у этой авиакомпании есть региональные дочерние компании и филиалы, которые далеко не так хороши. Первое знакомство с код-шеринговыми рейсами может оказаться очень неприятным.

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

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

Если вы никогда не пробовали смотреть как код на C++ разворачивается компилятором в код Assembly – вас ждёт много сюрпризов, причём, не нужно смотреть какой-то замудренный исходный код полный templates или других сложных конструкций: рассмотрите следущий snippet:

Как всегда, сначала немного базовой теории для понимания того, с чем мы имеем дело. 

Queue - однонаправленная очередь, представляет собой структуру данных, которая строится по принципу FIFO (first-in-first-out). Другими словами, чем раньше элемент был добавлен в коллекцию, тем раньше он оттуда будет удален. 

Выжимка по методам:

Всех приветствую! Меня зовут Александр Исаков, я аналитик-разработчик в Яндекс Лавке. Занимаюсь прогнозированием с применением методов машинного обучения, чтобы помочь Лавке вовремя подготовиться к пикам спроса. Мой доклад про то, как мы прогнозируем множество параметров для расчёта необходимого числа курьеров, чтобы у нас была возможность довезти все заказы вовремя.