Запишите вектор в матрицу, начиная с диагонали

Question

У меня есть длина вектора n и матрица mxm. Обычно m >> n (m намного больше, чем n). Мне нужно многократно записать вектор в матрицу, начиная с диагонали. Например:

vector v = [v_1, v_2, v_3] с 4x4 нулевой матрицей приводит к:

v_1,  v_2,  v_3,  0
0,    v_1,  v_2,  v_3
0,    0,    v_1,  v_2
0,    0,    0,    v_1

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

Answer 1

Одна из идей для ее решения заключается в том, чтобы проложить соответствующее количество нулей с обеих сторон и получить вдоль него скользящие окна длиной m.Мы можем использовать np.lib.stride_tricks.as_strided на основе scikit-image's view_as_windows, чтобы получить раздвижные окна. Больше информации об использовании as_strided на основе view_as_windows.

from skimage.util.shape import view_as_windows

def extend2D(a, m):
    # Create zeros padded version
    p1 = np.zeros(m-1,dtype=a.dtype)
    p2 = np.zeros(m-len(a),dtype=a.dtype)    
    b = np.concatenate((p1,a,p2))

    # Get sliding windows along it of lengths `m` and finally flip rows
    return view_as_windows(b,m)[::-1]

Результатом будет просто скольжение оконных представлений в дополненную нулями версию ввода.Таким образом, если вам нужно, чтобы выход имел собственное пространство памяти, добавьте к выводу .copy().

Примеры выполнения -

In [45]: a
Out[45]: array([5, 8, 6])

In [46]: extend2D(a, m=4)
Out[46]: 
array([[5, 8, 6, 0],
       [0, 5, 8, 6],
       [0, 0, 5, 8],
       [0, 0, 0, 5]])

In [47]: extend2D(a, m=5)
Out[47]: 
array([[5, 8, 6, 0, 0],
       [0, 5, 8, 6, 0],
       [0, 0, 5, 8, 6],
       [0, 0, 0, 5, 8],
       [0, 0, 0, 0, 5]])

Optimization-I

Если вы хотите испачкать руки с помощью strided-indexing, придерживаясь NumPy с помощью np.lib.stride_tricks.as_strided, и в процессе избегайте этого переворачивания на последнем шаге предыдущего подхода -

def extend2D_v2(a, m):
    p1 = np.zeros(m-1,dtype=a.dtype)
    p2 = np.zeros(m-len(a),dtype=a.dtype)    
    b = np.concatenate((p1,a,p2))
    s = b.strides[0]
    return np.lib.stride_tricks.as_strided(b[m-1:],shape=(m,m),strides=(-s,s))

Optimization-II

Оптимизируя далее, мы можем инициализировать массив нулей и затем назначить вход в него -

def extend2D_v3(a, m):
    b = np.zeros(2*m-1,dtype=a.dtype)
    b[m-1:m-1+len(a)] = a
    s = b.strides[0]
    return np.lib.stride_tricks.as_strided(b[m-1:],shape=(m,m),strides=(-s,s))

Синхронизация с n=100 и m=10000 массив случайных данных -

In [97]: np.random.seed(0)
    ...: a = np.random.randint(1,9,(100))

In [98]: %timeit extend2D(a, m=10000)
    ...: %timeit extend2D_v2(a, m=10000)
    ...: %timeit extend2D_v3(a, m=10000)
10000 loops, best of 3: 51.3 µs per loop
10000 loops, best of 3: 19.6 µs per loop
100000 loops, best of 3: 12.6 µs per loop

Answer 2

Вот аналогичный ответ на Divakar's , но только с NumPy.Он дополняет заданный вектор нулями, а затем создает представление из этого буфера:

import numpy as np

def view_into_diagonals(v, m):
    # Add zeros before and after the vector
    v_pad = np.pad(v, [(m - 1, m - len(v))], mode='constant')
    # Current stride
    s, = v_pad.strides
    # Offset from which the first row starts
    offset = s * (m - 1)
    # Make ndarray
    view = np.ndarray(shape=(m, m),
                      dtype=v_pad.dtype,
                      buffer=v_pad.data,
                      offset=offset,
                      # Each column moves one forward, each row moves one backwards
                      strides=(-s, s))
    # Probably better not write to it
    view.flags.writeable = False
    return view

print(view_into_diagonals([1, 2, 3], 6))
# [[1 2 3 0 0 0]
#  [0 1 2 3 0 0]
#  [0 0 1 2 3 0]
#  [0 0 0 1 2 3]
#  [0 0 0 0 1 2]
#  [0 0 0 0 0 1]]

Answer 3

Чек numpy.eye . Это работает для вас?

v = [1,2,3]
N = 5
M = 10
arr = np.sum(np.eye(N, k=i, M=10) * j for i, j in enumerate(v))
arr
>>array([[1., 2., 3., 0., 0., 0., 0., 0., 0., 0.],
   [0., 1., 2., 3., 0., 0., 0., 0., 0., 0.],
   [0., 0., 1., 2., 3., 0., 0., 0., 0., 0.],
   [0., 0., 0., 1., 2., 3., 0., 0., 0., 0.],
   [0., 0., 0., 0., 1., 2., 3., 0., 0., 0.]])

Редактировать (благодаря предложению hpaulj): Если ваша матрица очень большая и имеет множество нулей, вы можете использовать разреженные матрицы

from scipy.sparse import diags
arr = diags(v,offsets=[0,1,2],shape=(N,M))
print(arr.A)
>>array([[1., 2., 3., 0., 0., 0., 0., 0., 0., 0.],
   [0., 1., 2., 3., 0., 0., 0., 0., 0., 0.],
   [0., 0., 1., 2., 3., 0., 0., 0., 0., 0.],
   [0., 0., 0., 1., 2., 3., 0., 0., 0., 0.],
   [0., 0., 0., 0., 1., 2., 3., 0., 0., 0.]])