Ускорение поиска совокупного вхождения элементов

Я пытаюсь улучшить производительность своего кода. Код в основном вычисляет значение L_total (1x2640) и делает это, извлекая данные из другой переменной с именем L_CN (1320x6). У меня также есть матрица colindexes (2640x3), в которой хранятся значения строк для просмотра в L_CN.

Итак, как это происходит, код смотрит на colindexes, чтобы получить данные строки. Скажем, colindexes имеет следующую форму:

55    65    75
68    75    85
...

Программа рассчитает L_total(1), используя L_CN(55,1) + L_CN(65,1) + L_CN(75,1). Здесь первые индексы относятся к номерам строк, полученным из матрицы colindexes. Вторые индексы представляют количество вхождений этих номеров строк на данный момент. Следовательно, когда мы посчитаем L_total(2), будет L_CN(68,1) + L_CN(75,2) + L_CN(85,1). Здесь L_CN(75,2) произошло, потому что L_CN(75,1) использовалось раньше.

Для вычисления всей матрицы L_total хорошо работает следующий код. Он сохраняет количество вхождений для каждого индекса, увеличивая соответствующий индекс в переменной с именем list(2640x1) и, таким образом, вычисляет L_total. Это происходит за 0,023715 секунды. (Обратите внимание, что n это 2640 ниже)

for i=1:n
     list(colindexes(i,:)) = list(colindexes(i,:)) + 1;
     L_total(i) = sum(diag(L_CN(colindexes(i,:),list(colindexes(i,:)))));
end

Проблема в том, что я буду запускать эту часть кода снова и снова, может быть, миллион раз. Это часть большой симуляции. Следовательно, даже небольшая часть увеличения производительности — это то, что мне нужно. Во-первых, я подумал, что избавление от цикла for послужит для этой цели, и переключил код на следующий — получая небольшую помощь из этой темы: Вектор числа вхождений:

list_col = reshape(colindexes',1,[]);
occurrence = sum(triu(bsxfun(@eq,list_col,list_col.')));
list = reshape(occurrence,3,[])';
straight_index = colindexes + (list - 1)*k;
L_total = sum(L_CN(straight_index),2)';

Этот код также выполняет работу для list_col (1x7920), occurrence (1x7920), list (2640x3) и straight_index (2640x3). Однако, вопреки моим ожиданиям, это занимает 0,062168 секунды, что примерно в три раза хуже, чем реализация цикла for. 0,05217 секунды этой операции приходится на вторую строку, где формируется матрица вхождений. С такими размерами массива, как у меня, действительно неэффективно находить такие вхождения.

Вопрос в том, с циклом for или без него, как я могу увеличить производительность этого кода? Метод векторизации кажется хорошим, если только я смогу найти способ быстрее вычислить матрицу вхождений. Как я уже сказал, эта часть кода будет запускаться много раз, поэтому приветствуется любой процент увеличения производительности.

Благодарю вас!

Дополнительная информация: colindexes представляют собой большую матрицу размером 1320x2640. Вместо того, чтобы хранить всю эту матрицу, я сохраняю только расположение строк «1» в этой матрице в colindexes. Остальное ноль. Таким образом, colindexes, который я указал в вопросе, означает, что в 1-м столбце 55-й строки и во 2-м столбце 85-й строки есть «1» ... Таким образом, минимальный, максимальный диапазон составляет 1,1320. В каждом столбце всего 3 единицы, поэтому его размер 2640x3. Это, конечно, справочная информация, как она формируется. Если это поможет, количество вхождений для каждого значения в colindexes также одинаковое, то есть 6.

Итак, для матрицы A = [1 0 0 1; 0 1 1 0] colindexes равно [1; 2; 2; 1].


person etua    schedule 16.03.2014    source источник
comment
2640x1. Позвольте мне отредактировать ОП.   -  person etua    schedule 16.03.2014
comment
n будет? Извините, если я пропустил это.   -  person Divakar    schedule 16.03.2014
comment
Все в порядке, это огромный код, и я публикую его часть. Возможно, я пропустил указание одной или двух переменных. n равно 2640, я его тоже отредактирую.   -  person etua    schedule 16.03.2014
comment
Не могли бы вы опубликовать типичные значения и, возможно, минимальные и максимальные значения L_CN, list и colindexes?   -  person Divakar    schedule 16.03.2014
comment
colindexes представляют собой большую матрицу размером 1320x2640. Вместо того, чтобы хранить всю эту матрицу, я сохраняю только расположение строк «1» в этой матрице в colindexes. Остальное ноль. Таким образом, colindexes, указанный в вопросе, означает, что в 1-м столбце 55-й строки и во 2-м столбце 85-й строки есть «1» ... Таким образом, минимальный, максимальный диапазон составляет 1,1320. В каждом столбце всего 3 единицы, поэтому его размер 2640x3. Это, конечно, справочная информация, как она формируется. Если это поможет, количество вхождений для каждого значения в colindexes также одинаковое, то есть 6.   -  person etua    schedule 16.03.2014
comment
Не могли бы вы запустить это внутри этого цикла forstd(diag(L_CN(colindexes(i,:),list(colindexes(i,:))))) и сообщить нам, получаете ли вы какое-либо ненулевое или любое значение, которое не очень мало (порядка E-16)?   -  person Divakar    schedule 16.03.2014
comment
Не сразу, но после некоторой итерации, поскольку L_CN продолжает обновляться, появляется куча значений NaN, если я заменяю sum на std. Я не вижу смысла, к которому вы прибегаете со стандартным отклонением. Можете ли вы объяснить больше?   -  person etua    schedule 16.03.2014
comment
Вам не нужно заменять sum на std, просто добавьте этот расчет std выше или ниже строки, где вычисляется L_total. Я пробовал с некоторыми случайными числами, и все значения diag одинаковы, поэтому я подумал, что мы можем избежать суммирования.   -  person Divakar    schedule 16.03.2014
comment
Ага, понятно. Ну, я также получаю стандартные значения около 2,35–1,2. Так что они не такие уж и маленькие.   -  person etua    schedule 16.03.2014
comment
Насколько я понимаю, если бы вы использовали настоящую матрицу sparse вместо собственной реализации, это было бы так же просто, как sum(data, 1);   -  person Notlikethat    schedule 16.03.2014
comment
О, я не знал, что в MATLAB уже есть такая реализация. Я посмотрю на это.   -  person etua    schedule 17.03.2014


Ответы (1)


Если вы все еще используете цикл for, рассмотрите возможность сохранения colindexes(i,:) в переменной. Вы используете его 4 раза. Это может немного сэкономить ваше время.

person user51578    schedule 06.06.2019