2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Оптимизация алгоритма с тригонометрическими функциями
Сообщение04.04.2015, 13:19 
Аватара пользователя
Нужен совет по оптимизации данного алгоритма.
На вход алгоритм получает $N$ чисел $\psi_{1},\psi_{2},\ldots,\psi_{N}$ , $N$ пар $\left(x_{1},y_{1}\right),\left(x_{2},y_{2}\right),\ldots,\left(x_{N},y_{N}\right)$ и $L$ пар $\left(\theta_{1},\varphi_{1}\right),\left(\theta_{2},\varphi_{2}\right),\ldots,\left(\theta_{L},\varphi_{L}\right)$.
Далее вычисления выполняются так:
  1. Случайно, с равномерным законом распределения, выбираем индекс $m\in\left[1,N\right]$
  2. Вычисляем $B_{m}$ по формуле
    $B_{m}=\sum_{n=1}^{N}\sum_{l=1}^{L}e^{i\left(\psi_{n}+\alpha_{ml}-\alpha_{nl}\right)}-Le^{i\psi_{m}},$

    где
    $\alpha_{pq}=\frac{2\pi}{\lambda}\left(x_{p}\sin\theta_{q}\cos\varphi_{q}+y_{p}\sin\theta_{q}\sin\varphi_{q}\right);$

  3. Вычисляем новое значение $\psi_{m}$ по формуле
    $\psi_{m}=\pi+\arg B_{m};$
  4. Если еще не все $\psi_{m}$ обработаны, переходим на п.1;
  5. Вывод $\left\{ \psi_{1},\psi_{2},\ldots,\psi_{N}\right\}$

В моей задаче $N$ порядка нескольких тысяч, $L=75$, а уложиться надо в несколько миллисекунд на 12-ядерном ксеоне.

Я делаю так: новое значение каждого $\psi_{m}$ вычисляется по формуле $\psi_{m}=\pi+\mathrm{\arctg}\frac{\sum_{l=1}^{L}\sin\alpha_{ml}\sum_{n=1}^{N}\cos\left(\psi_{n}-\alpha_{nl}\right)+\sum_{l=1}^{L}\cos\alpha_{ml}\sum_{n=1}^{N}\sin\left(\psi_{n}-\alpha_{nl}\right)-L\sin\psi_{m}}{\sum_{l=1}^{L}\cos\alpha_{ml}\sum_{n=1}^{N}\cos\left(\psi_{n}-\alpha_{nl}\right)-\sum_{l=1}^{L}\sin\alpha_{ml}\sum_{n=1}^{N}\sin\left(\psi_{n}-\alpha_{nl}\right)-L\cos\psi_{m}}$. Видно , что суммы $\sum_{n=1}^{N}\cos\left(\psi_{n}-\alpha_{nl}\right)$ и $\sum_{n=1}^{N}\sin\left(\psi_{n}-\alpha_{nl}\right)$, а также значения $\cos\alpha_{pq}$ и $\sin\alpha_{pq}$ можно вычислять заранее, параллельно для всех возможных комбинаций индексов. А после вычисления каждого нового значения $\psi_{m}$ заменять соответствующий ему элемент суммы.

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

 
 
 
 Re: Оптимизация алгоритма с тригонометрическими функциями
Сообщение08.04.2015, 14:17 
Аватара пользователя
Добавьте два массива SS и SC размерностью L, и до начала вычисления $B_m$ заполните их $ SC_q=\sin\theta_{q}\cos\varphi_{q}$ и $SS_q=\sin\theta_{q}\sin\varphi_{q}$

-- 08 апр 2015, 14:24 --

Этого должно хватить. Непонятно другое - выбираете случайно или так, чтобы перебрать все N значений в случайном порядке?

 
 
 
 Re: Оптимизация алгоритма с тригонометрическими функциями
Сообщение08.04.2015, 19:00 
Аватара пользователя
Евгений Машеров в сообщении #1001576 писал(а):
Непонятно другое - выбираете случайно или так, чтобы перебрать все N значений в случайном порядке?
Перебрать все $m\in\left[1,N\right]$ в равномерно-случайном порядке без повторов. К сожалению не известна оптимальная последовательность перебора при $L>1$.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group