Проблема производительности при работе с массивами большой размерности

здравствуйте дорогие форумчанине!
Сбагрил программку обрабатывающую шум с прибора и фильтрующая его, после чего выдаёт это всё на zedgraph.
При прогоне 10тыс точек всё получалось достаточно быстро, но как только я вогнал туда 1млн точек...
Комп подвис и через минуту-две выдал-таки графики с шумами и без. Но это слишком долго. значения коэффициентов для фильтров мне нужно практически вручную определять и если на кажду проверку будет уходить по 1-2 мин. А если массив возьму пару часов(более 16 млн точек).
Для обработки пользуюсь простыми массивами.
т.е. создаю массив нужной размерности и пошло поехало.
private double[,] massiv = new double[,];
м.б. в случаях с большими массивами стоит пользоваться какими-нибудь другими способами???
Или же у меня где-нибудь в программе(VS) стоит какая-нибудь фича которая тормозит просчёт????

0

ToLexx, не видя кода сказать что-либо конкретное сложно.

0

Сообщение от ToLexx м.б. в случаях с большими массивами стоит пользоваться какими-нибудь другими способами???

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

И да, код бы тебе привести, в слепую сложновато

0

а вот и файлики)allan.rar

0

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

0

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

0

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

0

OwenGlendower, у него в этом цикле создаются переменные и массивы
Добавлено через 2 минуты
Можно подсчитать сколько раз выделяется память под эти переменные при 1 миллионе maxPoints. Меня цифра слегка пугает.

0

вполне может быть, но у меня проблемы уже на этапе фильтрации получаются когда выбираю фильтрацию и идёт обращение к ф-иям transform и CalcMat в файле calc.cs. Выбираю для обработки массив 1мдн точек и он просто зависает.

0

aquaMakc, на каждой итерации память выделяется только на массив sum. Остальные переменные являются локальными переменными value-типа и значит память для них резервируется один раз в начале метода на стеке.

Добавлено через 7 минут
ToLexx, у тебя наверное ошибка в алгоритме. Массив sum всегда содержит только нули. Поэтому цикл обновляющий массив means будет заполнять его всегда нулями.

1

Сообщение от OwenGlendower Остальные переменные являются локальными переменными value-типа и значит память для них резервируется один раз в начале метода на стеке

Если честно с выделением памяти под базовые типы я не разбирался, но я всё-таки сомневаюсь, что мы в каждой итерации цикла будем иметь дело с одними и теми-же экземплярами структур Int32 и Double. В конце-концов на MSDN написано

Члены, которые должны менять состояние экземпляра, в действительности возвращают новый экземпляр, инициализированный новым значением.

Хотя я могу ошибаться.

0

aquaMakc, ты глубоко ошибаешься. Память под все локальные переменные резервируется в начале метода. Цитата из MSDN всего лишь описывает фундаментальное свойство value-типов - передачу по значению.

0

OwenGlendower, ) спасибо, буду иметь в виду

Добавлено через 28 минут
ToLexx, подвисает потому-что выполняется в основном потоке, если вынести в отдельный поток врядли будет работать быстрее, но форма зависать не будет ).
Могу посоветовать вынести тяжёлые математические функции в отдельную библиотеку на том-же c++ и вызывать их из твоей программы. Читал, что это нормальное решение, если нужна производительность, а уходить с шарпа не хочется, но сам пока так не заморачивался.

0

ооо о как.
то бишь всё -таки рассчитывается именно массив долго?! Не zedgrapр отображает и ни что иное?!
Ща посоветовали каждую итерация pt кидать в txt файл вместе с системным временем.Если получится равномерное занесение, то типа всё дело ток в кол-ве точек.

Добавлено через 20 минут
сейчас прочитал статью http://http://ferrum-box.blogspot.ru/2013/09/linq.html. стоит смотреть в эту сторону или как? Реально уменьшить??

0

Сообщение от ToLexx Ща посоветовали каждую итерация pt кидать в txt файл вместе с системным временем

Нагляднее использовать StopWatch

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

0

Ага кроме того сейчас обрезал обрабатываемые массивы. ведь вывожу то 1 столбец, а обрабатываю 3. код сразу какой- то маленький стал без всех этих итераций j.

0

ToLexx, Попробовал я ваш исходник. Не знаю как у вас, а у меня больше всего времени тратится не на расчеты, а на парсинг текстового файла. Поэтому:
1) Не нужно вызывать парсинг несколько раз (он вызывается сначала в CalcMat, а затем вызывается еще раз при отображении графика). Нужно один раз пропарсить, а потом передавать в методы сформированный double[,]
2) Парсинг CSV файла - не оптимален, используйте вот этот парсер Передача данных из файла *CSV в таблицу dataGridView он будет значительно быстрее.
3) Ваш код у меня сразу вылетел в исключение, из-за того что вы все числа преобразуете в формат с запятой, а у меня стоит разделитель - точка.
4) Вы тратите очень много времени на Replace('.', ','). Это неправильно и не оптимально.
5) Math.Pow(raznost, 2); => raznost * raznost;
6) Рассчет выражений типа (beta / (beta + 1)) и (1 / (beta + 1)) нужно вынести за пределы циклов, поскольку они константны.

Касаемо пунктов 3 и 4: заменять точки на запятые - неправильно в принципе. Во-первых, метод double.Parse() парсит с текущими настройками пользователя. Поскольку вы точки заменяете на запятые, то ваш код считает нормально, только если у пользователя стоит разделитель запятая.
Во-вторых, я пользуюсь таким правилом: если парсится число, вводимое пользователем в интерфейсе программы, то нужно пользоваться просто double.Parse(), который парсит с текущими настройками разделителя. Запятые на точки заменять не нужно. Если же текстовый файл приходит извне (ваш случай) - тогда я считаю, что он в InvariantCulture, и имеет разделитель точку.
Итого, в методе transform вам не нужно заменять точку на запятую или наоборот, вам просто нужно парсить в инвариантной культуре:

2

Сейчас посмотрю, завтра закончу, отпишусь и файлик покажу как сделаю.

Добавлено через 9 минут
сейчас попробовал double.Parse(tbBetta1.Text) выдало exception:
"Необработанное исключение типа "System.FormatException" в mscorlib.dll
Дополнительные сведения: Входная строка имела неверный формат."

Добавлено через 11 минут
Попробоваля ещё такой вариант:
beta1 = double.Parse(tbBetta1.Text,NumberStyles. AllowDecimalPoint);
Тоже исключение. Всё утро вечера мудрёнее. Пойду спать. всё равно спс.

Добавлено через 8 часов 5 минут
Storm23
beta1 = double.Parse(tbBetta1.Text,CultureInfo.I nvariantCulture);
Всё заработало, вот только вы предлагали данный parse для чтения из файла, нормально ли его использовать с текстбоксами?

0

ToLexx, Ок. Теперь посмотрим на метод вычисления дисперсии Аллана (allanFunc).
Тут конечно прекрасно все: и алгоритм, и реализация, и оптимизация
Во-первых, у вас там ошибка, собственно сумма элементов массива не вычисляется (вам уже писали об этом в посте #10).
Но это не главное. Главное то, что в вычислительной математике нельзя вот просто так взять и применить математические формулы в лоб. Сложность вашего алгоритма O(n * k). Где n - число исходных точек (1000000) а k - число интервалов для тау (у вас 50000). Понятно, что число итераций огромно. Поэтому и считается это долго.
Оптимизируется это дело следующим образом: для вычисления всевозможных сумм в массивах используется т.н. интегральное представление. Смысл в том, что вы считаете первообразную (накопительную сумму) по всему массиву значений. А далее вы можете быстро посчитать сумму на любом отрезке этого массива, пользуясь свойством интеграла:

(где F - первообразная)

Таким образом для вычисления суммы на любом отрезке массива вам нужно просто посчитать разность двух чисел.
Т.о. сложность алгоритма для вычисления Аллана становится O(k), вместо прежних O(n * k). Прирост производительности можете посчитать сами

Исправленный исходник allan.zip.
Ошибки и иcправления я отметил стрелкой <<------

Еще пару моментов:
1) Вы в интерфейсе пишете что считается дисперсия Аллана, а на самом деле пытались считать ср.кв. отклонение (то есть корень из дисперсии). Я сейчас считаю дисперсию, если нужно отклонение - возьмите корень.
2) У вас вывод по осям сделан неоптимально. Вам нужно один раз посчитать результат (он сичтается по всем осям), а при переключении радиобаттона осей, нужно просто перестраивать график для соотв оси. Вы же сейчас для каждой оси начинаете пересчет заново.
3) Алгоритм хорошо паралелится, но мне было лень. Вы можете распаралелить сами, если не будет хватать производительности.

Сообщение от ToLexx Всё заработало, вот только вы предлагали данный parse для чтения из файла, нормально ли его использовать с текстбоксами?

Для текстбоксов используйте просто double.Parse(). Этот метод использует текущие настройки пользователя. И соотвественно ваша программа тоже ожидает ввод в том формате, который указан в настройках системы.

0

Сообщение от Storm23 Для текстбоксов используйте просто double.Parse(). Этот метод использует текущие настройки пользователя.

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


или на Вашей кривой 1-ый нырок это и есть искомая кривая.
Вообще простите по сути ведь благодаря этой кривой мы можем определить оптимальное количество отсчётов для осреднения(для определения значения сигала на данном отрезке времени).

0