Алгоритмы *

За последние две недели я занимался различными задачами на Leetcode. И сегодня я наткнулся на интересную задачу: Сумма последовательного подмассива - решением которой хотел бы с вами поделиться.

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

• Первая часть

В этой статье мы заложим основы нашего проекта и реализуем простую FFNN (feedforward neural network — нейронная сеть прямого распространения), которая впоследствии станет мозгом. Мы также рассмотрим множество тонкостей и идиом, которые встречаются в коде Rust, включая тесты.

Готовы? Тогда поехали.

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

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

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

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

От читателя поста ожидается, что он на базовом уровне понимает Rust, обычные структуры данных, а также концептуально представляет, как выделяется память (в стеке и куче).

Дополнение (14.05.2024): Я учёл поступившую обратную связь и подчеркнул, какие идеи объективно плохи, прояснил некоторые отступления и удалил идею о imbl.

Чтобы было проще прослеживать этапы реализации и исследовать код, отсылаю вас к репозиторию, сопровождающему этот пост.

TikTok знают все. ByteDance - тоже, ведь эта компания сделала TikTok. Но мало кто знает, что первый выстреливший продукт ByteDance - отнюдь не приложение с вирусными клипами, а нейроагрегатор новостей Toutiao. Именно в недрах Toutiao возник TikTok и его знаменитый алгоритм, за право над которым китайская компания сейчас воюет с американскими регуляторами.

Как только закон о запрете Тиктока в США вступил в силу, сразу начался цирк с конями. Сначала глава ByteDance выступил с обращением, где призвал американцев “встать на защиту свободы слова”, а еще заявил, что “компания не смирится и будет бороться”. Потом СМИ писали, что китайцы хотят продать Тикток американцам без алгоритма (ага, больно он кому-то нужен без алгоритма...). А совсем недавно технологические медиа начали пробрасывать версию, что ByteDance разработает отдельный алгоритм для ускользающей из рук ByteDance (и КПК) американской версии Тиктока. Видимо, чтобы можно было скинуть отжатый актив без особенных мук китайской совести.

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

Многие в курсе, что Тикток - это брат-близнец китайского сервиса Douyin (прямо-таки однояйцевый). В 2016 года хитрые китайцы запустили у себя Douyin, а потом “клонировали” его для западной аудитории. Еще чуть позже ByteDance купил платформу musical.ly, объединил её с Тиктоком, влил мегатонны юаней в маркетинг, и вот мы здесь.

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

Допустим, у нас есть массив чисел с плавающей запятой, и мы хотим их суммировать. Можно наивно подумать, что их достаточно просто сложить, например, на Rust.

Однако это запросто может привести к произвольно большой накопленной погрешности. Давайте проверим:

naive_sum(&vec![1.0; 1_000_000]) = 1000000.0
naive_sum(&vec![1.0; 10_000_000]) = 10000000.0
naive_sum(&vec![1.0; 100_000_000]) = 16777216.0
naive_sum(&vec![1.0; 1_000_000_000]) = 16777216.0

Ой-ёй… Что произошло? Проблема в том .что следующее 32-битное число с плавающей запятой после 16777216 — это 16777218. Так что при вычислении 16777216 + 1, значение округляется до ближайшего числа с плавающей запятой, имеющей чётную мантиссу, то есть снова до 16777216. Мы зашли в тупик.

К счастью, есть более совершенные способы суммирования массива.

На конференции FPGA-Systems был предоставлен маршрут проектирования блоков микросхем на основе использования C++ под названием ИРИС. Докладчик - заведующий кафедрой Мехмата МГУ Эльяр Гасанов. Его группа имеет значительный опыт проектирования оптимизированных по производительности блоков, например LDPC декодера, и ведет свои истоки из сотрудничества с LSI Logic в середине 1990-х годов.

Мои мысли после просмотра презентации:

Когда проводится один статистический тест на значимость различий, всегда есть шанс (ошибка первого рода = 5%, на уровне значимости p=0.05) получить ложный положительный результат случайно. Эта ошибка означает, что мы можем ложно утверждать, что значимое различие существует, притом, что в реальности этой значимости нет.

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

Предположим, что делается 20 однотипных тестов. Вероятность того, что получится ложный положительный результат равна 1 - (1 - 0.05)^20 ≈ 64%.

Привет, хаброчеловек)
В этой статье рассмотрим алгоритмы кластеризации DBSCAN и OPTICS, посмотрим их особенности, обсудим, когда что лучше применять
Welcome под кат

Сеть ресторанов запустила акцию в честь 8 марта: забронируйте столик в праздник, приходите в одиночку или с друзьями, затем закажите праздничный ужин и получите бесплатный десерт. Рекламу  акции настроили через Facebook Ads. Менеджерам приходили уведомления об отклике.

Они звонили, но в ответ слышали удивленные и раздраженные вопросы: «А вы кто? Какой ресторан? Акция? Я никуда не нажимал, как вы мне позвонили?»  

Менеджеры объясняли, кто они и какую акцию устраивает ресторан. Люди отказывались или сразу сбрасывали трубку.

Вместо того, чтобы бронировать столики для потенциальных клиентов, менеджеры тратили время на объяснения. А заинтересованные в акции не дозвонились.  

Давайте разбираться, почему так вышло:

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

Как не допустить такой ситуации в будущем?

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

Человек через рекламу Google Ads, Яндекс.Директ, Facebook Ads или другую будет сразу попадать в бота. Тот задаст необходимые вопросы, а пользователь сможет принять решение. 

Для таких случаев мы разработали сценарий в ChatApp Конструкторе ботов. Давайте взглянем на него.

Разберемся как выигрывать в игру 5букв с вероятностью 100%.

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

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

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

Предполагается, что вы немного знакомы с Rust, остальное я постараюсь объяснить.

Эта серия состоит из нескольких статей:

1. Введение (что мы будем симулировать, как работает нейронная сеть и генетический алгоритм).
2. Реализация нейронной сети.
3. Реализация генетического алгоритма.
4. Реализация глаз, мозга и самой симуляции (в двух частях).

Интересно? Тогда поехали.

Ещё одна причуда Python, исследование её подноготной и попытка понять, почему так случается.

Недавно в сети X был популярен этот твит (см. скриншот), и я обратил внимание. Это очередной сюрприз в Python, связанный с характерными для него уникальными деталями реализации.

Привет, Хабр! Меня зовут Миша Паутов, я аспирант Сколтеха и научный сотрудник группы Доверенные и безопасные интеллектуальные системы Института AIRI. Совсем недавно вместе коллегами мы предложили новый метод  создания цифровых водяных знаков для нейронных сетей. Такие объекты, по-другому называемые ватермарками, можно использовать для определения того, что вашу нейросеть кто-то скопировал и выдаёт за свою. Здесь я расскажу, в чем состоит идея предложенного метода, а более детально о нем можно почитать в препринте статьи, принятой на международную конференцию IJCAI. 

Простые числа удивительны!

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

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

Вызов

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

Генерировать простые числа, способные генерировать ключи для алгоритма RSA

На момент написания этой статьи хорошей длиной ключей RSA считаются 2048 битов. Ключи RSA генерируются перемножением двух простых чисел, так что для получения 2048-битного ключа нам нужны два числа длиной примерно 1024 бита. Это ограничивает рамки задачи генерацией 1024-битных простых чисел. Теперь вы знаете, откуда взялось число из заголовка поста.

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

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

Неважно, новичок ли вы, отлаживающий вашу первую программу «Hello World», или опытный инженер, — у каждого из нас всегда есть возможность улучшить свои навыки. Александр Шелютин, Data Architect в KarmaHQ, расскажет о разнице между тем, как просто заставить что-то работать, и написанием действительно хорошего кода.

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

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