Построение эффективного массива Numpy 2D из массива 1D
У меня есть такой массив:
A = array([1,2,3,4,5,6,7,8,9,10])
И я пытаюсь получить массив, как это:
B = array([[1,2,3],
[2,3,4],
[3,4,5],
[4,5,6]])
Где каждая строка (с фиксированной произвольной шириной) сдвинута на единицу. Массив A имеет длину 10 тыс. Записей, и я пытаюсь найти эффективный способ сделать это в Numpy. В настоящее время я использую vstack и цикл for, который работает медленно. Есть ли более быстрый способ?
Редактировать:
width = 3 # fixed arbitrary width
length = 10000 # length of A which I wish to use
B = A[0:length + 1]
for i in range (1, length):
B = np.vstack((B, A[i, i + width + 1]))
7 ответов
На самом деле, есть еще более эффективный способ сделать это... Недостаток использования vstack и т.д., это то, что вы делаете копию массива.
Кстати, это фактически совпадает с ответом @Paul, но я публикую это только для того, чтобы объяснить что-то более подробно...
Есть способ сделать это с помощью просто просмотров, чтобы не дублировать память.
Я напрямую позаимствовал это из поста Эрика Ригторпа для обсуждения с тупым предметом, который, в свою очередь, позаимствовал его из " Узкого места" Кита Гудмана (что весьма полезно!).
Основная хитрость заключается в том, чтобы напрямую манипулировать шагами массива(для одномерных массивов):
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's__array_interface__, что позволяет произвольным классам описывать буфер памяти как пустой массив.)
Итак, все, что мы сделали, это сделали так, чтобы шаг вперед на один элемент (8 байт в случае 64-битного массива) вдоль одной оси, а также только шаг на 8 байтов вперед вдоль другой оси.
Другими словами, в случае размера "окна" 3, массив имеет форму (whatever, 3), но вместо полного шага 3 * x.itemsize для второго измерения он только продвигает один элемент вперед, эффективно превращая строки нового массива в представление "движущегося окна" в исходный массив.
(Это также означает, что x.shape[0] * x.shape[1] не будет таким же как x.size для вашего нового массива.)
В любом случае, надеюсь, это немного прояснит ситуацию.
Это решение неэффективно реализовано в цикле python, поскольку оно поставляется со всеми видами проверки типов, которых лучше избегать при работе с массивами numpy. Если ваш массив исключительно высокий, вы заметите большую скорость с этим:
newshape = (4,3)
newstrides = (A.itemsize, A.itemsize)
B = numpy.lib.stride_tricks.as_strided(A, shape=newshape, strides=newstrides)
Это дает представление о массиве A. Если вы хотите новый массив, который вы можете редактировать, сделайте то же самое, но с .copy() в конце.
Детали по шагам:
newstrides кортеж в этом случае будет равен (4,4), потому что массив содержит 4-байтовые элементы, и вы хотите продолжить пошаговое выполнение ваших данных в пошаговых шагах в i-измерении. Второе значение "4" относится к шагам в j-измерении (в обычном массиве 4x4 это будет 16). Потому что в этом случае вы хотите также увеличить чтение из буфера с помощью 4-байтовых шагов в j-измерении.
Джо дает хорошее, подробное описание и делает вещи кристально ясными, когда говорит, что весь этот трюк состоит в одновременном изменении шагов и формы.
Какой подход вы используете?
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 мкс для второго.
Просто дальше идти с ответом @Joe General
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]]
Далее обобщить для двумерного случая, т.е. использовать его для извлечения патчей из изображения
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]]]
Я думаю, что это может быть быстрее, чем зацикливание, когда ширина фиксируется на небольшом числе...
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,:]
РЕДАКТИРОВАТЬ Очевидно, что решения, использующие шаги, превосходят это, с единственным серьезным недостатком, что они еще не хорошо документированы...
Взгляните на: 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 секунды.
Я использую более обобщенную функцию, похожую на функцию @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]]])