Визуализация алгоритмов стандартной библиотеки 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 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 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(event)); > private: /* . */ Script script_; Container copy_; std::shared_ptr original_; std::shared_ptr 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 . При наличии лог-файла визуализация не составляет труда. Во второй строке указаны исходные данные контейнера. Далее операции чтения или записи. В первом столбце указаны: временная отметка (наносекунды), тип операции, позиция и новое значение, если это запись.
Rotate c что это
Шаг 297.
Библиотека STL. Алгоритмы STL. Перестановочные алгоритмы. Циклический сдвиг элементов. Циклический сдвиг элементов внутри интервала
На этом шаге мы рассмотрим использование алгоритма, выполняющего циклический сдвиг элементов внутри интервала .
Для выполнения этой операции можно использовать следующий алгоритм:
void rotate (ForwardIterator beg, ForwardIterator newBeg, ForwardIterator end)
Производит циклический сдвиг элементов в интервале [beg,end) . После вызова *newBeg становится новым первым элементом.
Перед вызовом необходимо убедиться в том, что newBeg представляет действительную позицию н интервале [beg,end) ; в противном случае вызов приводит к непредсказуемым последствиям.
Сложность линейная (не более numberOfElements обменов).
Пример использования алгоритма rotate() :
//--------------------------------------------------------------------------- #include #include #include "algostuff.hpp" #include //необходимо для getch() #pragma hdrstop //--------------------------------------------------------------------------- #pragma argsused using namespace std; std::string ToRus(const std::string &in) < char *buff = new char [in.length()+1]; CharToOem(in.c_str(),buff); std::string out(buff); delete [] buff; return out; > int main() < vectorcoll; INSERT_ELEMENTS(coll,1,9); PRINT_ELEMENTS(coll,"Исходная коллекция:\n"); // Циклический сдвиг на один элемент влево rotate (coll.begin(), // Начало интервала coll.begin() + 1, // Новый первый элемент coll.end()); // Конец интервала PRINT_ELEMENTS(coll,"Циклический сдвиг на один элемент влево:\n"); // Циклический сдвиг на два элемента вправо rotate (coll.begin(), // Начало интервала coll.end() - 2, // Новый первый элемент coll.end()); // Конец интервала PRINT_ELEMENTS(coll,"Циклический сдвиг на два элемента вправо:\n"); // Циклический сдвиг, в результате которого элемент со значением 4 // переходит в начало rotate (coll.begin(), // Начало интервала find(coll.begin(),coll.end(),4), // Новый первый элемент coll.end()); // Конец интервала PRINT_ELEMENTS(coll,"Циклический сдвиг c 4 вначале:\n"); getch(); return 0; > //---------------------------------------------------------------------------
Текст этого примера можно взять здесь.
Как видно из приведенного примера, циклический сдвиг влево осуществляется с положительным смещением от начала, а сдвиг вправо — с отрицательным смещением от конца. Тем не менее прибавление смещения к итератору возможно только при использовании итераторов произвольного доступа (векторы поддерживают такие итераторы). Без итераторов произвольного доступа необходима функция advance() .
Результат выполнения программы выглядит так:
Рис.1. Результат выполнения приложения
На следующем шаге мы рассмотрим циклический сдвиг элементов при копировании .
Функция rotate
В данном примере блок повернут на 30 градусов по часовой стрелке:
#elem < transform: rotate(30deg); border: 1px solid black; width: 100px; height: 50px; >
Пример
В данном примере блок повернут на 30 градусов против часовой стрелки:
#elem < transform: rotate(-30deg); border: 1px solid black; width: 100px; height: 50px; >
Пример
В данном примере блок по наведению повернется на 1 оборот, так как значение поворота задано в 1turn (такого же эффекта можно добиться, если задать угол поворота в 360deg ). Для плавности поворота добавлено свойство transition :
#elem < border: 3px solid black; width: 100px; height: 50px; transition: transform 3s linear; >#elem:hover < transform: rotate(1turn); >
Смотрите также
- функцию rotateX ,
которая задает поворот по оси X - функцию rotateY ,
которая задает поворот по оси Y - функцию rotateZ ,
которая задает поворот по оси Z - функцию rotate3d ,
которая задает поворот по трем осям
Rotate своими руками
Паинт своими руками
Пишу свой паинт (точнее написал) но встала задача переписать его без использования типа данных HDC.
pdf reader своими руками
Прошу помощи. Нужна любая информация, которая поможет написать простейший pdf reader на C++.
Ассоциативный массив своими руками
Подскажите, пожалуйста, как реализовать такую конструкцию: array = 324;
Парсер collada своими руками
За рекурсивный парсинг берусь впервые, поэтому просьба "Ересь!" громко не орать и в теме не.
4681 / 2503 / 879
Регистрация: 29.11.2010
Сообщений: 5,454
1 2 3 4 5 6 7 8 9 10 11 12 13
templateclass ForwardIt> void rotate(ForwardIt first, ForwardIt n_first, ForwardIt last) { ForwardIt next = n_first; while (first != next) { std::swap(*first++, *next++); if (next == last) { next = n_first; } else if (first == n_first) { n_first = next; } } }
27698 / 17315 / 3811
Регистрация: 24.12.2010
Сообщений: 38,979
Сообщение от АнтонВарушин 
функцию Rotate
Что за функция? Что она делает? Если то, что я думаю, то есть весьма изячные алгоритмы.
Регистрация: 02.07.2019
Сообщений: 32
У нас есть массив 1 2 3 4 5 6 7 8 9 10
мы выбераем 1 2 3 и переносим в конец массива и на выходе 4 5 6 7 8 9 10 1 2 3
Но мне нужн только простой алгоритм
4681 / 2503 / 879
Регистрация: 29.11.2010
Сообщений: 5,454
Сообщение от АнтонВарушин
Но мне нужн только простой алгоритм
Куда уж проще-то?
Добавлено через 2 минуты
Сообщение от Байт
Что за функция? Что она делает?
Копипаста:
Меняет местами элементы в диапазоне [first, last) таким образом, что элемент n_first становится первым в новом диапазоне, а n_first-1 — последним.
Реализована в STL.
27698 / 17315 / 3811
Регистрация: 24.12.2010
Сообщений: 38,979
Сообщение от АнтонВарушин
простой алгоритм
Циклический сдвиг, значит.
N — размер массива, K — величина сдвига.
Разбиваем массив на 2 части размером K и N-K: 1 2 3 и 4 5 6 7 8 9 10.
Каждую часть переворачием 3 2 1 и 10 9 8 7 6 5 4
Соединяем и переворачиваем уже весь массив: 4 5 6 7 8 9 10 1 2 3 — Вуаля!
Алгоритм имеет условное название «Два кулака». придуман не мной, а уважаемым участником форума ValeryS
Есть и другие, несколько более эффективные алгоритмы, основанные на НОД (Наибольшем Общем Делителе), но и этот очень неплох, а главное, прост
На форуме это все обсуждалось. Найду — дам ссылочку.
Добавлено через 3 минуты
Сообщение от lemegeton
Меняет местами элементы в диапазоне
Но из поста 4 следует, что это не совсем то, что требуется ТС. (поэтому я и спросил). У вас — переворот (что действительно просто). Циклический сдвиг — это чуток посложнее (если, конечно, не реализовать его K сдвигами на 1 )
Добавлено через 1 минуту
Сообщение от lemegeton
Реализована в STL.
Имхо, именно это и вызывает сложности (понимания) ТС.