Как избежать большого умножения матрицы в Matlab

Question

В моем коде есть две большие матрицы, которые имеют одинаковое количество столбцов и различное количество строк. Как A(20000X4000) и B(30000X4000). Оба равны 0-1.

Я должен проверить каждую строку A со всеми строками B и подсчитать количество общих 1s. Например, если A(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), а ее строки обозначаются либо как тип A, либо тип B. Я должен сравнить все строки A и B вместе и перечислить 1s. Если число 1s в каждой строке A и B больше, чем некоторые оценки, то я использовал эти строки A и B для остальной части расчета. Таким образом, мне даже не нужно хранить A и B, все, что мне нужно, это список пар индексов строк. Что-то вроде [(3,2),(3,5),...], которое показывает, что я должен использовать третий ряд A и второй ряд B, также третий из A и пятый из B и так далее.

Первое, что пришло мне в голову, было A*B', оно дает правильный результат, но практически это очень дорого и в некоторых случаях невозможно сделать это умножение.

Я преобразовал матрицы в один тип данных, и он стал немного быстрее. Редкий не помог.

Задача кажется простой, просто подсчитывая общие 1s каждой строки A и все строки B, но не так просто реализовать. Учитывая, что код должен выполнять эту задачу как 1000 раз, тогда это практически невозможно.

Любая идея, как сделать перечисление общих без умножения? (Кстати, петли тоже не помогли).

Спасибо.

Answer 1

Я не знаю, действительно ли это действительно лучше, чем у вас, потому что в нем все еще есть цикл 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 сравнений. Это огромная задача и, безусловно, займет много времени. Возможно, попробуйте использовать параллельные вычисления, если вам нужно, чтобы они были быстрее.

Answer 2

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

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 

Answer 3

Решение, которое вы пытались это оптимальное или близкое к оптимальному.

Когда я пытаюсь это, она занимает меньше минуты:

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

Если вам действительно нужно сделать, это тысячи раз, есть только два сценария, которые я могу себе представить:

1. Вам не нужно делать это часто, в этом случае просто позвольте этому запуститься, и это будет сделано завтра.
2. Вы хотите делать это часто и быстро, важно найти гораздо более быстрое решение, просто не произойдет. Если у вас нет очень полезной информации о матрицах, которые вы будете умножать.

Если вы обнаружите, что это умножение образца намного больше минуты (скажем, более 10 минут), вы, вероятно, используете неэффективную память. В этом случае попробуйте получить еще один баран.

Answer 4

Я сделал некоторый бенчмаркинг; на моей машине (i7-3770 @ 3,40 ГГц), умножая полные матрицы размером 30000 x 4000 и 4000 x 20000 занимает около 55 секунд независимо от содержимого, то же самое, что и Деннис Джахеддин. Но использование разреженных матриц может сделать вычисления быстрее, в зависимости от разреженности. Если бы я определить степень разреженности r как соотношение между числом 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