Краткий ответ

Обход строк обычно быстрее из-за локальности доступа к памяти: соседние элементы строки расположены рядом в структуре данных и эффективнее используются кэшем процессора. При обходе столбцов программа чаще обращается к удалённым участкам памяти, поэтому растёт число промахов кэша и увеличивается задержка доступа.

Для вложенных списков Python эффект сложнее, чем для непрерывного числового массива: сами списки хранят ссылки, а объекты значений могут находиться в разных местах памяти. Тем не менее последовательный обход каждого внутреннего списка обычно лучше соответствует расположению его массива ссылок.

Исторический контекст

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

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

Постановка проблемы

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

Неверный порядок обхода приводит к менее предсказуемым обращениям к памяти. В результате процессор чаще ждёт загрузки данных, а оптимизация только количества Python-операций может не устранить основное узкое место.

Подробное решение

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

Минимальная иллюстрация различия порядка обхода:

matrix = [list(range(1000)) for _ in range(1000)]

row_total = 0
for row in matrix:
    for value in row:
        row_total += value

column_total = 0
for column in range(1000):
    for row in matrix:
        column_total += row[column]

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

Для списка Python нужно учитывать двойную косвенность: сначала читается ссылка из списка, затем сам объект, на который она указывает. Поэтому результат зависит не только от порядка обхода, но и от типа данных, размеров матрицы, размещения объектов и доли времени, которую занимает интерпретация Python-кода.

Практическое решение — хранить данные в формате, соответствующем вычислениям. Для плотных числовых данных специализированный непрерывный буфер или массивная библиотека обычно лучше вложенных списков: значения могут храниться компактнее, а операции выполняться в оптимизированном коде. Компромисс — необходимость подходящего типа данных, возможное копирование при преобразовании и менее универсальная модель по сравнению с обычными Python-объектами.

Изменять порядок циклов следует только после измерения. Маленькая матрица может полностью помещаться в кэш, а для неё стоимость Python-итераций или других операций может подавить эффект локальности. Проверять нужно время на реалистичном размере данных, а не только асимптотику алгоритма.

Ситуация из практики

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

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

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

Что кандидаты часто упускают

Всегда ли обход строк быстрее обхода столбцов?

Нет. Это не гарантия языка Python, а следствие конкретного представления данных, размера рабочей области и характера операции. Если матрица мала, данные уже находятся в кэше или основное время тратится на вызовы Python-функций, разница может быть незаметной. Кроме того, библиотека может хранить массив в другом порядке или сама оптимизировать доступ.

Почему замена вложенных списков на непрерывный массив может дать больший эффект, чем перестановка циклов?

Вложенные списки содержат ссылки на объекты Python, поэтому обработка значения может включать разыменование ссылки и работу с отдельным объектом. Непрерывный типизированный массив хранит элементы плотнее и часто позволяет выполнить цикл в коде библиотеки, минуя большое число интерпретируемых Python-операций. Цена — ограниченный набор типов, возможные преобразования и потеря универсальности обычных объектов.

Как отличить влияние локальности от обычной разницы в Python-коде?

Нужно сравнивать реализации с одинаковой логикой, количеством операций и одинаковым набором данных, измеряя их на нескольких размерах матрицы. Если преимущество появляется только после того, как рабочий набор перестаёт помещаться в кэш, это указывает на влияние иерархии памяти. Для подтверждения используют профилировщики аппаратных событий, способные показать промахи кэша, но сначала достаточно корректного бенчмарка и проверки профиля CPU.