确定包含特定项的矩阵行子集的快速方法

Question

我正在寻找一个解决以下问题的时间效率高的解决方案，它利用了我想多次执行某个操作的事实。我在下面实现了两种方法，我发现其中一种速度要快得多。我想知道这两种方法是否有更有效的替代方法

输入：用非负整数（0<；=每个整数<；=b）填充m*n维度的矩阵矩阵矩阵。还给定p个非负整数q₁，q₂，…，q_p（每个<；=b）和向量v₁，v₂，…，v_p。v_j的每个条目包含mat的d行索引

我感兴趣的是m、p和d大（~10⁶），n小（~10），b小（~100）的情况

输出：对于每对（v_j，q_j），返回v_j[0]、v_j[1]、…、v_j[d-1]中包含整数q_j的mat行的子列表

我的方法：因为p可能很大，所以我对mat进行了预处理，以确定每行是否包含0到b之间的任何数字。然后，我通过向量v_j来确定由其条目定义的mat行是否包含q_j。我尝试了两种不同的方法来存储mat的每一行是否包含0和b之间的任何整数。令我惊讶的是，我发现方法1的执行速度明显快于方法2

问题：我想知道是否有更好的（实用的）方法来预处理mat，以使每对（v_j，q_j）的操作尽可能快

编辑：将tmp变量定义为tmp=isPresent[qs[j]]并遍历tmp的元素可以得到更快的解决方案，但我希望我可以更快地完成某些事情

注：结果中元素的顺序并不重要

# Python code

import random
import numpy
import time

m = 1000000 # number of rows of mat
n = 10 # number of columns of mat
b = 255 # upper bound on entries of mat
d = 10000 # dimension of vec (containing row indices of mat)
p = 100 # number of vecs

# random specification of mat
# mat, vec, and q will be inputs from another part of the project
mat = []
for i in range(m):
    tmp = (numpy.random.permutation(b+1))[0:n]
    mat.append(tmp)

# random specification of vec and q
vecs = []
qs = []
for i in range(p):
    qs.append(random.randrange(0,b+1,1))
    vecs.append((numpy.random.permutation(m))[0:d])


# METHOD 1

# store the rows where each integer occurs
# not too worried about time taken by this step
isPresent = [[False]*m for i in range(b+1)]
for i in range(m):
    for j in mat[i]:
        isPresent[j][i] = True

# mainly care about reducing time from hereon
time1 = 0.0
for j in range(p):
    st1 = time.time()
    result1 = []
    for i in vecs[j]:
        if isPresent[qs[j]][i]:
            result1.append(i)
    time1 += time.time() - st1


# METHOD 2

# store the rows where each integer occurs
# not too worried about time taken by this step
isPresent = [[False]*(b+1) for i in range(m)]
for i in range(m):
    for j in mat[i]:
        isPresent[i][j] = True

# mainly care about reducing time from hereon
time2 = 0.0
for j in range(p):
    st2 = time.time()
    result2 = []
    for i in vecs[j]:
        if isPresent[i][qs[j]]:
            result2.append(i)
    time2 += time.time() - st2


print('time1: ',time1,'  time2: ',time2)

注意：我在笔记本电脑上观察时间1=0.46秒和时间2=0.69秒

Answer 1

TL；DR:是的，有一种更好的方法可以使用numpy计算。但是，请注意，有一种2D随机内存间接模式，通常速度较慢，并且很难优化

有用信息： 随机内存访问速度很慢。事实上，处理器很难预测要获取的内存地址，从而减少内存的延迟。只要数据适合缓存并多次重复使用，这就不算太糟糕。在巨大内存区域上进行的随机内存访问速度要慢得多，应该像瘟疫一样避免（如果可能的话）

分析： 这两种方法都在执行表达式isPresent[qs[j]][i]和isPresent[i][qs[j]]时执行随机内存间接寻址。 这样的间接行动是缓慢的。但是方法2的速度较慢，因为提取地址之间的平均距离往往比方法1大得多，从而导致一种称为缓存抖动的效果

更快的解决方案：Numpy可用于显著提高第一种方法的性能（得益于“矢量化”本机方法）。 事实上，这种方法使用普通的python循环，这些循环通常非常慢，并且多次重新计算isPresent[qs[j]]。 以下是更快的实现：

# Assume vecs is a list of np.arrray rather than a list of list

isPresent = [numpy.array([False]*m) for i in range(b+1)]
for i in range(m):
    for j in mat[i]:
        isPresent[j][i] = True

time3 = 0.0
for j in range(p):
    st3 = time.time()
    tmp = isPresent[qs[j]]
    result3 = numpy.extract(tmp[vecs[j]], vecs[j])
    time3 += time.time() - st3

绩效结果：

time1:  0.165357
time2:  0.309095
time3:  0.007201

新版本比第一种方法快23倍，比第二种方法快43倍

注意，通过并行计算j循环，可以显著加快这一速度，但这要复杂一些