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