Внутренняя организация массивов NumPy

Проблемы с порядком индексирования многомерных массивов

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

В первую очередь необходимо понять, что существуют две противоречивые конвенции индексирования двумерных массивов. Матричная нотация использует первый индекс для указания строки, а второй индекс — для указания столбца. Это противоположно геометрически ориентированной конвенции для изображений, где обычно первый индекс обозначает положение по оси x (т.е., столбец), а второй — по оси y (т.е., строка). Именно это является источником многих затруднений; пользователи, привыкшие к матричной нотации, и пользователи, ориентированные на изображения, ожидают разного поведения индексирования.

Вторая проблема заключается в том, как индексы соответствуют порядку хранения массива в памяти. В Fortran первый индекс изменяется быстрее всего при перемещении по элементам двумерного массива в памяти. Если вы используете матричную конвенцию индексирования, это означает, что матрица хранится по столбцам (так как при изменении первого индекса происходит переход к следующей строке). Поэтому Fortran считается языком с порядком хранения по столбцам. В C используется противоположная конвенция. В C последний индекс изменяется быстрее всего при перемещении по массиву в памяти. Поэтому C является языком с порядком хранения по строкам. Матрица хранится по строкам. Обратите внимание, что в обоих случаях предполагается использование матричной конвенции индексирования, т.е. для Fortran и C первый индекс соответствует строке. Эта конвенция подразумевает, что конвенция индексирования неизменна, а порядок данных изменяется для сохранения этого.

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

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

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

Итак, если это так, почему не выбрать порядок индексов, который наиболее соответствует вашим ожиданиям? В частности, почему не определить изображения с порядком по строкам так, чтобы использовать конвенцию для изображений? (Это иногда называется конвенцией Fortran против конвенции C, отсюда и опции «C» и «FORTRAN» для порядка массивов в NumPy.) Недостатком этого является потенциальное снижение производительности. Часто данные обращаются последовательно, либо неявно в операциях с массивами, либо явно при переборе строк изображения. При этом данные будут обращаться в не оптимальном порядке. Когда инкрементируется первый индекс, фактически происходит обращение к элементам, находящимся далеко друг от друга в памяти, с, как правило, низкой скоростью доступа к памяти. Например, для двумерного изображения im определенного так, что im[0, 10] представляет значение в x = 0, y = 10. Для согласованности с обычным поведением Python, im[0] представляло бы столбец в x = 0. Однако эти данные были бы распределены по всему массиву, так как данные хранятся в порядке строк. Несмотря на гибкость индексирования в NumPy, оно не может полностью устранить тот факт, что базовые операции снижают эффективность из-за порядка данных или что получение непрерывных подмассивов по-прежнему затруднено (например, im[:, 0] для первой строки, против im[0]). Таким образом, нельзя использовать идиому, такую как for row in im; for col in im работает, но не приводит к получению непрерывных столбцов данных.

Как оказалось, NumPy достаточно умен при работе с ufuncs, чтобы определить, какой индекс изменяется быстрее всего в памяти, и использовать его для внутреннего цикла. Таким образом, для ufuncs в большинстве случаев нет большого принципиального преимущества ни в одном из подходов. С другой стороны, использование ndarray.flat с массивом в порядке Fortran приведет к неэффективному доступу к памяти, так как соседние элементы в сглаженном массиве (итератор, собственно) не являются смежными в памяти.

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

Если вы хотите использовать порядок Fortran, учтите два подхода: 1) примите тот факт, что первый индекс не является самым быстро меняющимся в памяти, и все ваши процедуры ввода-вывода должны переупорядочивать данные при переходе из памяти на диск и обратно, или используйте механизм NumPy для сопоставления первого индекса с самым быстро меняющимся данными. Мы рекомендуем первый подход, если это возможно. Недостатком второго подхода является то, что многие функции NumPy будут возвращать массивы без порядка Fortran, если вы не позаботитесь о ключевом слове order. Это было бы очень неудобно.

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