На Хабре можно найти немало статей, посвящённых оптимизациям поиска кратчайшего пути на графе. Я расскажу ещё про еще один подход. Речь пойдёт о распараллеливании алгоритма A* и исполнении его на двух потоках, а также о сложностях, с которыми я столкнулся при реализации, и их преодолении.
User
C++. Унарный минус и беззнаковый тип
Привет, Хабр! Меня зовут Владимир, я работаю в VK Карты. Хочу рассказать про случай, который недавно произошёл у нас в подразделении. Он кажется достаточно типичным и может быть интересен другим программистам.
Нам, программистам на C++, не привыкать, что даже самый безобидный код может таить в себе сюрпризы. Рассмотрим пример:
uint32_t width = 7;
int32_t signed_offset = -width;
Он полон сюрпризов! Каких? Короткий ответ: значение signed_offset
не определено стандартом и зависит от реализации. Но это далеко не все неожиданности в этом коде. Статья как раз о них.
RVO и NRVO в C++17
Предположим, что в программе на C++ вы возвращаете из функции локальную переменную. Что происходит при вызове оператора return
: копирование, перемещение или ни то, ни другое? От этого зависит длительность вызова функции и эффективность наших программ. Я постарался разобраться с этим вопросом и дам рекомендации по написанию функций так, чтобы повысить шансы на применение этой оптимизации компиляторами. Ну, а сокращения в названии статьи — это Return Value Optimization (RVO) и Named Return Value Optimization (NRVO).
Под капотом сортировок в STL
Стандарт С++ почти никогда не указывает, как именно должен быть реализован тот или иной std алгоритм. Дается только описание того, что на входе, что на выходе и асимптотические ограничения по времени работы и памяти. В статье я постарался прикинуть, какие математические алгоритмы и структуры данных имели ввиду авторы стандарта, указывая ограничения для той или иной сортировки и для некоторых других алгоритмов. А так же как эти алгоритмы реализованы на практике.
При написании статьи я использовал стандарт C++17. В качестве реализаций рассматривал GCC 10.1.0 (май 2020) и LLVM/Clang 10.0.0 (март 2020). В каждой и них есть своя реализация STL, а значит и std алгоритмов.
Профилирование Android-приложений на потребление аккумулятора
Думаю, что у каждого пользователя Android рано или поздно возникает необходимость понять, какое приложение за ночь съело всю батарею притом, что телефон лежал с погашенным экраном. Участь найденного виновника не завидна: чаще всего его просто удаляют. Итак, что же сделать, чтобы наши приложения использовали аккумулятор минимально? В статье я постараюсь дать ответ на этот вопрос и рассказать о подходах к уменьшению потребления аккумулятора, которые мне доводилось использовать.