Как я могу оптимизировать этот алгоритм индексирования

Мои вопросы

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

Описание алгоритма

У меня сложная проблема индексирования, которую я изо всех сил пытаюсь решить.

Цель состоит в вычислении матрицы w_prime с использованием значений комбинация значений из матриц одинакового размера w, dY и dX.

Значение w_prime(i,j) рассчитывается как mean( w( indY & indX ) ), где indY и indX - это индексы dY и dX, которые равны i и j соответственно.

Здесь простая реализация в matlab алгоритма для вычисления w_prime:

for i = 1:size(w_prime,1)
  indY = dY == i;
  for j = 1:size(w_prime,2)
    indX = dX == j; 
    w_prime(ind) = mean( w( indY & indX ) );
  end
end

Проблемы с производительностью

Эта реализация достаточна в примере ниже; однако в моем фактическом случае использования w, dY, dX равны ~ 3000x3000 и w_prime равно ~ 60X900. Это означает, что каждый расчет индекса происходит на ~ 9 миллионов элементов. Излишне использовать эту реализацию слишком медленно, чтобы ее можно было использовать. Кроме того, мне нужно будет запустить этот код несколько десятков раз.

Пример расчета

Если я хочу вычислить w(1,1)

  • Найти индексы dY, равные 1, сохранить как indY
  • Найти индексы dX, равные 1, сохранить как indX

enter image description here

  • Найти пересечение indY и indX сохранить как ind

enter image description here

  • Сохраните mean( w(ind) ) до w_prime(1,1)

enter image description here

Общая проблема Описание

У меня есть множество точек, определяемых двумя векторами X, и T, оба равны 1XN, где N равно ~ 3000. Кроме того, значения X и T являются целыми числами, связанными интервалами (1 60) и (1 900) соответственно.

Матрицы dX и dT являются просто матрицами расстояний, что означает, что они содержат попарные расстояния между точками. Ie dx(i,j) равно abs( x(i) - x(j) ).

Они вычисляются с использованием: dx = pdist(x);

Матрица w может рассматриваться как весовая матрица, которая описывает, какое влияние оказывает одна точка на другую.

Цель вычисления w_prime(a,b) - определить средний вес между подмножеством точек, разделенных a в измерении X и b в измерении T.

Это можно выразить следующим образом:

enter image description here

Ответы

Ответ 1

Это просто с ACCUMARRAY:

nx = max(dX(:));
ny = max(dY(:));

w_prime = accumarray([dX(:),dY(:)],w(:),[nx,ny],@mean,NaN)

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

w_prime = accumarray([dX(:),dY(:)],w(:),[],@mean)

Итак, что делает резервуар? Он смотрит на строки [dX(:),dY(:)]. Каждая строка дает координатную пару (i,j) в w_prime, к которой добавляется строка. Для всех пар (1,1) он применяет функцию (@mean) к соответствующим записям в w(:) и записывает вывод в w_prime(1,1).