Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
temp888
0 / 0 / 0
Регистрация: 14.12.2012
Сообщений: 17
1

Найти пару (2 и более) векторов СКО = 0

03.12.2015, 02:48. Просмотров 286. Ответов 13
Метки нет (Все метки)

Есть массив
double data[500][5000]

Содержит значения -100..100

Нужно найти сумму строк(векторов) и выбрать такие пары СКО которых стремиться к 0

Пример

C++ (Qt)
1
2
3
4
5
6
7
8
9
10
#pragma omp parallel for schedule(dynamic, 1)
for(int i = 0;i < 500;i++){
   for(int j = i + 1;j < 500;j++){
      double tmp[5000];
      for(int p = 0;p < 5000; p++){
         tmp[p] = data[i][p] + data[j][p];
      }
      stddev(tmp);
   }
}
Работает жутко медленно.
В перспективе находить пару из 10-15 векторов.

Как максимально оптимально решить задачу, какие методы использовать?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.12.2015, 02:48
Ответы с готовыми решениями:

Найти пару векторов из заданного набора имеющую минимальное скалярное произведение
Даны p различных векторов одинаковой размерности N: a^((1))={〖a^((1))〗_n }= , и ...

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

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

Выбрать пару векторов или массивов, которая даст минимальное скалярное произведение
Добрый день, подскажите пожалуйста как создать n векторов или массивов, если изначально не известно...

Дан массив экспериментальных значений Х. Найти среднее и СКО
дано массив экспериментальных значений X. Определить функции вычисления среднего значения x и...

13
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,487
03.12.2015, 09:37 2
Цитата Сообщение от temp888 Посмотреть сообщение
выбрать такие пары СКО которых стремиться к 0
что значит "стремится к 0"? меньше заданного значения? минимальное из имеющихся?

Цитата Сообщение от temp888 Посмотреть сообщение
Как максимально оптимально решить задачу, какие методы использовать?
1. Нужно заранее посчитать суммы всех строк.
http://www.cyberforum.ru/cgi-bin/latex.cgi?S_{i} = \sum_{p=0}^{n-1}x_p

Пусть
http://www.cyberforum.ru/cgi-bin/latex.cgi?F_{ij} = \sum_{p=0}^{n-1}(x_p - \bar{x})^2
где
http://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{x_{ij}} = (S_{i} + S_{j})/n
Тогда
http://www.cyberforum.ru/cgi-bin/latex.cgi?\sigma_{ij} = \sqrt{\frac{1}{n}F_{ij}}

2. исходя из этой формулы определяемся с критерием для Fij

3. для всех пар строк в цикле "на лету" считаем Fij с отсечением по критерию из пункта 2 (массив tmp не нужен)
0
temp888
0 / 0 / 0
Регистрация: 14.12.2012
Сообщений: 17
03.12.2015, 13:39  [ТС] 3
что значит "стремится к 0"? меньше заданного значения? минимальное из имеющихся?
например в double tmp[5000]; у нас все значения 10 то СКО такого массива будет 0
смысл выбрать такие i j СКО которых минимально

Нужно заранее посчитать суммы всех строк.
Суммы строк могут совпадать, если суммировать пары и хранить эти данные памяти не хватит
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,487
03.12.2015, 14:00 4
Цитата Сообщение от temp888 Посмотреть сообщение
смысл выбрать такие i j СКО которых минимально
Это я понял. Но я не понял, почему во множественном числе "выбрать такие пары".
Значит, в качестве критерия используем текущее минимальное значение.

Цитата Сообщение от temp888 Посмотреть сообщение
Суммы строк могут совпадать
Ну и пусть себе совпадают. Вы даже не узнаете, что какие-то суммы совпали.

Добавлено через 5 минут
Цитата Сообщение от temp888 Посмотреть сообщение
если суммировать пары и хранить эти данные памяти не хватит
зачем суммировать пары, если сумму пары строк можно вычислить, сложив суммы этих строк?
0
temp888
0 / 0 / 0
Регистрация: 14.12.2012
Сообщений: 17
04.12.2015, 16:16  [ТС] 5
У нас есть i процессов и j измерений по дискретным периодам.
Цель найти такие процессы работа которых в группе даст СКО 0 или самое минимальное.

Например [2,-1],[0,1],[-4,5] в итоге получили вектор {1,1,1} и СКО такого вектора 0

Так я вижу эту задачу влоб.
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
06.12.2015, 10:17 6
Цитата Сообщение от temp888 Посмотреть сообщение
Так я вижу эту задачу влоб.
Я тоже. shecdule dynamic здесь скорее в минус. Что за реализация stddev и как записывается рез-т? Если все аккуратно, то не должно оно быть "жутко медленно", похоже это рез-т стремления писать поменьше (не перетруждаться)

Добавлено через 19 часов 41 минуту
Да, забыл самое главное Здесь использование векторных команд процессора (SIMD) даст отличный прирост (в N раз) - стоит поискать такую реализацию stddev
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,487
06.12.2015, 17:17 7
Я не понимаю, в чём проблема. На моём ноутбуке для случайных данных считает за 1.5 сек в один поток и за 0.4 сек, если распараллелить. Это при том, что на случайных данных отсечение лишено смысла. Если у ТС данные неслучайны, и для некоторых пар близкие к нулю значения, то должно работать заметно быстрее за счёт отсечения.
0
temp888
0 / 0 / 0
Регистрация: 14.12.2012
Сообщений: 17
08.12.2015, 01:02  [ТС] 8
Как вы предлагаете отсекать?

Попробуйте найти группу из 5 процессов, боюсь ноутбук не справиться.
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,487
08.12.2015, 09:35 9
Цитата Сообщение от temp888 Посмотреть сообщение
Попробуйте найти группу из 5 процессов, боюсь ноутбук не справиться.
Правильно я Вас понял, что пара - это не 2 вектора, а 5?

(И нам надо посчитать ско для суммы этих 5 векторов?)
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
08.12.2015, 12:33 10
Цитата Сообщение от temp888 Посмотреть сообщение
Попробуйте найти группу из 5 процессов, боюсь ноутбук не справиться.

Не по теме:

И подошли они к рельсам.. "Бззззык" - сказала японская бензопила - и сломалась. "Аааа, блин!" - сказали суровые сибирские мужики

Для 3 и более нужна теория, выделять "группы" зная отношение/схожесть "каждый с каждым". Читайте, потом расскажете
0
temp888
0 / 0 / 0
Регистрация: 14.12.2012
Сообщений: 17
08.12.2015, 14:36  [ТС] 11
Цитата Сообщение от Shamil1 Посмотреть сообщение
Правильно я Вас понял, что пара - это не 2 вектора, а 5?
(И нам надо посчитать ско для суммы этих 5 векторов?)
На 5 мой компьютер не справляется. Грубый перебор не подходит.
В идеале нужно 10-20.
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,487
08.12.2015, 15:14 12
Если Вы парой называете 10-20, то Вам стоит сформулировать задачу так, чтобы было понятно, что Вам надо.
Лично я парой называю 2.

Цитата Сообщение от temp888 Посмотреть сообщение
Например [2,-1],[0,1],[-4,5] в итоге получили вектор {1,1,1} и СКО такого вектора 0
Вот этот Ваш пример ещё более запутывает, так как ИМХО противоречит тому, что было в исходном сообщении.
Из этого примера следует, что СКО считается не для векторов, а для сумм векторов. Что делает задачу элементарной.
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
08.12.2015, 15:56 13
Насколько я понял, юзер должен иметь возможность находить 5 (или 10, 20 - задается) серий измерений которые "максимально близки" друг к другу. В качестве критерия близости используется СКО по сумме серий - во всяком случае пока. Т.е. сложили 5 серий, получили новую серию (тоже из 500 эл-тов), и по ней уже СКО. Здесь конечно в лоб не пройдет

Не по теме:

В общем случае "элементарно" != "просто"



Давным-давно делал задачу для кардиологии, и вспомнилось такое: серии могут быть очень, очень близки, НО - с каким-то "смещением", поэтому при "просто сложении" СКО не поймает близость

Добавлено через 24 минуты
Что-то я тоже "потерял нить". Что это за критерий такой? Ну сложили 2 серии которые идеально совпадают - ну у серии-суммы СКО и будет максимальный (т.е. самый большой)
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,487
08.12.2015, 16:22 14
В первом сообщении есть код, который попарно суммирует вектора и считает ско получившегося вектора-последовательности. Я, по наивности решил, что именно это и требуется.

Теперь, вроде бы, выясняется, что нужно суммировать вектора не по 2, а по "10-15" и чем больше, тем лучше. Что само по себе странно. Ведь при увеличении количества на 1 задача кардинально меняется, и вектора из первого решения могут попасть во второе решение только случайно.
0
08.12.2015, 16:22
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.12.2015, 16:22

Найти базис системы векторов и координаты всех векторов в найденном базисе
найти базис системы векторов и координаты все векторов в найденном базисе если...

Найти классы аддитивной группы векторов плоскости по подгруппе векторов
Найти классы аддитивной группы векторов плоскости (выходящих из начала координат) по подгруппе...

Найти базис и ранг системы векторов и координаты всех векторов в найденном базисе
найти базис и ранг системы векторов a1=(1,2) a2=(2,3) a3=( 6,5) и координаты всех векторов в...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru