Задать вопрос
  • Где могла закрасться ошибка?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    В вашем рассуждении ошибка в том, что вы не домножаете условную вероятность 2/6 на вероятность условия. Вы же полную вероятность считатете а P(A) = P(A|B)*P(B)+P(A|!B)*P(!B). У вас P(A|B) = 0, как вы заметили - если они встретились в первом туре, то во втором уже не встретятся. Но все-равно надо 2/6 домножать на P(!B) - вероятность того, что они не встретились в первом туре. А это 1-1/7 = 6/7. В итоге получается все то же 2/6*6/7=2/7.

    Но рассуждения автора проще. Можно рассмотреть все независимые элементарные исходы "где в сетке оказался второй игрок". Их 7, они равновероятны по симметрии. Дальше надо домножить на вероятность, что они начиная так встретятся (выиграют свои матчи).
    Ответ написан
    4 комментария
  • Является ли безопасным отнять от указателя 1 и итерироваться по массиву [1,N], а не [0, N-1]?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Это не безопасно. Это не UB, но оно не определено стандартом. А значит, компилятор может что-то там соптимизитровать и поломать код.
    В документации написано:

    Every value of pointer type is one of the following:
    * a pointer to an object or function (in which case the pointer is said to point to the object or function), or
    * a pointer past the end of an object, or
    * the null pointer value for that type, or
    * an invalid pointer value.


    Т.е. arr у вас, вообще-то, invalid pointer value перед циклом.

    Плюс там же написано:
    Any other use of an invalid pointer value has implementation-defined behavior.


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

    Edit: немного не то написал. Так делать "не рекомендуется", а не "небезопасно". Оно генерирует непереносимый код. Если у вас на конкретном компиляторе с конкретными ключами работает, то, в общем-то, можно использовать. Но лучше не надо.
    Ответ написан
    5 комментариев
  • Seed для CRC32?

    mayton2019
    @mayton2019
    Bigdata Engineer
    Я сразу попробую ответить на главный вопрос.

    написать хэш-таблицу без коллизий


    Написать такую таблицу можно если мы заранее знаем весь набор данных (в случае автора это
    множество ключей (K). Здесь для простоты предполагаем что ключи - это целые числа int32 (DWORD).

    Алгоритм примерно такой:
    1) Берем размер хеш-таблицы в n = size(K). Метод открытой адресации.
    2) Берем любую хеш-функцию (по области определения больше чем n
    SHA1, MD5, xxhash, mur-mur-hash)
    3) Начинаем наполнять таблицу.
    4) Как только детектирована коллизия - удаляем старую таблицу и создаем новую
    с размером например 120% от исходного n.
    5) Повторяем алгортм до тех пор пока не будут расставлены все ключи.

    Profit.

    Если мы не знаем наши данные изначально (у нас их нет и мы не знаем количество и тип данных)
    то мы не можем гарантировать отсустствие коллизий хотя-бы потому что у нас
    нету такой хеш функции которая бы гарантировала отсутствие коллизий на вариативном
    типе данных
    .

    Изучать хеширование на базе целых чисел - вобщем-то не интересно. Более общий случай - это
    строки (String) и я-бы делал эксперименты со строками и с реальными данными (мобильные
    телефоны емейлы налоговые номера и прочее). Целые числа - это .... слишком синтетические
    тесты и их результаты потом никуда натянуть нельзя.

    UPD: Алгоритм в таком виде не работает. По крайней мере от коллизий мы не избавились.
    Не голосуйте здесь пока.
    Ответ написан
  • Почему T * может работать ощутимо быстрее (~ на 25-30%) в качестве хранилища данных, чем std::byte *?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Надо смотреть, что там компилятор нагенерировал.

    Создайте 2 функции, которые отличаются только вот в этих вот местах.
    Вставьте код в https://godbolt.org/

    Смотрите ассемблерный код для двух функций.

    Может, срабатывает strict aliasing. Видя тип T сомпилятор понимает, что эта переменная не может быть изменена какими-то другими std::byte в соседнем коде и может, например, пропустить загрузку-выгрузку данных в регистр из памяти.

    Может вообще что-то другое.

    Единственный вариант разобраться - это смотреть на ассемблерный код функций, которые вы и сравниваете. Не каких-то кусков, оттуда надерганных, а функций целиком.
    Ответ написан
    Комментировать
  • Является ли такой способ выделения массива объектов на хипе идиоматичным?

    @res2001
    Developer, ex-admin
    Можно использовать std::malloc вместо new.
    Если класс полиморфный, то можно предварительно вычислять max из размеров всех детей и использовать это значение для выделения массива. Список детей должен быть заранее известен.
    Ответ написан
    1 комментарий
  • Является ли одинаковой скорость 2-х фрагментов кода (доступ к элементу массива по индексу)?

    gbg
    @gbg Куратор тега C++
    Любые ответы на любые вопросы
    Из общих соображений - да, умножение нужно и там и там. Однако! Представленный код является шаблоном, следовательно, будет инлайнится по месту. Следовательно - нужно смотреть конкретный код, который вызывает этот метод - может оказаться так, что компилятор сможет выкинуть умножение совсем - например, если обращение происходит в цикле - можно ведь шагать сразу на размер инта.

    В любом случае, такой уровень экономии на спичках имеет реальную ценность только после того, как все остальные способы оптимизации программы уже выполнены, потому что это недалеко от реализации на ассемблере и интринсинках.
    Ответ написан
    1 комментарий
  • Является ли хорошей практикой ввод приватного ключа через терминал на старте приложения(сервера), а не через файл?

    saboteur_kiev
    @saboteur_kiev Куратор тега Информационная безопасность
    software engineer
    Нет.

    Если ключ физически будет на флешке, то в момент запуска все равно нужно его вставить в сервер и он будет на файловой системе. А если отключить флешку, а приложение нужно срочно перестартовать - у тебя это не получится сделать удаленно.

    Если у тебя есть опасения по поводу приватного ключа, сгенерирую ключ с passphrase, оно для этого и придумано
    Ответ написан
    3 комментария
  • Почему Clang (с -O3) не векторизует данный цикл?

    mayton2019
    @mayton2019
    Bigdata Engineer
    В первом варианте был массив четверок int или массив 128 битных элементов.
    Во втором случае - два независимых массивка 64х битных элементов которые в памяти
    расположены достаточно далеко и для них скорее всего не нашлось такой векторной
    команды которая-бы адресовалась к паре 64 + 64.
    Ответ написан
    9 комментариев
  • Какие компиляторы "принято" использовать в клиентских приложениях для разных платформ (Windows, MacOS etc)?

    Кажется, что всё-таки чаще Clang/LLVM, тк он под капотом умеет компилировать под MSVC ABI, если компилируешь под винду, и GNU ABI, когда компилируешь под Linux.
    Ответ написан
    Комментировать
  • Интеграция C++ в Electron'е?

    C++ умеет компилироваться в wasm, а wasm умеет работать с канвасом через webgl.

    Но, ИМХО, если идти в эту сторону, то использование какого-нибудь tauri+Rust выглядит разумнее, чем Electron + C++
    Ответ написан
    1 комментарий
  • Proof of work как защита от разного вида спама?

    У подхода минусов возможно и нет, потому что PoW изначально как защита от спама и задумывался, а вот с реализацией могут быть проблемы, например антивирусы могут ругаться, принимая за майнер, ОС видя 100% загрузку процесса может начать прижимать ресурсы для приложения, для пользователя 10-15 секунд это очень большое время, а для атакующего 10-15 секунд CPU может быть вполне приемлемое время, смотря какие прибыли он из этого извлекает.
    Ответ написан
    3 комментария
  • Можно ли объявить переменную-член класса с помощью метапрограммирования?

    @MarkusD Куратор тега C++
    все время мелю чепуху :)
    Соберем немного конкретики из комментариев.

    Отсюда:
    Только хотелось бы без специализации, чтобы код не дублировать

    Единственным дублированием кода тут будет только заголовок частичной специализации шаблона. В силах писателя определить общий между специализациями код и вынести его в родительский для всех специализаций класс.
    А с подобным дублированием справляется шаблон std::enable_if[?]. Часто его используют для выбора поведения шаблона исходя из черт аргумента шаблона.

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

    Отсюда:
    соответственно во всех методах, где этот член используется можно будет проверку if constexpr (someCondition)

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

    За чистотой кода нужно следить. Подобные вещи, как вот такие блоки if constexpr, нужно убирать в функции. А где эти функции лучше расположить? Верно - прямо там, где для их работы определены данные. Поэтому на самом деле if constexpr не нужен. Нужно определить набор функций с поведением там где оно возможно. А где нет - определить заглушки чтобы клиентский, относительно вариативного поведения, код не нуждался в проверках и мог просто обращаться к вариативному поведению так, как будто оно не вариативно и есть всегда.
    Опять же, тут хорошо подходит пример с DebugName[?], в котором такие заглушки реализованы.
    Ответ написан
    1 комментарий
  • Можно ли объявить переменную-член класса с помощью метапрограммирования?

    @res2001
    Developer, ex-admin
    Условия можно проверять с помощью enable_if.
    Переменную, видимо, придется запихнуть во вложенную шаблонную структуру, где и использовать enable_if.
    Я сам не силен в метапрограммировании, но можете начать по этой ссылке копать, там и примеров много.
    Ответ написан
    Комментировать
  • Assignment operator VS Destructor + Placement new, где аргумент placement new - prvalue?

    @dolusMalus
    С++ programmer from gamedev
    Мне кажется, что данный вопрос стоит рассмотреть с точки зрения нескольких позиций:
    1. Безопасность относительно исключений. Какой уровень гарантий должен предоставлять данный метод?
    2. Производительность. Критично ли получить максимально эффективный код или на данном этапе этим можно пожертвовать?
    3. Оценить проектное решение в свете известных и проверенных практик, например, принципы SOLID


    Для начала определяемся используются ли вообще исключения в Вашем проекте и если нет, то можно переходить сразу к вопросу о производительности. В противном случае, рассмотрим каждый случай:
    int32_t index = sizeof(T) * head;
            (reinterpret_cast<T *>(&buffer[index]))->~T();
            new (&buffer[index]) T(std::forward<Args>(args)...);
            head = (head + 1) % maxSize;

    данный вариант не предоставляет даже базовых гарантий (basic exception guarantee), т.к. если конструктор сгенерирует исключение, то мы уже закончили время жизни объекта вызвав деструктор, но не изменятся size и head; а значит мы пришли в невалидное состояние.

    int32_t index = sizeof(T) * head;
            (reinterpret_cast<T *>(&buffer[index]))->~T();
            new (&buffer[index]) T(std::forward<Args>(args)...);
            head = (head + 1) % maxSize;

    Можем сделать развилку по noexcept для конструктора с помощью SFINAE или if constexpr и в случае, если конструктор является noexcept; то оставить данный код. В противном случае придется уже действовать в зависимости от необходимого уровня гарантий, однако решения будут достаточно громоздкие: в добавок к развилке надо будет ловить исключение, пробрасывать его дальше, при этом восстанавливать объект или уменьшать счетчики и т.п. Более того можно вообще не обеспечить сильную гарантию при определенных условиях. Как видите, это уже сильно осложнило решение.
    Теперь к другому варианту:
    // Assignment operator
    //        (*(reinterpret_cast<T *>(&buffer[sizeof(T) * head]))) = T(std::forward<Args>(args)...);

    Здесь ситуация относительно лучше, т.к. проблемы могут быть только на уровне оператора присваивания, что как минимум перекладывает часть ответственности в сторону автора типа T. Однако воспользовавшись решением от Евгений Шатунов можно относительно легко получить достаточно понятный и "чистый" код на уровне сильных гарантий. Также стоит посмотреть в сторону copy and swap идиомы, как близкой к данной проблеме.
    По итогу при необходимости строгих гарантий стоит отдать предпочтение варианту с временным объектом.

    С точки зрения производительности, если нет необходимости в максимальной оптимизации, то стоит отдать предпочтение более понятному коду. Данный момент уже прекрасно освещен в ответе Евгений Шатунов, поэтому не вижу смысла повторяться. Однако формально если отбросить предположения об оптимизациях, то вариант с реконструированием по месту (деструктор -> конструктор) оптимальней, т.к. гарантировано не требует выделения дополнительных ресурсов от временного объекта и только две операции + нет необходимости в относительно сложном анализе на перемешаемость/копируемость. В случае со swap, мы можем таки попасть на копирование в зависимости от перемещаемости типа T.

    И часто забываемый, но крайне важный пункт про проектирование. Здесь нарушен Single responsibility принцип, что возможно и породило этот вопрос. Т.е. у Вас метод по добавлению элемента может удалять/заменять элементы, что должно вызвать вопросы. Более того, вы решили за клиента вашего API (даже если это и Вы сами) как нужно обрабатывать исключительную ситуацию по переполнению. Потом например вы решите, что в одном месте стоит сложить старые элементы в отдельную очередь в другом залогировать или удалять не по одному, а сразу половину буффера. Все это потребует переписывания метода add, а зачем и почему? Попробуйте убрать эту часть кода заменив на выбрасывание исключения или вариант с возвращением успешности операции (менее грамотное решение, но это уже из области субъективной оценки) и посмотреть как увеличится прозрачность и простота написания клиентского кода для этого метода. Еще стоит посмотреть на сходное проектное решение в std::vector и его методе pop_back. Подумайте почему он не возвращает удаленный элемент?

    Итого, если важна производительность и не важна работа с исключениями; то разумно выбрать вариант с реконструированием; иначе обмен с временным объектом. Но не стоит забывать всегда про анализ проектного решения и правильную ли Вы проблему вообще решаете.
    Ответ написан
    2 комментария
  • Assignment operator VS Destructor + Placement new, где аргумент placement new - prvalue?

    @MarkusD Куратор тега C++
    все время мелю чепуху :)
    К современному коду предъявляется немало требований. В частности, код должен отвечать определенным критериям качества чтобы иметь шансы на добавление в основной репозиторий в качестве решения задачи.
    Среди таких критериев качества нередко бывают: соответствие общему стилю кода, соответствие общему стилю форматирования, наличие документации или самодокументируемость, а так же - элементарная понятность для читателя.

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

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

    *reinterpret_cast<T*>( &buffer[ sizeof( T ) * head ] ) = T{ std::forward<Args>( args )... };

    Да, тут присутствует Value Initialization и оператор перемещения. Однако, оптимизация этого кода сведет все к довольно короткому и как можно более быстрому коду. Поэтому не стоит беспокоиться об этом на текущем этапе. Лучше беспокоиться о понятности кода для читателя.
    Столь же понятным будет и такой код:
    auto T vicar{ std::forward<Args>( args )... };
    std::swap( *reinterpret_cast<T*>( &buffer[ sizeof( T ) * head ] ), vicar );

    Он не будет вызывать много вопросов, разве только вопрос относительно использования std::swap, но только от людей со слабой привычкой пользоваться STL.

    Однако, такой код может привести к ошибке трансляции в том случае, если T является неперемещаемым. В твоем ЦБ должны присутствовать проверки на перемещаемость, копируемость и возможность размена состояний.
    Если T можно копировать, но не перемещать, использовать стоит оператор копирования.
    И только если ни копировать, ни перемещать T нельзя, следует пользоваться деструктором и размещающим конструктором.

    Я бы рекомендовал все три действия оформить в виде перегрузок шаблона функции со SFINAE, чтобы для любого T включалась только одна конкретная перегрузка шаблона.
    Ответ написан
    6 комментариев
  • Почему в с++11 появилась 1 перегрузка push_back и метод emplace_back, ведь можно было использовать универсальную ссылку?

    kray74
    @kray74
    emplace_back не помещает переданный объект в вектор, а создаёт новый объект сразу внутри вектора. В качестве аргументов emplace_back принимает параметры конструктора создаваемого объекта.

    Перечитал еше раз вопрос и понял, что я не на то отвечаю.
    По поводу двух версий push_back Howard Hinnant (член комитета по стандартизации C++) ответил, что проще было добавить новую функцию, чем изменять существующую.
    Ответ написан
    Комментировать
  • Существует ли такой анализатор кода?

    Viktor_T2
    @Viktor_T2
    python developer
    Комментировать
  • Член класса/структуры типа uint8_t * или int8_t *, оптимизация?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Тут проблема не в том, что член класса char*, а в том, что запись идет в char*, и из-за strict aliasing правил - это может быть запись куда угодно, в том числе в &this. Кешировать пришлось бы любой член структуры, любого типа.

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

    Частично это можно решить кешированием, можно попробовать поменять типы кое где. Но делать это не стоит - это та самая преждевременная оптимизация, о которой писал Кнут. Лучше алгоритм хороший и структуры данных правильные в вашей программе выберите. А уже дальше, если профилирование покажет, что вот тут вот узкое место, то можно смотреть на ассемблерный код и думать, как убедить компилятор геренировать что-то более быстрое.
    Ответ написан
  • Можно ли обратиться к статическому полю шаблона класса без инстанцирования шаблона?

    @sergiodev
    class CircularBufferBase
    {
    public:
        static const int32_t MEMBER_TO_BE_ACCESSIBLE_OUTSIDE = 0;
    };
    
    template <typename T, int32_t maxSize>
    class CircularBuffer : public CircularBufferBase {
        ...
    }


    CircularBufferBase::MEMBER_TO_BE_ACCESSIBLE_OUTSIDE
    Ответ написан
    1 комментарий