Сдвиг строки большой матрицы по горизонтали

Question

Я ищу способ смещения строк квадратной матрицы по горизонтали. В частности, мой вопрос касается случая, когда размер матрицы очень велик, скажем, 500 * 500 или 1000 * 1000, но я приведу небольшой пример 5 * 5, чтобы прояснить это. Предположим, у нас есть следующая матрица:

 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

Я хотел бы сместить строки по горизонтали, в которых я получаю следующую матрицу, и заполнить пустые ячейки нулями:

1    7   13   19   25
2    8   14   20    0
3    9   15    0    0
4   10    0    0    0
5    0    0    0    0

Написание кода для маленькой матрицы, такой как это легко в R, но я ищу очень большие матрицы, как я указал выше. Любая помощь будет оценена.

Answer 1

В примере предлагается создать новую матрицу, чей jth столбец представляет собой jth строку оригинала, смещенную влево на j-1 места и дополненную нулями на верно, как в этом расчете с матрицей 10 000 X 10 000:

n <- 1e4
a <- matrix(seq_len(n^2), n, byrow=TRUE)
system.time({
  b <- matrix(sapply(seq_len(nrow(a)), function(i) c(a[i,i:ncol(a)], rep(0, i-1))), n, n)
})

user  system elapsed 
0.97    0.00    0.99 

(Это использует один поток и отражает типичное завершение многих тестовых прогонов.) Один второй для матрицы с 100 000 000 записей не плохо. Хотя это большой объем оперативной памяти, поэтому вы можете изменить код, если вход является разреженной матрицей, чтобы он тоже выводил разреженную матрицу.

---

Размышляя над этим, мне пришло в голову, что избегать конкатенации c и просто копировать на месте должно быть быстрее, предполагая, что можно очень быстро инициализировать матрицу нулей. Оказывается, это так (и код еще проще):

system.time({
  b <- matrix(0, nrow(a), ncol(a))
  for (i in seq_len(nrow(a))) b[1:(n+1-i), i] <- a[i, i:ncol(a)]
})

user  system elapsed 
0.62    0.00    0.62 

Это примерно на 50% быстрее. Поскольку издержки l oop будут относительно небольшими, а тело l oop - (предположительно) оптимизированной векторной копии, вряд ли существует значительно более быстрое однопоточное решение.