Зная основы работы операции в двоичной системе счисления, можно воспользоваться знанием того, что четные числа в двоичном коде всегда оканчиваются на 0, тогда легко можно привести несколько примеров проверки четности числа.
- Использование AND оператора.
bool isEven(int n)
{
return (!(n & 1));
}- Использование XOR оператора.
bool isEven(int n)
{
return ((n | 1) > n);
}- Использование OR оператора.
bool isEven(int n)
{
return (n ^ 1 == n + 1);
}- Функция из задания.
bool isEven(int value)
{
return value%2==0;
}Проведем дизассемблинг gcc 12.2
Проведем дизассемблинг clang 15.0.0
Как видим, для gcc в предлагаемой заданием функцией также используется оператор AND как и в первой моей реализации четности. Clang же не делает оптимизацию, и используется операция деления для функции %2. Вероятно компиляторы для языков, где эти выражения эквивалентны, будут одинаково реализовывать оба варианта. Проведем бенчмарк, подав на вход каждой функции числа от 0 до 2000000000, используем компилятор clang
The time for %2: 6.562500 seconds
The time for XOR: 4.546875 seconds
The time for OR: 4.218750 seconds
The time for AND: 4.078125 seconds
Как мы видим, худший результат выдает %2 ввиду операции деления, остальные функции показывают неплохое время, AND - лучшее Проведем бенчмарк, используя другой компилятор gcc(g++)
The time for %2: 3.843750 seconds
The time for XOR: 3.984375 seconds
The time for OR: 4.093750 seconds
The time for AND: 3.812500 seconds
Как мы видим, ввиду того, что реализация для %2 и AND одинакова, то и затраченное время примерно одинаково, также для AND опять лучшая скорость
Однако это еще не все, не стоит забывать про флаги оптимизации, для более удобного бенчмарка воспользуюсь сайтом https://quick-bench.com/
Результаты тестов функции от 0 до 2000000000 (пришлось увеличить количество подоваемых чисел дабы результат тестирования был более нагляден)
Как видим, результаты совсем другие, в зависимости от используемого уровня оптимизации мы получаем разные лучшие по скорости функции
Первая реализация кругового буфера реализована с помощью массива и указателей, в классе реализована функция для динамического расширения, однако если не использовать метод расширения, то буффер превратится в фиксированный. Если используется массив фиксированного размера, все операции с буфером выполняются за постоянное время O(1), для динамического расширения также стоит учитывать O(n) сложность переноса элементов.
https://github.com/OlegMatveevS/Task/blob/main/TaskTwo/RingBuffer.cpp
Вторая реализация выполнена на списках,
Операции вставки, не требующие обхода, имеют временную сложность O(1).
И вставка, требующая обхода, имеет временную сложность O (n).
https://github.com/OlegMatveevS/Task/blob/main/TaskTwo/RingBufferList.cpp
Реализация с помощью списков более гибка, позволяет получать доступ к любой позиции и имеет динамическое расширение. Реализация на массиве предпочтительна когда размер известен заранее.
Ввиду того, что для разных случайных значений, разные алгоритмы сортировки будут выдавать разные результаты предложить самый быстрый алгоритм невозможно.
Взятые мною бенчмарки алгоритмов из свободного доступа
Полностью неотсортированный массив:
Частично отсортированный массив (половина элементов упорядочена):
У разных алгоритмов время работы находится в экспоненциальной или логарифмической зависимости от числа элементов структуры данных (массива) N. Как мы видим, ни один из алгоритмов не является лидером во всех тестах, например в частично отсортированном массиве quick sort для небольших массивов данных показывает худший результат, однако при увеличении числа элементов разрыв сокращается, и quick sort становится лидером