A*******e
发帖数: 284 | 1 R新手请高人指点。
现在有一个很大的matrix，比如讲5000*3000，我需要寻找到这个matrix中那些相邻的
值的sum最小，然后给出坐标。相邻我指的是一个16*9的matrix。
我能想到的就是把这个matrix subset成各种可能（肯定是很大的数）16*9的小matrix
，然后求sum 给坐标。但这个效率肯定很低。
然后这个大的matrix还有接近上万个。请问有什么高效的方法。 | w********m
发帖数: 1137 | 2 row，column排序的话，可以二分。不过听你的描述，好像只有暴力了吧，O（M*N).
用C写扩展，可能会快些吧。 | k*******a
发帖数: 772 | 3 ## function to find sums of all subset matrix: k_row * k_col
move_sum <- function(x, k) diff(c(0, cumsum(x)), k)
move_sum_mat <- function(mat, k_row, k_col) {
new_mat <- t(apply(mat, 1, move_sum, k = k_col))
new_mat <- apply(new_mat, 2, move_sum, k = k_row)
new_mat
}
## test matrix
mat <- matrix(sample(1:10, 100, replace=T), nrow=10, ncol=10)
## get sums for all subset matrix with 4 rows and 9 cols
mymat <- move_sum_mat(mat, 4, 9)
## find starting row and col for max sub matrix
which(mymat == max(mymat), arr.ind = T)
## large matrix, speed seems to be ok, about 5 seconds
mat_big <- matrix(rnorm(5000*3000), nrow=5000, ncol=3000)
mat_big_sum <- move_sum_mat(mat_big, 16, 9)
which(mat_big_sum == max(mat_big_sum), arr.ind = T) | v*******e
发帖数: 11604 | 4
这个可以用C写。而且一部分加法可以复用，比如坐标（i,j)的值的可以从(i-1,j)值的
来，只要做16个加法和16个减法。
【在 w********m 的大作中提到】
: row，column排序的话，可以二分。不过听你的描述，好像只有暴力了吧，O（M*N).
: 用C写扩展，可能会快些吧。
| g******2
发帖数: 234 | 5 +1 to kirklanda,
minor issue: the k_row and k_col probably should be swapped. and the t()
does not seem to be necessary. | k*******a
发帖数: 772 | 6 You are right, k_row and k_col should be swapped
t() seems to be necessary since it looks like when I apply on margin 1, the
result is rotated
【在 g******2 的大作中提到】
: +1 to kirklanda,
: minor issue: the k_row and k_col probably should be swapped. and the t()
: does not seem to be necessary.
| s*****n
发帖数: 134 | 7 这个是图像处理里常用的二维卷积运算。 MATLAB里有conv2 function可以直接调用。 http://rosettacode.org/wiki/Image_convolution
如果是自己再造轮子的话可以考虑用快速傅立叶变换。空间域上的卷积等于频域上的点
乘。不过麻烦的是要把原始矩阵加上零凑成2的整数次方，才好用快速傅立叶变换。
另一个思路就是用移动窗口的中心坐标为key，对相同key的cell做加法reduce，还没试
过在R里实现。
matrix
【在 A*******e 的大作中提到】
: R新手请高人指点。
: 现在有一个很大的matrix，比如讲5000*3000，我需要寻找到这个matrix中那些相邻的
: 值的sum最小，然后给出坐标。相邻我指的是一个16*9的matrix。
: 我能想到的就是把这个matrix subset成各种可能（肯定是很大的数）16*9的小matrix
: ，然后求sum 给坐标。但这个效率肯定很低。
: 然后这个大的matrix还有接近上万个。请问有什么高效的方法。
| v*******e
发帖数: 11604 | 8
。 http://rosettacode.org/wiki/Image_convolution
你说得对。pad到横竖都是2的整数次像素数。我其实想到过用是卷积，只是好久没碰EE
的东西，直觉傅立叶变换和直接运算一样快，忘记了可以用快速傅立叶变换。
【在 s*****n 的大作中提到】
: 这个是图像处理里常用的二维卷积运算。 MATLAB里有conv2 function可以直接调用。 http://rosettacode.org/wiki/Image_convolution
: 如果是自己再造轮子的话可以考虑用快速傅立叶变换。空间域上的卷积等于频域上的点
: 乘。不过麻烦的是要把原始矩阵加上零凑成2的整数次方，才好用快速傅立叶变换。
: 另一个思路就是用移动窗口的中心坐标为key，对相同key的cell做加法reduce，还没试
: 过在R里实现。
:
: matrix
| g******2
发帖数: 234 | 9 Kirklanda's code is fast enough to handle lz's case... |
|
