Визуализация алгоритмов стандартной библиотеки C++

В интернете много различных видео, в которых визуализируются алгоритмы. Как правило, такая визуализация делается под определенный алгоритм, и код отрисовки соединен с кодом самого алгоритма. Мне пришла идея отделить визуализацию алгоритма от его исполнения. Тогда можно будет визуализировать любой алгоритм. В том числе алгоритмы стандартной библиотеки С++. Я нашёл способ сделать это, и вот что у меня получилось.

Алгоритмы

std::accumulate и std::reduce

В приведенном выше видео визуализированы два алгоритма: std::reduce и std::accumulate на небольшом наборе данных. Видно, что порядок обхода std::reduce непоследовательный, как в случае std::accumulate. Хотя для выбранных данных std::accumulate отработал быстрее, для больших наборов данных std::reduce показывает себя лучше. Также std::reduce поддерживает параллельное исполнение.

std::shuffle

std::shuffle переупорядочивает элементы диапазона случайным образом, используя заданный генератор случайных чисел.

std::merge

std::merge из двух отсортированных последовательностей формирует новую отсортированную последовательность. Данный алгоритм используется, например, в сортировке слиянием.

std::rotate

Работа алгоритма std::rotate выглядит довольно любопытно. std::rotate «вращает» элементы контейнера в левом направлении так, что заданный в качестве параметра элемент становится первым.

std::lower_bound и std::upper_bound

Алгоритмы std::lower_bound и std::upper_bound являются реализацией бинарного поиска. std::lower_bound возвращает итератор на первый элемент, равный искомому. Второй — на первый элемент, больший заданному. Оба итератора можно получить с помощью алгоритма std::equal_range.

std::remove

Видео выше демонстрирует работу std::remove. Удаляемому значению соответствует самая высокая линия. Алгоритм не удаляет элементы контейнера, поскольку имеет доступ только к итераторам. Элементы, которые должны остаться после удаления, перемещаются в начало. Само удаление может быть выполнено посредством метода erase контейнера (remove-erase idiom).

std::sort и std::sort_heap

Сравнение работы std::sort и std::sort_heap (предварительно строится пирамида с помощью алгоритма std::make_heap). В продемонстрированном примере std::sort работает заметно быстрее.

std::reverse_copy

std::reverse_copy копирует элементы контейнера в другой контейнер в обратном порядке.

std::next_permutation

Алгоритм std::next_permutation для генерации перестановок использует лексиграфический порядок элементов. На приведенном видео продемонстрированы перестановки массива из 4-х элементов. Алгоритм std::next_permutation применен последовательно 23 раза.

Это все лишь несколько алгоритмов стандартной библиотеки C++. С полным списком можно ознакомиться по ссылке: https://en.cppreference.com/w/cpp/algorithm. Пишите в комментариях, визуализацию каких ещё алгоритмов вы бы хотели увидеть?

Как это работает

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

// Отправляет информацию о вызываемых методах исходного итератора обработчику. template <typename OriginalIterator> class NotifyingIterator { public:     using iterator_category = typename OriginalIterator::iterator_category;     using value_type = typename OriginalIterator::value_type;     using difference_type = typename OriginalIterator::difference_type;     using pointer = typename OriginalIterator::pointer;     using reference = typename OriginalIterator::reference;      /*         ...         здесь переопределeны методы исходного итератора         ...     */      // Доступ к элементу контейнера будет трактован как чтение или запись     reference operator * () {         sendMessage("reference operator * ()");         sendAccessEvent();         return *current_;     }          void sendAccessEvent() const {         difference_type pos = getOffset();         assert(pos >= 0);         Access event(pos);         handler_.handle(event);     }  private:         IEventHandler& handler_;     OriginalIterator begin_;     OriginalIterator current_; }; 

Поэтому оказался необходим механизм интерпретации последовательности доступов к контейнеру в последовательность чтений и записей. Такая интерпретация осуществляется посредством сравнения версий исходного и измененного контейнера после каждого разыменования итератора.

template <typename Container> class EventInterpreter: public IEventHandler { public:     /*          ...     */     void handle(Event& event) override {         if (event.getType() != Event::Access)             return;         if (recordingIsPaused_ )             return;         // Каждая запись и чтение имеет временную отметку.          // Приостанавливаем время, чтобы процесс обработки событий не влиял на тайминг.         pause_guard pause(*stopwatch_);         // Проверяем, изменился ли контейнер и интерпретируем изменения как операции записи.         checkWriting();     // Сохраняем информацию о доступе к элементу контейнера         addAccess(static_cast<Access&>(event));     } private:     /*          ...     */     Script script_;     Container copy_;     std::shared_ptr<Container> original_;     std::shared_ptr<Stopwatch> stopwatch_; };

Важной особенностью решения является отделение визуализации и логирования. Логирование алгоритма происходит до его визуализации. Результат сохраняется в файл. Далее этот файл загружается отдельной программой, отвечающей только за «проигрывание» полученного лог-файла. Пример такого файла:

std::sort_heap 24,24,22,20,20,21,21,4,8,12,10,9,20,18,18,2,1,5,4,4,4,3,8,2,3,1,8,4,18,14 932,access,29 1563,access,0 2074,write,29,24 3096,access,2 3587,access,1 4269,access,1 4920,access,0 5712,access,4 ...

При наличии лог-файла визуализация не составляет труда. Во второй строке указаны исходные данные контейнера. Далее операции чтения или записи. В первом столбце указаны: временная отметка (наносекунды), тип операции, позиция и новое значение, если это запись.

С полным исходным кодом можно ознакомиться по ссылке

Продолжение.