Рисование случайного ненулевого элемента из разреженной матрицы

У меня есть разреженная логическая матрица, которая довольно велика. Я хотел бы извлечь из него случайные ненулевые элементы без сохранения всех ненулевых элементов в отдельном векторе (например, с помощью команды find). Есть простой способ сделать это?Рисование случайного ненулевого элемента из разреженной матрицы

В настоящее время я реализую выборку отбраковки, которая рисует случайный элемент и проверяет, является ли это ненулевым или нет. Но это неэффективно, когда отношение ненулевых элементов невелико.

источник

2012-02-14 user1210230

Я думаю, что поиск довольно оптимизирован для разреженных матриц, если это то, о чем вы беспокоитесь. –

Я беспокоюсь о памяти не время работы. Однако даже с точки зрения времени выполнения, если вы хотите выбрать только несколько элементов, найти не так эффективно. – user1210230

Использование 'nonzeros' должно быть немного более эффективным с точки зрения памяти, чем' find', так как вы не храните указатели строк и столбцов. –

find - это стандартный интерфейс для получения ненулевых элементов в разреженной матрице. Посмотрите здесь http://www.mathworks.se/help/techdoc/math/f6-9182.html#f6-13040

[i,j,s] = find(S)

находка возвращает индексы строк ненулевых значений в векторе я, индексы столбцов в векторе у, а сами ненулевые значения в векторе с.

Не нужно приобретать. Просто выберите случайный индекс в i, j.

источник

2012-02-15 00:07:51

Возможно, моя точка зрения была недостаточно ясной. Я НЕ хочу использовать find, потому что тогда мне нужно хранить индексы в отдельном векторе (i и j в вашем примере), который будет очень интенсивным для памяти. Сравните его с самой разреженной матрицей, которая является разреженной логической матрицей. – user1210230

это было ясно, но нет другого пути. –

Редкая логическая матрица - не очень практическое представление ваших данных, если вы хотите выбрать случайные местоположения. Отбор проб и find - это только два способа, которые имеют смысл для меня. Вот как вы можете сделать их эффективно (если вы хотите, чтобы получить 4 случайные места):

%# using find 
idx = find(S); 
%# draw 4 without replacement 
fourRandomIdx = idx(randperm(length(idx),4)); 
%# draw 4 with replacement 
fourRandomIdx = idx(randi(1,length(idx),4)); 
%# get row, column values 
[row,col] = ind2sub(size(S),fourRandomIdx); 



%# using rejection sampling 
density = nnz(S)/prod(size(S)); 
%# estimate how many samples you need to get at least 4 hits 
%# and multiply by 2 (or 3) 
n = ceil(1/(1-(1-density)^4)) * 2; 
%# random indices w/ replacement 
randIdx = randi(1,n,prod(size(S))); 
%# identify the first four non-zero elements 
[row,col] = find(S(randIdx),4,'first');

источник

2012-02-15 02:53:22 Jonas

матрица пХт с NNZ ненулевых элементов требует NNZ + п + 1 целых чисел для хранения местоположения его ненулевым записей. Для логической матрицы нет необходимости хранить значение ненулевых записей: все они истинны. Соответственно, вам лучше всего преобразовать вашу логическую разреженную матрицу в список линейных индексов ненулевых записей вместе с n и m, для чего требуется только nnz + 2 целых числа хранения. Из них (и ind2sub) вы можете легко восстановить индексы, соответствующие любой ненулевой записи, которую вы произвольно выбираете, используя randi в диапазоне 1..nnz

источник

2012-02-16 05:18:16 lsfinn

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

Можете уточнить цель? В исходном посте вы указали, что хотите нарисовать «случайные ненулевые элементы»; тем не менее, в вашем комментарии кажется, что вы также хотите рисовать нулевые записи. Не могли бы вы уточнить? I.e., когда вы делаете произвольную ничью из матрицы, вы рисуете из всех записей или только некоторые (и, если да, то какие)? Когда вы рисуете, что вы хотите (например, индексы, индексы и значение элемента или ...)? Наконец, приходит ли матрица к вам как к случайной матрице или она построена из чего-то другого, так что ее представление находится под вашим контролем? – lsfinn

Представляя записи в формате 3 столбца, (i, j, value), вы можете просто выбрать элементы из списка. Для того, чтобы получить это, вы можете использовать свой оригинальный метод для создания разреженной матрицы (то есть предшественник sparse()), или использовать find команды, а-ля [i,j,s] = find(S);

Если вам не нужны записи, и вам кажется нет, вы можете просто извлечь i и j.

Если по какой-либо причине ваша матрица массивна и ограничения в оперативной памяти серьезны, вы можете просто разделить матрицу на области и позволить вероятности выбора данной подматрицы пропорционально числу ненулевых элементов (с использованием nnz) в этой подматрице. Вы можете зайти так далеко, чтобы разделить матрицу на отдельные столбцы, а остальная часть вычисления тривиальна. NB: применяя sum к матрице, вы можете получить количество столбцов (при условии, что ваши записи равны 1 с).

Таким образом, вам не нужно даже беспокоиться об отбраковке (это кажется бессмысленным для меня в этом случае, поскольку Matlab знает, где все ненулевые записи).

источник

2012-02-16 05:30:31 Iterator

Рисование случайного ненулевого элемента из разреженной матрицы

ответ

Смежные вопросы