Найти редкую строку в матрице - PullRequest
Новая
       15

Найти редкую строку в матрице

0 голосов
/ 06 ноября 2018

У меня есть матрица в MATLAB, и я хочу определить, какая строка содержит наибольшее количество нулей. То есть я хочу найти самую редкую строку (и столбец) в матрице. Любой способ сделать это более эффективно, чем зацикливание с mat(sum(mat==0,i)==i,:)? Или это предпочтительный метод?

Я использую это для реализации LU-факторизации с использованием «эвристики упорядочения минимальной степени» для решения линейной системы.

Ответы [ 2 ]

0 голосов
/ 06 ноября 2018

Я не знаю функции, которая могла бы выполнять это построчно векторизованным способом (то есть до тех пор, пока я не увидел гениальное решение Рэйриенга ), но зацикливаясь на nnz должно быть довольно быстро Петли больше не очень медленные, так как новый двигатель вышел с R2016a. 

tmp = zeros(size(mat,1),1);
for ii = 1:size(mat,1)
    tmp(ii) = nnz(mat(ii,:));
end

В качестве примечания: я бы поспорил против использования i в качестве переменной , поскольку оно обозначает мнимую единицу .

0 голосов
/ 06 ноября 2018

Чтобы найти «редкую» строку, если я правильно ее интерпретирую, это означает, что вы хотите найти строку с наибольшим количеством нулей. Вы можете использовать sum в векторизованном виде в сочетании с max, чтобы выяснить это: 

[~, row] = max(sum(mat == 0, 2));

mat == 0 преобразует всю вашу матрицу в true/false так, что true будет нулевым значением, а false в противном случае, тогда мы используем sum и суммируем по каждой строке индивидуально. Это уменьшит проблему, так что каждый элемент подсчитывает, сколько нулевых элементов мы встретили в строке. Используя второй вывод max для этого результата, row будет, таким образом, содержать любую строку, имеющую наибольшее количество нулей. Мы игнорируем первый вывод, так как он выведет фактическое наибольшее значение, которое нас не волнует, учитывая вашу проблему.

Если вас беспокоит скорость, вы можете выполнить умножение матрицы на вектор с преобразованной матрицей true/false с вектором ones. Таким образом, он будет выполнять сумму для вас, и, таким образом, матрица повышается до double точности: 

[~, row] = max((mat == 0)*ones(size(mat, 2), 1)));

Незначительная нота

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

...