Алгоритмы *

Приветствую, сообщество Habr.

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

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

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

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

Статья «When FTM Discovered MUSIC: Accurate WiFi-based Ranging in the Presence of Multipath» опубликована в материалах Международной конференции IEEE по компьютерным коммуникациям, которая прошла в Торонто, Канада, с 6 по 9 июля 2020 г. (IEEE International Conference on Computer Communications, INFOCOM 2020). Идеи, изложенные в этой публикации, получили дальнейшее развитие, в частности, в статье «FSI: A FTM Calibration Method Using Wi-Fi Physical Layer Information» («FSI: метод калибровки FTM с использованием информации о физическом уровне Wi-Fi»), опубликованной во 2-й части материалов 17-й Международной конференции по беспроводным алгоритмам, системам и приложениям, которая прошла в Даляне, Китай, с 24 по 26 ноября 2022 г. (Wireless Algorithms, Systems, and Applications; WASA 2022).

Аннотация. Недавно (относительно, в 2016 году – прим. пер.) стандартизирован IEEE протокол точного измерения времени (Fine Timing Measurement, FTM), основанный на измерении дальности по времени распространения сигнала (Time-Of-flight, TOF). Большое количество публикаций посвящены определению местоположения Wi-Fi-устройств в помещениях. С другой стороны доступных соответствующих решений по состоянию на данный момент очень мало. Поэтому появление FTM может стать поворотным моментом в преодолении разрыва между теорией и практикой. Эксперименты с первыми картами Wi-Fi, поддерживающими FTM, показывают, что в условиях прямой видимости (Line-Of-Sight, LOS), они обеспечивают точность до нескольких метров, но точность в условиях вне прямой видимости (Non-Line-Of-Sight, NLOS) может быть не такой высокой. В этой статье представлен FUSIC – первый метод, который улучшает точность измерений с помощью FTM в условиях LOS до значений в условиях NLOS без необходимости внесения каких-либо изменений в стандарт.

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // зловещий хакинг чисел с плавающей запятой на уровне битов
    i  = 0x5f3759df - ( i >> 1 );               // какого чёрта?
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // первая итерация
//  y  = y * ( threehalfs - ( x2 * y * y ) );   // вторая итерация, можно удалить

    return y;
}

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

Введение

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

Описание алгоритма

Алгоритм использует матрицу размером 5xN для хранения информации о графе и вычисления кратчайших путей. Каждая строка матрицы содержит следующую информацию:

ChatGPT генерирует разнообразный и привлекательный для человека текст. Но что делает текст «хорошим»? Это субъективно и зависит от контекста. Например, если вы попросите сочинить историю, нужен творческий подход. Если вы запрашиваете информацию, то хотите, чтобы она была правдивой. А если вы просите написать код, то ожидаете, что он будет исполняемым.

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

Именно данные с фидбеком от людей позволили дообучить их языковую модель и сделать продукт таким «человечным».

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

Как обрабатывать подобные выражения с помощью кода и графического интерфейса?

Фанатам Тьюринга точно будет интересно)

ChatGPT, GPT-4 и Claude — это мощные языковые модели, которые дообучают, используя метод, который называется «обучение с подкреплением на основе отзывов людей» (Reinforcement Learning from Human Feedback, RLHF). Благодаря этому такие модели лучше отражают наши ожидания в плане их поведения, они лучше соответствуют тому, как мы собираемся их использовать.

В этом материале мы рассмотрим процесс обучения модели LLaMa c использованием RLHF. Модель будет учиться отвечать на вопросы с сайта Stack Exchange.

Ряд Фибоначчи часто упоминается на собеседованиях, потому что в нем демонстрируется множество мощных методов, включая рекурсию. Он является отличным примером того, что мы называем мемоизацией(запоминанием). Понимание ряда Фибоначчи и его работы очень полезно.

Математически ряд Фибоначчи представляет собой последовательность чисел, которые следуют этому уравнению: F(n) = F(n-1) + F(n-2). Эта последовательность встречается в различных интересных контекстах, например, в природе, в раковинах, спиральных структурах и галактиках, а также в дизайне римских полов, и даже брокеры используют ряд Фибоначчи для прогнозирования акций.

В этой статье я расскажу об одном способе вычисления x mod p, для p вида (2 ** n - omega), причём omega значительно меньше 2 ** n. Напишу генератор констант на Python. Приведу пару игрушечных примеров на С++, для которых может быть выполнено исчерпывающее тестирование для всех возможных аргументов. А в качестве серьёзной проверки - вычислю 97! mod (2 ** 256 - 2 ** 32 - 977).

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

Будем пытаться писать быстрый драйвер флешки и при этом попробуем сэкономить её ресурс при перезаписях.

Эксперименты на торе

Существуют UWB радио трансиверы, которые умеют измерять точное время отправки и приема радио пакетов. Под словом "точно" подразумевается, что с дискретизацией 15ps. В качестве примера можно привести микросхему DW1000. TimeStamp(ы) очень полезная функция так как открывает дорогу для измерения расстояния между трансиверами.

Однако сам по себе чип DW1000 на аппаратном уровне не умеет вычислять TOF, которое фигурирует в формуле вычисления расстояние между трансиверами.

Вычисление TOF это чисто программная работа, которая должна осуществляться на уровне Firmware.

#Decawave