Оптимизация цикла MATLAB

Question

У меня есть матрица, matrix_logical (50000,100000) , то есть разреженная логическая матрица (много ложных значений, некоторые истинные).Я должен создать матрицу, пересечение (50000,50000) , которая для каждой пары i, j , из строк matrix_logical (50000,100000) , хранит количество столбцов, для которых строки i и j имеют оба значения "true" в качестве значения.

Вот код, который я написал:

% store in advance the nonzeros cols
for i=1:50000
    nonzeros{i} = num2cell(find(matrix_logical(i,:)));
end

intersect = zeros(50000,50000);

for i=1:49999
    a = cell2mat(nonzeros{i});
    for j=(i+1):50000
        b = cell2mat(nonzeros{j});
        intersect(i,j) = numel(intersect(a,b));
    end
end

Можно ли еще увеличить производительность?Вычисление матрицы занимает слишком много времени.Я хотел бы избежать двойного цикла во второй части кода.

matrix_logical является разреженным, но он не сохраняется как разреженный в MATLAB, поскольку в противном случае производительность становится наихудшей из возможных.

Answer 1

Поскольку запись [i, j] подсчитывает количество ненулевых элементов в поэлементном умножении строк i и j, вы можете сделать это, умножив matrix_logical на его транспонирование (вам следует преобразовать в числовой тип данных сначала, например matrix_logical = single(matrix_logical)):

inter = matrix_logical * matrix_logical';

И это работает как для разреженного, так и для полного представления.

EDIT

Для того чтобы вычислить numel(intersect(a,b))/numel(union(a,b)); (как указано в вашем комментарии), вы можете использовать тот факт, что для двух наборов a и b у вас есть

length(union(a,b)) = length(a) + length(b) - length(intersect(a,b))

Итак, вы можете сделать следующее:

unLen = sum(matrix_logical,2);
tmp = repmat(unLen, 1, length(unLen)) + repmat(unLen', length(unLen), 1);
inter = matrix_logical * matrix_logical';
inter = inter ./ (tmp-inter);

Answer 2

Развивая мой комментарий, вот функция расстояния, подходящая для pdist()

function out = distfun(xi,xj)
    out = zeros(size(xj,1),1);
    for i=1:size(xj,1)
        out(i) = sum(sum( xi & xj(i,:) )) / sum(sum( xi | xj(i,:) ));
    end

По моему опыту, sum(sum()) быстрее для логики, чем nnz(), таким образом, его появление выше.

Вам также необходимо использовать squareform() для изменения формы вывода pdist() соответствующим образом:

squareform(pdist(martrix_logical,@distfun));

Обратите внимание, что pdist() включает в себя меру расстояния 'jaccard', но на самом деле это расстояние Джакарда , а не индекс Джакарда или коэффициент , это значение, которое вы, очевидно, после.

Answer 3

Если я вас правильно понял, вы хотите логическое И строк:

intersct = zeros(50000, 50000)
for ii = 1:49999
    for jj = ii:50000
        intersct(ii, jj) = sum(matrix_logical(ii, :) & matrix_logical(jj, :));
        intersct(jj, ii) = intersct(ii, jj);
    end
end

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