Отклик на вакансию Junior programmer (Python, C++)

Автор: Антон Доспехов (Anton Dospekhov)

На языке Python или С/С++, написать алгоритм (функцию) определения четности целого числа, который будет аналогичен нижеприведенному по функциональности, но отличен по своей сути. Объяснить плюсы и минусы обеих реализаций.

Python example:

def isEven(value): return value % 2 == 0

C/C++ example:

bool isEven(int value){return value % 2 == 0;}

Решение:

Имеем определение четности целого числа (с Википедии):

Чётное число — целое число, которое делится на 2 без остатка: …, −4, −2, 0, 2, 4, 6, 8, …

Нечётное число — целое число, которое не делится на 2 без остатка: …, −3, −1, 1, 3, 5, 7, 9, …

Используя свойство суммы (если два числа кратны n, то и их сумма тоже кратна n) можно сформировать следующее определение четности используя математичекую индукцию:

0 — чётное число
1 — нечетное число
Если n — четное число, то (n + 2) — тоже четное число.
Если n — нечетное число, то (n + 2) — тоже нечетное число.

Мы можем записать данную формулировку через рекурсию, т. е. обратным путем. Для числа n мы знаем, что для того, чтобы быть четным, (n - 2) должно быть четным, а для него четным должно быть (n - 4) и т. д. В конце концов, мы придем либо к 0, либо к 1 и воостановим цепочку обратно через индукцию.

С++ Решение:

bool isEven(int value)
{
    if (value == 0) return true;
    if (value > 1) return isEven(value - 2);
    if (value < -1) return isEven(value + 2);
    return false;
}

Заметьте, что для отрицательных чисел мы двигаемся в положительную сторону, и можем остновиться на -1.

Сравнение двух решений:

`return value % 2 == 0`	Рекурсия
Константная сложность	Линейная сложность
Не расходует лишнюю память	Может вызвать переполнение стека
Простота решения

На языках Python(2.7) и/или С++, написать минимум по 2 класса реализовывающих циклический буфер. Объяснить плюсы и минусы каждой реализации.

Решение :

Полный исходный код можно найти здесь.

Идея циклического буффера заключается в обертке статического массива так, чтобы после его конца сразу же шло его начало. Новые элементы добавляются в конец последовательности, в то время как удаляемые элементы просто вычеркиваются. Последовательность не сдвигается для компенсации образовавшего "пузыря" в памяти, а остается на месте. В процессе работы она будет постепенно "ползти" вправо и, когда достигнет края массива, телепортируется в начало.

Для первой реализации идеи я отслеживаю положение последовательности, использую голову и хвост, аналогично змее. При добавлении перемещается голова, при извлечении — хвост. Поскольку голова всегда должна быть не левее хвоста (для правильного определения размера), последовательность двигается по диапазону, вдвое большему, чем вместимость контейнера. Таким образом, конец первого и начало второго склеены вместе на их стыке. Как только последовательность пересекает стык, к диапазону приклеивается новый контейнер и удаляется старый из самого начала. В итоге всё равно остаются 2 виртуальных контейнера. При доступе к эелементам я нормализую индекс, чтобы он был в пределах границ контейнера.

// Сделать класс шаблонным для любых типов данных
template <class T, class Allocator = std::allocator<T>>
class CyclicBufferRanged
{
public:
    // Запретить создание буфера если не указана вместимость
    CyclicBufferRanged() = delete;

    // Создать буфер указанного размера. Аллокатор автоматически выделит необходимое место
    CyclicBufferRanged(size_t capacity) :
        Capacity(capacity),
        Buffer(ContainerAllocator.allocate(capacity))
    {}

    ~CyclicBufferRanged()
    {
        ContainerAllocator.deallocate(Buffer, Capacity);
        Buffer = nullptr;
    }

    // Поместить елемент в буфер вернуть true. Если буфер заполнен, вернуть false
    bool Insert(T element)
    {
        if (GetSize() >= Capacity) return false;
        // Нормализовать индекс головы буфера и переместить в него элемент
        Buffer[Head % Capacity] = std::move(element);
        // Передвинуть голову буфера
        ++Head;
        return true;
    }

    // Попытаться извлечь эелемент из буффера и вернуть его. Если буфер пуст, вернуть std::nullopt
    std::optional<T> Extract()
    {
        if (GetSize()) // Буфер не пустой?
        {
            T element = std::move(Buffer[Tail]);// Извлечь элемент из буфера
            ++Tail; // Передвинуть хвост
            // Сдвинуть голову и хвост на один буфер вниз
            if (Tail >= Capacity)
            {
                Tail -= Capacity;
                Head -= Capacity;
            }
            return std::make_optional(element);
        }
        else
        {
            return std::nullopt;
        }
    }

    // Количество хранимых элементов равно разнице индексов головы и хвоста
    size_t GetSize() { return Head - Tail; }
    size_t GetCapacity() { return Capacity; }

private:
    Allocator ContainerAllocator{};
    T* Buffer{ nullptr };
    size_t Capacity;
    size_t Head{ 0 }, Tail{ 0 };
};

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

// Сделать класс шаблонным для любых типов данных
template <class T, class Allocator = std::allocator<T>>
class CyclicBufferSized
{
public:
    // Запретить создание буфера если не указана вместимость
    CyclicBufferSized() = delete;

    // Создать буфер указанного размера. Аллокатор автоматически выделит необходимое место
    CyclicBufferSized(size_t capacity) :
        Capacity(capacity),
        Buffer(ContainerAllocator.allocate(capacity))
    {}

    ~CyclicBufferSized()
    {
        ContainerAllocator.deallocate(Buffer, Capacity);
        Buffer = nullptr;
    }

    // Поместить елемент в буфер вернуть true. Если буфер заполнен, вернуть false
    bool Insert(T element)
    {
        if (Size >= Capacity) return false;
        // Найти конец очереди и поместить в него эелемент
        Buffer[(Start + Size) % Capacity] = std::move(element);
        ++Size;
        return true;
    }

    // Попытаться извлечь эелемент из буффера и вернуть его. Если буфер пуст, вернуть std::nullopt
    std::optional<T> Extract()
    {
        if (GetSize())
        {
            T element = std::move(Buffer[Start]); // Извлечь елемент из буффера
            --Size; // Уменьшить размер буфера
            ++Start; // Передвинуть начало очереди
            Start %= Capacity; // Циклически сбросить начало очереди если оно достигло конца массива
            return std::make_optional(element);
        }
        else
        {
            return std::nullopt;
        }
    }

    // Размер просто хранится как переменная
    size_t GetSize() { return Size; }
    size_t GetCapacity() { return Capacity; }

private:

    Allocator ContainerAllocator{};
    T* Buffer{ nullptr };
    size_t Capacity;
    size_t Start{ 0 }, Size{ 0 };
};

Сравнение двух реализаций:

Через диапазон	Через размер
Не хранит размер, вычисляет динамически	Хранит размер
Требует валидации левой и правой границ	Требует валидации размера
Может быть переписан в виде адаптера только для контейнеров, поддерживающиех итераторы	Может быть переписан в виде адаптера для любых последовательных контейнеров

На языке Python или С/С++, написать функцию, которая быстрее всего (по процессорным тикам) отсортирует данный ей массив чисел. Массив может быть любого размера со случайным порядком чисел (в том числе и отсортированным). Объяснить почему вы считаете, что функция соответствует заданным критериям.

Поскольку для задачи не заданы точные условия, алгоритм сортировки должен быть максимально универсальным. Ключевые моменты:
- Неизвестно, целые ли числа, если да, то каков их диапазон. Если же числа вещественные неизвестно соответствуют ли они стандарту IEEE-754 для хранения вещественных чисел. В связи с этим мы не можем использовать сортировку подсчетом/поразрядную сортировки и им подобные, несмотря на то, что они гораздо эффективнее. Алгоритм должен быть шаблонным и применим только к абстрактным данным, поддерживающим операцию сравнения, а именно оператор меньше "<".
- Простые алгоритмы сортировки (например Сортировка вставками) будут эффективны только на небольших массивах данных, в нашей же задаче размер массива неизвестен.
- Одной из самых эффективных алгоритмов сортировки считается быстрая сортировка, однако она имеет несколько недостатков, такие как:
  - Рост сложности с O(n log(n)) до O(n^2) при порядке чисел, близкому к обратному
  - Тенденция к нерациональному использованию памяти, т. к. алгоритм рекурсивный.
Учитывая все перечисленные факторы, можно сделать вывод, что самым эффективным (по времени) решением будет алгоритм, совмещающий в себе принцип быстрой сортировки, но с оптимизациями, взятыми из других алгоритмов. Назовем этот алгоритм гибридной сортировкой.

Полный код можно найти здесь.

Сперва реализуем алгоритм быстрой сортировки. Принцип её простой: избрать разделительный элемент, после чего разделить исходный массив так, чтобы элементы меньше разделителя были до него, а больше — после. Затем рекурсивно отсортировать полученные путём разделения разделителем участки:
```
template<class RandomAccessIterator>
void quickSort(RandomAccessIterator begin, RandomAccessIterator end)
{
    
    if (begin >= end) return; // Крайний случай для пустого/некорректного диапазона
    RandomAccessIterator pivot = quickSortPartition(begin, end);
    quickSort(begin, pivot);
    quickSort(pivot + 1, end);
}
```
В качестве разделителя мы берем последний элемент и пытаемся определить его будущую позицию. Пробегая по массиву, мы смещаем все элементы меньше разделителя влево и сдвигаем его предполагаемую позицию. После, мы помещаем разделитель на его законное место и возвращаем его.
```
template<class RandomAccessIterator>
RandomAccessIterator quickSortPartition(RandomAccessIterator begin, RandomAccessIterator end)
{
    // Выбрать разделителем последний элемент
    RandomAccessIterator pivot = begin + std::distance(begin, end) - 1;
    // Предполагаемое место разделителя изначально в начале массива
    RandomAccessIterator futurePivot = begin;
    for (RandomAccessIterator i = begin; i != end; ++i)
    {
        if (*i < *pivot)
        {
            // Найден элемент меньше разделителя, сместить его влево, а разделитель — вправо
            std::swap(*i, *futurePivot);
            ++futurePivot;
        }
    }
    // Поставить значение разделителя на его место
    std::swap(*pivot, *futurePivot);
    return futurePivot;
}
```
Теперь попробуем оптимизировать решение. Небольшие интервалы массива лучше сортировать простым алгоритмом сортировки, пусть даже и с большей сложностью. Отсутствие лишних операций с пямятью и локальность данных играют в этом решающую роль. Реализуем алгоритм сортировки вставками. Суть его простая - взять элемент из неотсортированного участка массива и постепенно смещать его на его законное место вниз. Продолжать пока все эелементы не встануть на свои места:
```
template<class RandomAccessIterator>
void insertionSort(RandomAccessIterator begin, RandomAccessIterator end)
{
    // Не рассматривать массивы в которых менее 2 элементов
    if (begin == end || (begin + 1) == end) return;
    for (RandomAccessIterator next = begin + 1; next != end; ++next)
    {
        RandomAccessIterator drop = next; // Элемент который мы будем опускать
        // Опускаем либо до начала, либо до первого эелемента больше него
        while (drop != begin && (*drop < *(drop - 1)))
        {
            std::swap(*drop, *(drop - 1));
            --drop;
        }
    }
    return;
}
```
Теперь соберем гибридный алгоритм. Небольшие подмассивы будем сортировать вставками, остальные — быстрой. В первую очередь будем сортировать меньшие участи, чтобы сократить дерево вызовов:
```
template<class RandomAccessIterator>
void hybridSort(RandomAccessIterator begin, RandomAccessIterator end)
{
    if (begin >= end) return;
    // Это порог размера массива, ниже которого мы сортируем только вставками
    constexpr size_t recursionThreshold = 128;
    if (std::distance(begin, end) >= recursionThreshold) // Быстрая сортировка
    {
        RandomAccessIterator pivot = quickSortPartition(begin, end);
        // Сначала выбираем меньший подмассив, затем больший
        if (std::distance(begin, pivot) < std::distance(pivot, end))
        {
            hybridSort(begin, pivot);
            hybridSort(pivot + 1, end);
        }
        else
        {
            hybridSort(pivot + 1, end);
            hybridSort(begin, pivot);
        }
    }
    else // Сортировка вставками
    {
        insertionSort(begin, end);
    }
}
```
Следует отметить, что порог рекурсии подбирается экспериментально. Полагаю, что оптимальное значение будет зависеть от входных данных и от конфигурации железа.

Теперь протестируем призводительность между алгоритмами, а также с библиотечной функцией std::sort:
```
// Фунция замера времени выполнения
template<class RandomAccessIterator>
std::chrono::microseconds Benchmark(
    RandomAccessIterator begin,
    RandomAccessIterator end,
    void (*sortFunction)(RandomAccessIterator begin, RandomAccessIterator end)
)
{
    auto start = std::chrono::high_resolution_clock::now();
    sortFunction(begin, end);
    auto finish = std::chrono::high_resolution_clock::now();
    auto elapsedTime = std::chrono::duration_cast<std::chrono::microseconds>(finish - start);
    return elapsedTime;
}

int main()
{
    std::mt19937 rng;
    std::uniform_int_distribution dist;

    // Длина массива
    static constexpr size_t vectorLength = 100000;

    // Массив заполняется случайными числами, все алгоритмы работают на одном и том же наборе
    std::vector<int> vInsertion(vectorLength);
    std::generate(vInsertion.begin(), vInsertion.end(), [&]() { return static_cast<int>(dist(rng)); });
    decltype(vInsertion) vQuick(vInsertion);
    decltype(vInsertion) vStdSort(vInsertion);
    decltype(vInsertion) vHybrid(vInsertion);

    // Замер времени выполнения и вывод информации
    std::cout << "Sorting " << vectorLength << " elements of type " << typeid(decltype(vInsertion[0])).name() << "." << std::endl;
    std::cout << "Insertion sort took " << Benchmark(vInsertion.begin(), vInsertion.end(), insertionSort).count() << " mcs." << std::endl;
    std::cout << "Quick sort took " << Benchmark(vQuick.begin(), vQuick.end(), quickSort).count() << " mcs." << std::endl;
    std::cout << "std::sort took " << Benchmark(vStdSort.begin(), vStdSort.end(), std::sort).count() << " mcs." << std::endl;
    std::cout << "Hybrid sort took " << Benchmark(vHybrid.begin(), vHybrid.end(), hybridSort).count() << " mcs." << std::endl;

    // Проверка, что все алгоритмы произвели идентичный результат
    if (!std::equal(vInsertion.begin(), vInsertion.end(), vQuick.begin())) std::cout << "Inconsistent results discovered." << std::endl;
    if (!std::equal(vInsertion.begin(), vInsertion.end(), vStdSort.begin())) std::cout << "Inconsistent results discovered." << std::endl;
    if (!std::equal(vInsertion.begin(), vInsertion.end(), vHybrid.begin())) std::cout << "Inconsistent results discovered." << std::endl;

    return 0;
}
```
Пример вывода:
```
Sorting 100000 elements of type int.
Insertion sort took 1333130 mcs.
Quick sort took 6083 mcs.
std::sort took 6230 mcs.
Hybrid sort took 5122 mcs.
```
Как можно заметить наш гибридный алгоритм сортировки работает гораздо быстрее быстрой сортировки, а также библиотечной. Порог в 128 элементов был найден подбором. В худшем случае, производительность будет стремиться к результату быстрой сортировки при низком пороге, и к результату сортировки вставками при высоком. Также алгоритм был протестирован на других типах данных, таких как float и double.

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

TonyDecvA180XN/Отклик.md

Select an option

No results found