Обход матрицы также распространен в обработке изображений, машинном обучении и конкурентном программировании.

В таких языках, как C и C++, обход матрицы построчно выполняется значительно быстрее, чем по столбцу за столбцом.

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

Вот ловушка, в которую люди невольно попадают.

Обход матрицы строка за строкой или столбец за столбцом может сильно повлиять на общую производительность вашего кода.

Интересно, почему? 🤔

Это из-за механизма кэширования, который используют компьютеры. В таких языках, как C и C++, двумерный массив целых чисел представляется как линейная последовательность целых чисел в памяти. Есть два способа линейного хранения этих целых чисел:

1) Строковый порядок

2) Колонка-мажорный порядок

Рассмотрим следующую матрицу M

Строковый порядок для M: 1 2 3 4 5 6 7 8 9

Столбец-мажорный порядок для M: 1 4 7 2 5 8 3 6 9

Порядок варьируется от языка к языку. Например, C и C++ используют порядок строк, в то время как Fortran использует порядок столбцов.

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

Причина этого проста. Когда ЦП обращается к элементу массива, он должен получить доступ к ячейке памяти, в которой он хранится. При доступе к ячейке памяти он загружает часть памяти вокруг ячейки, включая ячейку, и сохраняет ее в кэше. Из-за этого в кеш загружается непрерывный блок памяти, который содержит требуемый элемент вместе с соседними с ним элементами. Теперь, если ЦП пытается получить доступ к следующему элементу или любому элементу, который находится рядом с элементом, к которому мы обращались ранее, он с большей вероятностью будет найден в кеше, что приведет к высокой вероятности попадания в кеш, что приведет к более быстрому время доступа (CPU всегда сначала ищет необходимые данные в кеше, а затем в RAM). Таким образом, это приводит к значительному сокращению общего времени доступа, тем самым улучшая общее время выполнения.

Я сравнивал его с матрицей 10000 * 10000. Построчный обход был в 2,5 раза быстрее, чем постолбцовый обход на моей машине.

Можете попробовать на своей машине. Вот ссылка на код для запуска.

Подпишитесь на другие подобные материалы 🙌