r - 将列表匹配到 R 中的矩阵行

Question

“a”是一个列表，“b”是一个矩阵。

a<-list(matrix(c(0,2,0,1,0,2,0,0,1,0,0,0,0,0,2,2),4), 
        matrix(c(0,1,0,0,0,1,1,0,0,0,0,0),3),
        matrix(c(0,0,0,0,2,0,1,0,0,0,0,0,2,0,2,1,0,1,1,0),5))
b<-matrix(c(2,2,1,1,1,2,1,2,1,1,2,1,1,1,1,1,1,2,2,2,1,2,1,1),6) 

> a
[[1]]
     [,1] [,2] [,3] [,4]
[1,]    0    0    1    0
[2,]    2    2    0    0
[3,]    0    0    0    2
[4,]    1    0    0    2

[[2]]
     [,1] [,2] [,3] [,4]
[1,]    0    0    1    0
[2,]    1    0    0    0
[3,]    0    1    0    0

[[3]]
     [,1] [,2] [,3] [,4]
[1,]    0    0    0    1
[2,]    0    1    0    0
[3,]    0    0    2    1
[4,]    0    0    0    1
[5,]    2    0    2    0

> b
     [,1] [,2] [,3] [,4]
[1,]    2    1    1    2
[2,]    2    2    1    2
[3,]    1    1    1    1
[4,]    1    1    1    2
[5,]    1    2    1    1
[6,]    2    1    2    1

列表“a”中有 3 个对象。我想测试列表“a”中每个对象中的所有非零元素是否与矩阵“b”中同一行的相应位置匹配。如果匹配，则输出b匹配的行号。

比如第二个对象是

[[2]]
     [,1] [,2] [,3] [,4]
[1,]    0    0    1    0
[2,]    1    0    0    0
[3,]    0    1    0    0

我们可以看到第1行的非零数是1，位于该行的第3位，可以匹配矩阵“b”的第1-5行，第2行为1，位于该行的第1位，可以匹配矩阵“b”的第3-5行，第3行非零数为1，位于第2位这一行，它可以匹配矩阵“b”的3-4行。所以只有矩阵“b”的第3行或第4行才能匹配到该对象中的所有行，所以输出结果为“3 4”。

我的尝试代码如下:

temp<-Map(function(y) t(y), Map(function(a) 
           apply(a,1,function(x){
                 apply(b,1, function(y) identical(x[x!=0],y[x!=0]))}),a))
lapply(temp, function(a) which(apply(a,2,prod)==1))

结果如下:

[[1]]
integer(0)

[[2]]
[1] 3 4

[[3]]
[1] 6

没错。但我想知道是否有更快速的代码来处理这个问题？

Answer 1

有几列并尝试利用具有 > 1 个唯一值或没有非零值的列来减少计算量:

ff = function(a, b)
{
    i = seq_len(nrow(b))  #starting candidate matches
    for(j in seq_len(ncol(a))) {
        aj = a[, j]
        nzaj = aj[aj != 0L]
        if(!length(nzaj)) next  #if all(a[, j] == 0) save some operations
        if(sum(tabulate(nzaj) > 0L) > 1L) return(integer())  #if no unique values in a column break looping 
        i = i[b[i, j] == nzaj[[1L]]]  #update candidate matches
    }

    return(i)
}
lapply(a, function(x) ff(x, b))
#[[1]]
#integer(0)
#
#[[2]]
#[1] 3 4
#
#[[3]]
#[1] 6

用你实际尺寸的数据:

set.seed(911)
a2 = replicate(300L, matrix(sample(0:3, 20 * 5, TRUE, c(0.97, 0.01, 0.01, 0.01)), 20, 5), simplify = FALSE)
b2 = matrix(sample(1:3, 15 * 5, TRUE), 15, 5)
identical(OP(a2, b2), lapply(a2, function(x) ff(x, b2)))
#[1] TRUE
microbenchmark::microbenchmark(OP(a2, b2), lapply(a2, function(x) ff(x, b2)), times = 50)
#Unit: milliseconds
#                              expr        min         lq       mean     median         uq       max neval cld
#                        OP(a2, b2) 686.961815 730.840732 760.029859 753.790094 785.310056 863.04577    50   b
# lapply(a2, function(x) ff(x, b2))   8.110542   8.450888   9.381802   8.949924   9.872826  15.51568    50  a

OP 是:

OP = function (a, b) 
{
    temp = Map(function(y) t(y), Map(function(a) apply(a, 1, 
        function(x) {
            apply(b, 1, function(y) identical(x[x != 0], y[x != 
                0]))
        }), a))
    lapply(temp, function(x) which(apply(x, 2, prod) == 1))
}