Сравнение времени работы различных алгоритмов транспонирования матриц

Рассмотрим 3 алгоритма c асимптотикой O(n²):

1. stupid – идет по диагоналям матрицы, начиная с самой нижней и заканчивая верхней, обращаясь к элементам различных массивов.
2. naive – наивый алгоритм, проходит последовательно по всем столбцам и записывает значения из них в соответствующие строки.
3. cacheOblivious – кэш-эффективный алгоритм, на каждом этапе разделяющий обрабатываемый участок пополам по большей стороне. После того, как такой алгоритм доходит до достаточно маленького прямоугольника, он транспонирует обрабатываемый участок наивно (данная модификация требуется, чтобы добиться оптимального сотношения выгоды от учёта существования кэша и затрат на рекурсивные вызовы). Он использует принцип пространственной локальности кэш-памяти компьютера.

Реализации алгоритмов – методы класса matrix, они реализованы в файле matrix.cpp.

Результаты тестирования

На графике видно, что при небольших размерах (не превышающих 2·10³) разность во времени работы описанных алгоритмов пренебрежимо мала, при этом на бо́льших, чем 2.5·10³ она становится заметной.

Алгоритм (3) быстрее, чем (2), чуть меньше чем в 2 раза, и быстрее, чем (1), заметно больше, чем в два раза.