Эффективная 2D-матрица из массива 1D

Ответ 1

На самом деле есть еще более эффективный способ сделать это... Недостатком использования vstack и т.д. является то, что вы делаете копию массива.

Кстати, это фактически идентично ответу @Paul, но я публикую это только для того, чтобы объяснить вещи немного подробнее...

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

Я напрямую заимствую это из сообщение Эрика Ригторпа в numpy-обсуждение, который, в свою очередь, заимствовал его у Keith Goodman Bottleneck (что очень полезно!).

Основной трюк состоит в том, чтобы напрямую манипулировать шагами массива (для одномерных массивов):

import numpy as np

def rolling(a, window):
    shape = (a.size - window + 1, window)
    strides = (a.itemsize, a.itemsize)
    return np.lib.stride_tricks.as_strided(a, shape=shape, strides=strides)

a = np.arange(10)
print rolling(a, 3)

Где a - ваш входной массив, а window - длина требуемого окна (3, в вашем случае).

Это дает:

[[0 1 2]
 [1 2 3]
 [2 3 4]
 [3 4 5]
 [4 5 6]
 [5 6 7]
 [6 7 8]
 [7 8 9]]

Тем не менее, нет полного дублирования памяти между исходным a и возвращенным массивом. Это означает, что он быстро и масштабируется намного лучше, чем другие варианты.

Например (используя a = np.arange(100000) и window=3):

%timeit np.vstack([a[i:i-window] for i in xrange(window)]).T
1000 loops, best of 3: 256 us per loop

%timeit rolling(a, window)
100000 loops, best of 3: 12 us per loop

Если мы обобщим это на "скользящее окно" вдоль последней оси для N-мерного массива, мы получим функцию "качения" Эрика Ригторпа:

import numpy as np

def rolling_window(a, window):
   """
   Make an ndarray with a rolling window of the last dimension

   Parameters
   ----------
   a : array_like
       Array to add rolling window to
   window : int
       Size of rolling window

   Returns
   -------
   Array that is a view of the original array with a added dimension
   of size w.

   Examples
   --------
   >>> x=np.arange(10).reshape((2,5))
   >>> rolling_window(x, 3)
   array([[[0, 1, 2], [1, 2, 3], [2, 3, 4]],
          [[5, 6, 7], [6, 7, 8], [7, 8, 9]]])

   Calculate rolling mean of last dimension:
   >>> np.mean(rolling_window(x, 3), -1)
   array([[ 1.,  2.,  3.],
          [ 6.,  7.,  8.]])

   """
   if window < 1:
       raise ValueError, "`window` must be at least 1."
   if window > a.shape[-1]:
       raise ValueError, "`window` is too long."
   shape = a.shape[:-1] + (a.shape[-1] - window + 1, window)
   strides = a.strides + (a.strides[-1],)
   return np.lib.stride_tricks.as_strided(a, shape=shape, strides=strides)

Итак, рассмотрим, что происходит здесь... Манипуляция массивом strides может показаться немного волшебным, но как только вы поймете, что происходит, это совсем не так. Шаги массива numpy описывают размер в байтах шагов, которые необходимо предпринять, чтобы увеличить одно значение вдоль данной оси. Итак, в случае одномерного массива 64-битных поплавков длина каждого элемента составляет 8 байтов, а x.strides - (8,).

x = np.arange(9)
print x.strides

Теперь, если мы преобразуем это в массив 2D, 3x3, шаги будут (3 * 8, 8), так как нам нужно было бы прыгать 24 байта для увеличения на один шаг вдоль первой оси и 8 байтов для увеличения на один шаг вдоль вторая ось.

y = x.reshape(3,3)
print y.strides

Аналогично, транспозиция такая же, как просто изменение шагов массива:

print y
y.strides = y.strides[::-1]
print y

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

Поэтому, если вы хотите одновременно изменять форму и размер массива, вы не можете сделать это, установив x.strides и x.shape, даже если новые шаги и форма совместимы.

То, что входит numpy.lib.as_strided. Это на самом деле очень простая функция, которая просто устанавливает шаги и форму массива одновременно.

Он проверяет, совместимы ли эти два, но не то, что старые шаги и новая форма совместимы, как это происходит, если вы установите два независимо друг от друга. (Фактически это делает через numpy __array_interface__, который позволяет произвольным классам описывать буфер памяти как массив numpy.)

Итак, все, что мы сделали, сделало так, что один шаг вперед (8 байтов в случае 64-разрядного массива) вдоль одной оси, но также только шаги 8 байт вперед вдоль другой оси.

Другими словами, в случае "окна" размером 3, массив имеет форму (whatever, 3), но вместо того, чтобы выполнить полный 3 * x.itemsize для второго измерения, он выполняет только один элемент вперед, эффективно делая строки нового массива "движущимся окном" в исходном массиве.

(Это также означает, что x.shape[0] * x.shape[1] не будет таким же, как x.size для вашего нового массива.)

Во всяком случае, надеюсь, это делает вещи немного яснее..

Ответ 2

Это решение неэффективно реализуется с помощью цикла python, поскольку он поставляется с любыми типами проверки типов, которых лучше избегать при работе с массивами numpy. Если ваш массив исключительно высок, вы заметите большую скорость:

newshape = (4,3)
newstrides = (A.itemsize, A.itemsize)
B = numpy.lib.stride_tricks.as_strided(A, shape=newshape, strides=newstrides)

Это дает представление о массиве А. Если вам нужен новый массив, который вы можете редактировать, выполните то же самое, но с .copy() в конце.

Подробности по шагам:

Кортеж newstrides в этом случае будет (4,4), потому что массив имеет 4 байтовые элементы, и вы хотите продолжать выполнять шаги по вашим данным на шагах с одним элементом в i-измерении. Второе значение "4" относится к шагам в j-размерности (в обычном массиве 4x4 это будет 16). Потому что в этом случае вы также хотите увеличить количество чтения из буфера в 4-байтовых шагах в j-мерном размере.

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

Ответ 3

Какой подход вы используете?

import numpy as np
A = np.array([1,2,3,4,5,6,7,8,9,10])
width = 3

np.vstack([A[i:i-len(A)+width] for i in xrange(len(A)-width)])
# needs 26.3µs

np.vstack([A[i:i-width] for i in xrange(width)]).T
# needs 13.2µs

Если ваша ширина относительно низкая (3) и у вас большой A (10000 элементов), то разница еще важнее: 32,4 мс для первого и 44 мкс для второго.

Ответ 4

Просто чтобы продолжить с ответа @Joe вообще

import numpy as np
def rolling(a, window):
    step = 2 
    shape = ( (a.size-window)/step + 1   , window)


    strides = (a.itemsize*step, a.itemsize)

    return np.lib.stride_tricks.as_strided(a, shape=shape, strides=strides)

a = np.arange(10)

print rolling(a, 3)

который выводит:

[[0 1 2]
 [2 3 4]
 [4 5 6]
 [6 7 8]]

Для дальнейшего обобщения для случая 2d, используйте его для извлечения патча из изображения

def rolling2d(a,win_h,win_w,step_h,step_w):

    h,w = a.shape
    shape = ( ((h-win_h)/step_h + 1)  * ((w-win_w)/step_w + 1) , win_h , win_w)

    strides = (step_w*a.itemsize, h*a.itemsize,a.itemsize)


    return np.lib.stride_tricks.as_strided(a, shape=shape, strides=strides)

a = np.arange(36).reshape(6,6)
print a
print rolling2d (a,3,3,2,2)

который выводит:

[[ 0  1  2  3  4  5]
 [ 6  7  8  9 10 11]
 [12 13 14 15 16 17]
 [18 19 20 21 22 23]
 [24 25 26 27 28 29]
 [30 31 32 33 34 35]]
[[[ 0  1  2]
  [ 6  7  8]
  [12 13 14]]

 [[ 2  3  4]
  [ 8  9 10]
  [14 15 16]]

 [[ 4  5  6]
  [10 11 12]
  [16 17 18]]

 [[ 6  7  8]
  [12 13 14]
  [18 19 20]]]

Ответ 5

Я думаю, что это может быть быстрее, чем цикл, когда ширина фиксируется с низким номером...

import numpy
a = numpy.array([1,2,3,4,5,6])
b = numpy.reshape(a, (numpy.shape(a)[0],1))
b = numpy.concatenate((b, numpy.roll(b,-1,0), numpy.roll(b,-2,0)), 1)
b = b[0:(numpy.shape(a)[0]/2) + 1,:]

EDIT. Очевидно, что решения, использующие шаги, превосходят это, причем единственным серьезным недостатком является то, что они еще недостаточно хорошо документированы...

Ответ 6

Взгляните на: view_as_windows.

import numpy as np
from skimage.util.shape import view_as_windows
window_shape = (4, )
aa = np.arange(1000000000) # 1 billion
bb = view_as_windows(aa, window_shape)

Около 1 секунды.

Ответ 7

Я использую более обобщенную функцию, аналогичную функции @JustInTime, но применимую к ndarray

def sliding_window(x, size, overlap=0):
    step = size - overlap # in npts
    nwin = (x.shape[-1]-size)//step + 1
    shape = x.shape[:-1] + (nwin, size)
    strides = x.strides[:-1] + (step*x.strides[-1], x.strides[-1])
    return stride_tricks.as_strided(x, shape=shape, strides=strides)

Пример,

x = np.arange(10)
M.sliding_window(x, 5, 3)
Out[1]: 
array([[0, 1, 2, 3, 4],
       [2, 3, 4, 5, 6],
       [4, 5, 6, 7, 8]])


x = np.arange(10).reshape((2,5))
M.sliding_window(x, 3, 1)
Out[2]: 
array([[[0, 1, 2],
        [2, 3, 4]],

       [[5, 6, 7],
        [7, 8, 9]]])