Numpy: транспонировать результат расширенного индексирования

>>> import numpy as np
>>> X = np.arange(27).reshape(3, 3, 3)
>>> x = [0, 1]
>>> X[x, x, :]
array([[ 0,  1,  2],
       [12, 13, 14]])

Мне нужно суммировать его по измерению 0, но в реальном мире матрица огромна, и я бы предпочел суммировать ее по измерению -1, что быстрее из-за расположения памяти. Следовательно, я хотел бы, чтобы результат был транспонирован:

array([[ 0, 12],
       [ 1, 13],
       [ 2, 14]])

Как я могу это сделать? Я хотел бы, чтобы результат «расширенной индексации» numpy был неявно транспонирован. Транспонировать его явно с .T в конце еще медленнее и не вариант.

Update1: в реальном мире расширенная индексация неизбежна, а одинаковые индексы не гарантируются.

>>> x = [0, 0, 1]
>>> y = [0, 1, 1]
>>> X[x, y, :]
array([[ 0,  1,  2],
       [ 3,  4,  5],
       [12, 13, 14]])

Update2: чтобы уточнить, что это не проблема XY, вот собственно проблема:

У меня есть большая матрица X, которая содержит элементы x из некоторого распределения вероятностей. Распределение вероятности элемента зависит от окрестности элемента. Этот дистрибутив неизвестен, поэтому я следую процедуре выборки Гиббса, чтобы построить матрицу, состоящую из элементов из этого распределение. В двух словах это означает, что я делаю некоторое начальное предположение для матрицы X, а затем продолжаю перебирать элементы матрицы X, обновляя каждый элемент x формулой, которая зависит от соседних значений x. Итак, для любого элемента матрицы мне нужно получить его соседей (расширенная индексация) и выполнить над ними некоторую операцию (суммирование в моем примере). Я использовал line_profiler, чтобы увидеть, что строка, которая занимает большую часть времени в моем коде, берет сумму массива относительно измерения 0, а не -1. Поэтому я хотел бы знать, есть ли способ создать уже транспонированную матрицу в результате расширенной индексации.


person alisianoi    schedule 28.12.2014    source источник
comment
Я могу быть удивлен, если есть более быстрый способ, чем numpy.transpose, выполнить эту работу, так как она компилируется в C.!   -  person kasravnd    schedule 28.12.2014
comment
Я проголосовал за ваш вопрос, но подозреваю, что может быть небольшая проблема с XY происходит здесь.   -  person NPE    schedule 28.12.2014
comment
@NPE Тогда я могу описать проблему. Сейчас будет обновление   -  person alisianoi    schedule 28.12.2014
comment
@NPE сделал все возможное, чтобы обновить. Большая картина не очень помогает, извините.   -  person alisianoi    schedule 28.12.2014
comment
@all3fox: Это здорово, спасибо, что нашли время, чтобы предоставить некоторый контекст.   -  person NPE    schedule 28.12.2014
comment
Я предполагаю, что имеет значение фактическое расположение памяти, а не то, какая это ось. Другими словами, если элементы, которые вы хотите суммировать, не хранятся в памяти рядом друг с другом, это будет медленным независимо от того, на какой оси результирующей матрицы они находятся. Если вам удалось получить транспонированную матрицу, вы просто переместите замедление от операции суммы к операции транспонирования.   -  person BrenBarn    schedule 28.12.2014
comment
@BrenBarn да, вы правы, мне нужна структура памяти. В python последний индекс -1 в макете памяти по умолчанию C является самым быстрым (местность). Вот почему мне нужно, чтобы новый массив, который всегда создается с помощью расширенной индексации, был транспонирован --- таким образом я смогу суммировать по самому быстрому индексу.   -  person alisianoi    schedule 28.12.2014
comment
@all3fox В python последний индекс -1 в макете памяти C по умолчанию является самым быстрым (локальностью) - нет, я думаю, вы путаетесь с массивами Fortran. С массивом строк будет быстрее обращаться к соседним элементам в измерении 0th, а не в измерении -1th.   -  person ali_m    schedule 28.12.2014
comment
@ali_m, кажется, это наоборот. И когда я проверил это, это было ложно. X = np.random.randn(100, 100, 100); X.sum(-1) у меня самый быстрый (с коэффициентом 0,6:1); X.sum(1) лишь немного быстрее, чем X.sum(0) (примерно в 0,9:1). Смотрите мой комментарий ниже.   -  person senderle    schedule 29.12.2014
comment
@senderle Это странно - используя точно такую ​​​​же настройку, X.sum(0) занимает 819 долларов США, X.sum(1) - 861 доллар США, а X.sum(2) - 887 долларов США. В вашем примере вы можете подтвердить, что X.flags.c_contiguous == True?   -  person ali_m    schedule 29.12.2014
comment
Подтвержденный. X.flags.c_contiguous это True. Отредактировано: повторно подтверждено после вашего комментария ниже.   -  person senderle    schedule 29.12.2014
comment
@senderle В этом случае моя единственная мысль состоит в том, что это должно быть какая-то странная вещь, зависящая от архитектуры. У вас есть другая машина, на которой вы можете это проверить?   -  person ali_m    schedule 29.12.2014
comment
Это будет почти идентичное оборудование. Но теоретический момент остается - суммирование по -1 должно быть самым быстрым, если только я не ошибаюсь катастрофически. Но я думаю, что все ставки сняты, это зависит от архитектуры или версии numpy. Я использую Intel Mac со встроенным numpy версии 1.6.2.   -  person senderle    schedule 29.12.2014
comment
@senderle FWIW это действительно похоже на версию numpy - я также вижу, что порядок таймингов обратный для numpy v1.6.2. Должен признаться, что я никогда особо не задумывался о том, каким должен быть теоретически оптимальный порядок — я всегда просто выполняю самые быстрые тесты. Основываясь на моем чтении вики-страницы, кажется, что суммирование по последнему измерению должно быть наиболее удобным для кэширования, но факт в том, что (по крайней мере, для последних версий numpy) верно обратное.   -  person ali_m    schedule 29.12.2014
comment
Интересный! Что ж, это доказывает вашу большую точку зрения, не так ли? Давайте продолжим обсуждение в чате.   -  person senderle    schedule 29.12.2014


Ответы (1)


Я хотел бы суммировать его по измерению 0, но в реальном мире матрица огромна, и я бы предпочел суммировать ее по измерению -1, что быстрее из-за расположения памяти.

Я не совсем уверен, что вы имеете в виду под этим. Если базовый массив является основным по строкам (по умолчанию, т. е. X.flags.c_contiguous == True), то его суммирование по 0-му измерению может быть немного быстрее. Простое перемещение массива с помощью .T или np.transpose() само по себе не меняет способ расположения массива в памяти.

Например:

# X is row-major
print(X.flags.c_contiguous)
# True

# Y is just a transposed view of X
Y = X.T

# the indices of the elements in Y are transposed, but their layout in memory
# is the same as in X, therefore Y is column-major rather than row-major
print(Y.flags.c_contiguous)
# False

Вы можете преобразовать из упорядочения по строкам в упорядочение по столбцам, например, с помощью np.asfortranarray(X), но невозможно выполнить это преобразование без создания полной копии X в памяти. Если вы не собираетесь выполнять множество операций над столбцами X, тогда почти наверняка не стоит выполнять преобразование.

Если вы хотите сохранить результат суммирования в массиве столбцов, вы можете использовать out= kwarg для X.sum(), например:

result = np.empty((3, 3), order='F') # Fortran-order, i.e. column-major
X.sum(0, out=result)

В вашем случае разница между суммированием строк и столбцов, вероятно, будет очень минимальной, поскольку вы уже собираетесь индексировать несмежные элементы в X, вы уже потеряете преимущество < href="http://en.wikipedia.org/wiki/Locality_of_reference#Spatial_and_temporal_locality_usage" rel="nofollow">пространственное расположение ссылки, которое обычно несколько ускоряет суммирование по строкам.

Например:

X = np.random.randn(100, 100, 100)

# summing over whole rows is slightly faster than summing over whole columns
%timeit X.sum(0)
# 1000 loops, best of 3: 438 µs per loop
%timeit X.T.sum(0)
# 1000 loops, best of 3: 486 µs per loop

# however, the locality advantage disappears when you are addressing
# non-adjacent elements using fancy indexing
%timeit X[[0, 0, 1], [0, 1, 1], :].sum()
# 100000 loops, best of 3: 4.72 µs per loop
%timeit X.T[[0, 0, 1], [0, 1, 1], :].sum()
# 100000 loops, best of 3: 4.63 µs per loop

Обновлять

@senderle упомянул в комментариях, что при использовании numpy v1.6.2 он видит обратный порядок времени, то есть X.sum(-1) быстрее, чем X.sum(0) для массива строк. Кажется, это связано с версией numpy, которую он использует - используя v1.6.2, я могу воспроизвести порядок, который он наблюдает, но используя две более новые версии (v1.8.2 и 1.10.0.dev-8bcb756), я наблюдаю обратное ( то есть X.sum(0) быстрее, чем X.sum(-1) с небольшим отрывом). В любом случае, я не думаю, что изменение порядка памяти в массиве может сильно помочь в случае OP.

person ali_m    schedule 28.12.2014
comment
Чтобы уточнить, что я хочу: я знаю, что расширенная индексация создает новый массив numpy. Вместо этого я хотел бы сделать транспонированную версию этого массива. Я также вижу ваши тайминги, спасибо. Похоже, ускорение все-таки будет небольшим. - person alisianoi; 28.12.2014
comment
По моим таймингам с вашим 3д X, X.sum(0) и X.T.sum(-1) занимают одинаковое время. X.sum(-1) и X.T.sum(0) одинаково быстрее. X.T просто изменяет массив на Fcontiguous. - person hpaulj; 28.12.2014
comment
@hpaulj Я не удивлен, увидев изменчивость величины эффекта - эти эффекты локальности обычно очень зависят от процессора и компилятора. - person ali_m; 28.12.2014
comment
Я чувствую, что может возникнуть некоторая путаница в отношении того, что означает суммирование по измерению x. Насколько я понимаю, a.sum(0) суммирует по 0-му измерению, что означает, что он суммирует векторы column. Другими словами, он уменьшает 0-е измерение. Итак, если у вас есть массив (2, 5), и вы суммируете по 0 измерению, вы получаете массив из пяти элементов. Поскольку numpy по умолчанию хранит данные последовательно по строкам, суммирование по 0-му измерению будет немного медленнее (при условии, что измерения имеют одинаковый размер). - person senderle; 29.12.2014
comment
И я добавлю, что когда я вырезаю и вставляю тестовый код выше в ipython, я получаю противоположный результат. X.T.sum(0) более чем в два раза быстрее. Значит, что-то тут не так... - person senderle; 29.12.2014
comment
@senderle Я не знаю, что сказать - я подтвердил тайминги на двух разных машинах и с двумя разными версиями numpy (v1.8.2 и 1.10.0.dev-8bcb756). В каждом случае, который я пробовал до сих пор, X.sum(0)X.sum(1)X.sum(2). Вы можете точно подтвердить это X.flags.c_contiguous == True? - person ali_m; 29.12.2014