2

我的代码中有两个大矩阵，它们具有相同的列数和不同的行数。喜欢A(20000X4000)和B(30000X4000)。两者都是 0-1 稀疏的。

我应该检查 A 的每一行和 B 的所有行，并计算常见 1 的数量。例如 ifA(1,:)=[0 1 0 1 1]和B([1 2],:)=[1 1 1 1 1;0 0 0 1 1]，我需要得到结果3和2。

假设有一个大的 0-1 矩阵C(50000X4000)，并且它的行被标记为 typeA或 type B。我应该比较所有行A和B一起并枚举1。如果 A 和 B 的每一行中 1 的数量大于某些界限，那么我将使用 A 和 B 的那些行进行其余的计算。所以，我什至不需要存储Aand B，我需要的只是行索引对的列表。类似的东西[(3,2),(3,5),...]表明我应该使用的第三行A和第二行，以及B第三行A和第五行B，依此类推。

我想到的第一件事是A*B'，它给出了正确的结果，但实际上它非常昂贵，在某些情况下不可能进行这种乘法。

我将矩阵转换为单一数据类型，它变得有点快。稀疏没有帮助。

这个任务看起来很简单，只计算 的每一行A和所有行的常见 1 B，但实现起来并不容易。考虑到代码应该像 1000 次一样完成这个任务，那么这实际上是不可能的。

知道如何在不乘法的情况下枚举常见的吗？（顺便说一句，循环也没有帮助）。

谢谢。

4

4 回答 4

2

我不知道这是否真的比你所拥有的更好，因为它仍然有一个 for 循环，但如果有人能弄清楚如何删除那个 for 循环，你应该很高兴。

%  create temp data
A = rand(20000,4000) < 0.5;
B = rand(30000,4000) < 0.5;
counts = zeros(size(A,1),size(B,1),'uint8');
for i = 1:size(A,1)
    counts(i,:) = sum(bsxfun(@eq,A(i,:),B),2);
end

无论哪种方式，该过程都将花费很长时间，因为您要比较 30000 行和每行 4000 个元素、20000 次或近似2.4e+12比较。这是一项艰巨的任务，而且肯定需要很长时间。如果您需要更快，可以尝试使用并行计算。

于 2013-12-04T17:16:50.367 回答
1

我做了一些基准测试；在我的机器（i7-3770 @ 3.40GHz）上，无论内容如何，​​将大小为 30000 x 4000 和 4000 x 20000 的完整矩阵相乘大约需要 55 秒，这与 Dennis Jaheruddin 发现的相同。但是使用稀疏矩阵可以使计算更快，这取决于稀疏性。如果我将稀疏度定义r为 s 的数量与矩阵元素的比率1，我会得到以下结果：

r      time / s 
0.001   0.07
0.002   0.3
0.005   2.1
0.01    8.3
0.02   25

以下是用于确定这些数字的代码：

m = 20000;
n = 4000;
o = 30000;

r = 0.001;

N = round(r * m * n);
A = sparse(randi(m, N, 1), randi(n, N, 1), 1, m, n);

N = round(r * n * o);
B = sparse(randi(o, N, 1), randi(n, N, 1), 1, o, n);

tic
C = A * B';
toc
于 2013-12-09T20:52:03.610 回答
0

如果整个矩阵的乘法不能完成，一个想法是一次处理一个垂直条纹。对于每个条带，您计算所需的结果，并将其与前面的条带累加：

A = double(rand(5,300)<.5); %// random data
B = double(rand(4,300)<.5); %// random data

S = 10; %// stripe size
result = zeros(size(A,1),size(B,1)); %// initialize to 0
for s = 1:10:size(A,2) %// each vertical stripe, of width S
    ind = s+(0:S-1);
    result = result +  A(:,ind)*(B(:,ind)).';
end

查看：

>> result

result =

    73    72    62    72
    84    70    79    71
    83    84    76    77
    77    80    77    74
    71    71    70    74

>> A*B.'

ans =

    73    72    62    72
    84    70    79    71
    83    84    76    77
    77    80    77    74
    71    71    70    74
于 2013-12-04T23:20:09.963 回答
0

您尝试的解决方案是最优的或接近最优的。

当我尝试这个时，不到一分钟：

A = round(rand(30000,4000));
B = round(rand(20000,4000));
tic,A*B';toc;

如果你真的需要这样做数千次，我只能想象两种情况：

  1. 你不需要经常这样做，在这种情况下让它运行，明天就会完成
  2. 您想经常这样做并加快速度，找到更快的解决方案根本不会发生。除非你有一些关于你将要相乘的矩阵的非常有用的信息。

如果你发现这个样本乘法超过一分钟（比如超过 10 分钟），你可能正在低效地使用内存。在这种情况下，尝试获得更多的内存。

于 2013-12-09T20:17:53.823 回答