Какую платформу выбрать для максимальной скорости решения задачи?

Добрый день!

У меня есть алгоритм, в котором считается матрица близостей для большого количества точек. Вектора (точки) могут иметь большой размер, а количество точек исчисляется тысячами и десятками тысяч. Соответственно, работает у меня все медленно: 10 000 записей в массиве перебираются 10 000 раз и при этом считается эвклидово расстояние. Я программирую на VBA & MQL (metatrader).

Как можно это ускорить? Применение расчетов на GPU может дать ускорение? Может быть, есть какие-то хитрости для ускорения алгоритма полного перебора?

Буду благодарен за подсказки.

0

переписывайте расчёты в виде функций на языке С, запихивайте их в dll, затем вызывайте из метатрейдера.
Ускорение математики (по моему опыту года 2007 вроде бы - т.е. на МТ4, а пятый может и побыстрее четвёртого быть) было раз в 20. За счёт того, что псевдокомпилированный (и затем исполняемый интерпретатором) метатрейдеровский код был заменён истинным машинным кодом. У меня тоже евклидовы расстояния считались - но для алгоритма кластеризации типа динамических ядер.
Ещё в 4 раза ускорение будет при векторизации расчётов (при использовании SSE-команд процессора). Хороший сишный компилятор (типа интеловского, майкрософтовского) может векторизовать и сам - но я бы на это не надеялся, если не имеете опыта и не знаете, как правильно всё указать компилятору и сделать всё сопутствующее (ибо там ещё надо будет данные выравнивать на границу параграфа). Или даже в 8 раз ускорение - на AVX-командах. Т.е. 20*4=80, или 20*8=160, вот такое вот ускорение может быть, грубо говоря - в сотню раз.

GPUшка подобное тоже ускорит. Но к ней надо будет тоже ходить из dll, написанной на С/С++ (васик же вроде не позволит?), так что проще, наверно, будет сделать минимальный шаг (сишный код, пусть и не оптимизированный, зато откомпилированный в настоящие команды процессора) - вдруг уже после ускорения раз в 20 всё станет комфортным?

Насчёт изменения алгоритма - пока ничего сказать не могу, недостаточно информации о задаче (нафиг считается матрица близостей и т.д.).

1

Сообщение от alexmosc Применение расчетов на GPU может дать ускорение?

Конечно может! Вместо вложенного цикла со сложность алгоритма будете считать всё сразу в потоков со сложность O(C).

Сообщение от alexmosc Может быть, есть какие-то хитрости для ускорения алгоритма полного перебора?

Если условия задачи позволяют - замените евклидово расстояние на метрику Минковского 1-го порядка (расстояние городских кварталов).

1

Сообщение от VTsaregorodtsev переписывайте расчёты в виде функций на языке С, запихивайте их в dll, затем вызывайте из метатрейдера.

VTsaregorodtsev, спасибо за подробный ответ!

Я попробую сделать dll на C, или попрошу кого-нибудь. Сейчас я могу комфортно прогнать 20 000 записей, как раз хватает времени на чай попить. А хотелось бы, например, часовые бары за 15 лет (более 90 000) посмотреть. Это реализую в будущем.

Сообщение от VTsaregorodtsev Насчёт изменения алгоритма - пока ничего сказать не могу, недостаточно информации о задаче (нафиг считается матрица близостей и т.д.).

VTsaregorodtsev, я был бы рад услышать Ваше мнение о том, что я делаю. Думаю написать даже статью (первую по статистике).

Дошел до идеи критерия силы зависимостей в произвольном ряде данных (может не произвольном, но в обширном семействе рядов).

(Знаю, что таких методов много. Сам считал теоретико-информационные статистики, в частности: total correlation, mutual information, pointwise mutual information).

1 шаг алгоритма: считаю среднее расстояние между двумя случайными точками. Для этого и беру полную матрицу близостей и считаю среднее по полученным значениям. Некоторые тонкости буду опускать, чтобы быть кратким. Каждая точка отражает отрезок ряда данных любой длины n >= 1. Выбираем сами. Данное среднее расстояние есть не что иное как мат.ожидание расстояний между прошлым и будущим ряда при отсутствии памяти. То есть, за любым вектором последует любой другой (перехлесты частичные и полные исключаю).

2 шаг. Считаю расстояния между последовательно идущими векторами (без перехлеста). Беру также среднее. Это будет мат.ожидание расстояния между прошлым и будущем, наблюдаемое в ряде.

3 шаг. Беру отношение второго к первому. Получаем либо 1 - наблюдаемый ряд без памяти, меньше 1 - за произвольным вектором следует похожий вектор - персистентность ряда, больше 1 - за вектором следует отличный от него вектор - антиперсистентность ряда. В пределе данное отношение будет равно 0 или 2 (можно поделить на 2, чтобы получить от 0 до 1, где 0,5 - памяти нет), что означает полную детерминированность. Это я называю слабым критерием, так как вероятен вариант, когда в ряде с памятью мат.ожидание расстояний между соседними векторами совпадет с мат.ожиданием рандомного ряда.

4 шаг - вычисление сильного критерия. Построим гистограмму плотности расстояний по 1 и 2 пункту. Количественно выразим различие в функциях плотности. Если в гиперкубе есть упорядоченность связей между точками, все будет видно на гистограммах.

Таким образом, я говорю про критерий наличия статистических связей в последовательности данных. С параметрами нужно играть: длина вектора выбирается эмпирически, преобразование ВР в вектора тоже опытно, логарифмировать, взять differences, в процентах или в абсолютных значениях, нормализовать ли каждую переменную вектора в один интервал - на выбор исследователя.

На ряде котировок цен открытия дня EURUSD за 10 лет получается, что минимум критерия достигается на длине вектора 10-20, где коэффициент принимает значения 0,95. То есть, работает персистентность.

Для биткоинных данных по дням коэффициент очень отличается от рандома.

Для синтетика, цепи Маркова 1 порядка, порог вероятности 0,6, отлично видно, ряд трендовый или антитрендовый. Коэффициент отличается от рандома на 20%!

И т.д.

Как вы думаете, эта работа заслуживает детального описания в рамках статьи?

Сообщение от evgr Конечно может! Вместо вложенного цикла со сложность алгоритма будете считать всё сразу в потоков со сложность O(C).

evgr, спасибо! Буду иметь в виду на будущее, но сам факт уже радует!

Добавлено через 7 часов 13 минут

Сообщение от evgr Если условия задачи позволяют - замените евклидово расстояние на метрику Минковского 1-го порядка (расстояние городских кварталов).

Спасибо! Почитаю, подумаю.

0

Сообщение от alexmosc А хотелось бы, например, часовые бары за 15 лет (более 90 000) посмотреть. Это реализую в будущем.

Ну, это обычный процессор без проблем сделает. Сужу, правда, по своему опыту программирования расчётных задач (а я программировать-оптимизировать математику умею).
Сотня тыс. векторов, и перебор каждого с каждым - это для меня комфортно. Пример - оценка константы Липшица в задаче обучения с учителем, там надо найти максимум отношения нормы разности выходных (зависимых) частей векторов к норме разности входных (независимых) частей векторов. Т.е. получение оценки, насколько существенно может меняться выход моделируемой системы при некотором изменении входов.
Причём, заметьте, ещё и на несколько ядер процессора расчёты можно распараллелить (ну, это уже кто насколько компетентен или насколько готов глубоко погружаться в системное программирование).

Насчёт же Вашей идеи алгоритма/статистики... Не знаю. Сильно просто получается - может, эта америка уже давно открыта. Мне, например, похожий (вернее, не для временных рядов) подход показали мои ботанико-экологические соавторы. У них это называется коэффициентом коллигации (если нужна ссылка на печатную работу, откуда всё это растёт - то, например, Нешатаев В.Ю. Методы анализа геоботанических материалов. – Л., 1987 - 188 С.), он равен отношению апостериорной вероятности p(y_i|z_j) наблюдаемости i-го биовида в j-й зоне к априорной вероятности p(y_i) встречи этого вида среди всех видов на всей широкой территории (несколько неперекрывающихся зон). Когда коэффициент коллигации выше единицы, можно говорить о предпочтениях вида к j-й зоне, когда значительно ниже единицы – о приближении эколого-климатических условий зоны к границам ареала биовида (биовиду в условиях этой зоны некомфортно, он там встречается реже, чем "в среднем по большой больнице").
Мне просто мой склероз во втором часу ночи уже изменяет - помню то, чего реально касался руками Для лесообразователей Сибири - коэффициенты коллигации таки нормально показывают приуроченности или предпочтения разных пород к разным климатическим зонам.
У Вас же вместо отношения вероятностей - отношение расстояний, и дальнейшие шаги. В общем, мне подумать надо (вспомнить, встречал ли что подобное) - но на свежую голову я на форуме обычно не появляюсь

0

Сообщение от VTsaregorodtsev Насчёт же Вашей идеи алгоритма/статистики... Не знаю. Сильно просто получается - может, эта америка уже давно открыта.

Спасибо большое за ответ! Я специально Вам задал вопрос, так как знаю, что Вы большой эксперт.

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

Я тут думал еще над этим алгоритмом и понял, что он сырой. Ну во-первых, не факт все же, что разница в плотности расстояний буде обязательно иной. Не могу доказать. Сила критерия под вопросом.

Во-вторых, смущают экстремумы критерия: если он близок к нулю, векторы будут максимально похожи, а если 1 - зеркально непохожи. А если вектор детерминирован по ацки сложной нелинейной формуле, но не похож?, - подумал я. Тогда максимизации или минизации не произойдет вообще. И пришел к следующему шагу.

В-третьих. Я набираю массив расстояний между двумя любыми векторами (без повторов), где количество расчетов будет равно (N^2 - N) / 2. Догадался снизить объем расчетов, исключая повторы.

Заполняю массив, например, расстоянием между точкой Ai и Ai+x, в другом столбце массива я считаю расстояния между векторами, которые соответствуют "будущему" двух обработанных точек: Ai+future и Ai+x+future, то есть, со сдвигом на количество лагов, отделяющих будущее.

Заполнил весь массив, затем построил по парам значений точечную диаграмму. Теперь самое интересное. В предположении о том, что два соседних вектора связаны функционально и строго, имеет место положение: при расстоянии между двумя точками стремящемся к 0, расстояние между соответствующими этим точкам векторам "будущего" будет также стремиться к 0.

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

Для логистического отображения хаоса, при параметре r = 3,7 (при векторе длиной 1, то есть мерим связь между соседними точками) получается следующая графика - во вложении.

Интересует левый угол. Четко видно, что в пределе уменьшение расстояния между парой точек ведет к уменьшению расстояния между соответствующими им точками будущего.

Пока новый критерий не считал, но если показать справедливость такого схождения в ноль, то это будет доказательством наличия детерминированности.

Пока я выдохся.

Миниатюры

 

0

alexmosc, ну, динамические системы и детерминированный хаос как расчётные примеры - это уже совсем другое, по сравнению с "невидимой рукой рынка"
Для нормальных динам.систем - Вы так получите оценку ляпуновского показателя, с точностью до какого-то масштабирующего множителя или гладкой функции y=f(x) (где y - то, что посчитается у Вас, а х - оценка ляпуновского показателя, которая меряется не по отстоящим во времени векторам, а по параллельно (вернее, рядом) проходящим участкам траектории динам.системы).

0

Сообщение от VTsaregorodtsev динамические системы и детерминированный хаос как расчётные примеры - это уже совсем другое, по сравнению с "невидимой рукой рынка"

Спасибо, VTsaregorodtsev.

Это был синтетический пример, чтобы продемонстрировать работу подхода. Такая же красивая картинка получается при анализе простой синусоиды, если мы берем n>1 длину вектора - тогда полная детерминированность следующего состояния кривой: в нуле точки сходятся, что говорит о функциональной зависимости, а по ходу роста X растет и Y.

Ну, я говорю о том, что если функциональная зависимость - пусть слабая - есть, то будет наблюдаться схождение в нуле. Получается, похоже на теорию хаоса. Хм, интересно, может я подсознательно оттуда и почерпнул методику.

А вот данные по реальным наблюдениям. Пара eurusd, дневные цены открытия, примерно 8 лет. Вектор взят длиной 3 точки.

Первый график всеобъемлющий, а второй с увеличением, чтобы левый край было лучше видно.

Заметно, что расстояния начинают расти. Вот как оформить в виде одного числа тот факт, что около нуля распределение не равномерное, растущее, я пока не додумался.

Еще, кстати, интересно, что максимальное дистанцированные вектора (правая часть X) дают будущее более похожее, чем рандом.

"Невидимая рука рынка" это же и есть функция зависимости, только один маленький вопросик: чего от чего и как это измерить. Это поиск иголки в стоге сена.

Миниатюры

   

0

Ааа, подчеркну, что связи с мат.аппаратом хаотических динамических систем не предполагается! Достаточно показать, что чем ближе вектора, тем более похожее будущее они генерируют, что выливается в наличие зависимости. А дальше идет игра с построением вектора, количеством лагов и т.д. Можно, например, даже сравнить многомерный вектор и следующую за ним одну точку (между ними расстояния точно также будут считаться).

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

0