Задать вопрос
  • Локальная или интегральная теорема Лапласа?

    Alexandroppolus
    @Alexandroppolus
    кодир
    Ты можешь посмотреть на задачу так: провели ровно 2300 испытаний, какова вероятность, что успех наступил от 600 до 2300 раз.

    Так что да, интегральная.

    Собственно, ты и сам об этом написал, непонятно тогда в чем загвоздка
    Ответ написан
    6 комментариев
  • Где могла закрасться ошибка?

    Alexandroppolus
    @Alexandroppolus
    кодир
    Если взять турнирную сетку на 2^N человек (или N раундов), то можно ещё составить рекуррентную формулу вероятности встречи P(N)

    P(1) = 1
    P(N) = 1/(2^N - 1) + (2^N - 2) /(2^N - 1) * 1/4 * P(N-1)

    2^N - это 2 в степени N

    здесь первое слагаемое для случая, когда второй игрок в самом ближайшем раунде встречается с первым
    второе слагаемое - все остальные случаи, для которых с вероятностью 1/4 оба игрока выиграют раунд и далее встретятся с вероятностью P(N-1)

    теперь по индукции можно доказать, что P(N) = 1/2^(N-1)
    Ответ написан
    Комментировать
  • Где могла закрасться ошибка?

    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
    Комментировать