В интернете много различных видео, в которых визуализируются алгоритмы. Как правило, такая визуализация делается под определенный алгоритм, и код отрисовки соединен с кодом самого алгоритма. Мне пришла идея отделить визуализацию алгоритма от его исполнения. Тогда можно будет визуализировать любой алгоритм. В том числе алгоритмы стандартной библиотеки С++. Я нашёл способ сделать это, и вот что у меня получилось.
Алгоритмы
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
...При наличии лог-файла визуализация не составляет труда. Во второй строке указаны исходные данные контейнера. Далее операции чтения или записи. В первом столбце указаны: временная отметка (наносекунды), тип операции, позиция и новое значение, если это запись.
