С Новым годом! Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.86/21: Рейтинг темы: голосов - 21, средняя оценка - 4.86
0 / 0 / 0
Регистрация: 25.07.2013
Сообщений: 163
1

Оптимизация кода с массивом

10.12.2013, 17:39. Показов 4027. Ответов 46
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Здраствуйте, есть некая программа которую сильно тормозит ниже представленный кусок кода... (для удобства некоторые места заменил конкретными цифрами), считается все это непотребство очень долго для выполняемой задачи
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
for (int pye=0; pye<(1103-104+1); pye++)
                {
                   for (int pxe=0; pxe<(1103-104+1); pxe++)
                  {
                    int ert = 0;
                    double summa_FragmentMassiv1 = 0;
                    double summa_FragmentMassiv2 = 0;
                    for (int o=pye; o<(pye+104);o++)
                         {
                            int egb = 0;
             for (int l=pxe; l<(pxe+104);l++)
                {
            summa_FragmentMassiv1+=Massiv1[o,l]*VesPF[ert,egb];
                                  summa_FragmentMassiv2+=Massiv2[o,l]*VesPF[ert,egb];                       
                   egb++;
                }
            ert++;
                   }
                     MassivRandn1[pye,pxe]=summa_FragmentMassiv1;
                     MassivRandn2[pye,pxe]=summa_FragmentMassiv2;
                   
                  }                
                }
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
10.12.2013, 17:39
Ответы с готовыми решениями:

Оптимизация кода
Console.WriteLine(&quot;Нажми Enter для старта...&quot;); // баги: 1. после вывода примера если нажать enter...

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

Оптимизация кода
Вопрос такой есть ли способ оптимизировать сей код, прибегая к помощи массивов или иными путями?...

Оптимизация кода
Как можно красиво зарефакторить следующий код? int a; int b; ...

46
Master of Orion
Эксперт .NET
6100 / 4956 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
13.12.2013, 21:21 21
Author24 — интернет-сервис помощи студентам
Hsert, Parallel.For нет смысла вкладывать друг в друга, т.к. число ядер не превышает как правило восьми, то есть даже в верхнем цикле каждой итерации не достанется отдельного потока.

Оптимизировать можно, но нетривиально.
0
338 / 327 / 154
Регистрация: 29.10.2012
Сообщений: 949
15.12.2013, 10:01 22
Как уже говорилось выше единственное что приходит в голову для уменьшения времени работы это уменьшения количества циклов.
Но циклы ведь количество циклов можно уменьшать по разному. Вспомнил еще школьный пример увеличения быстродействия программы:
Вот есть такие исходные данные - вещественный массив 100х100 и умножаем его на одномерный массив длиною 100:
Кликните здесь для просмотра всего текста
C#
1
2
3
4
5
6
7
8
9
double[,] arr = new double[100, 100];
double[] v = new double[100];
Random r = new Random();
for (int i = 0; i < 100; i++)
{
    for (int j = 0; j < 100; j++)
        arr[i, j] = (double)r.Next(100000, 10000000) / 1000;
    v[i] = (double)r.Next(100000, 10000000) / 1000;
}

Если запустить умножение каждой исходной строки массива на второй массив, то уже при 100 тыс. у меня заняло 11 сек. см. приложенный файл.
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
double summ = 0;
int index = 0;
 
for (int k = 0; k < 100000; k++)
    for (int i = 0; i < 100; i++)
    {
        for (int j = 0; j < 100; j++)
        {
            summ += arr[i, j] * v[j];
            index++;
        }
    }
stopwatch.Stop();
Console.WriteLine(stopwatch.Elapsed);
А вот если допустить, что наш массив по ширине кратный 10,то можно в одном проходе внутреннего массива провести 10 операций сложения/умножения, тем самым уменьшить количество внутренних массивов в 10 раз.
Вот так:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
double summ = 0;
int index = 0;
 
for (int k = 0; k < 100000; k++)
    for (int i = 0; i < 100; i++)
        for (int j = 0; j < 10; j++)
        {
            summ += arr[i, j] * v[j];
            j++;
            summ += arr[i, j] * v[j];
            j++;
            summ += arr[i, j] * v[j];
            j++;
            summ += arr[i, j] * v[j];
            j++;
            summ += arr[i, j] * v[j];
            j++;
            summ += arr[i, j] * v[j];
            j++;
            summ += arr[i, j] * v[j];
            j++;
            summ += arr[i, j] * v[j];
            j++;
            summ += arr[i, j] * v[j];
            j++;
            summ += arr[i, j] * v[j];
        }
stopwatch.Stop();
Console.WriteLine(stopwatch.Elapsed);
То и время обработки этого объема данных у меня уменьшилось до 1,2 сек. См приложенный второй файл.
И того время уменьшилось в 9,46 раза.
Согласен увеличивается количество кода, но никто не мешает вынести все это в отдельный класс и оттуда запускать. Можно написать несколько классов, например для массивов кратных числам 2, 3, 5, 10, 17 и т.д. и перед запуском проверять кратность и вызывать соответствующий метод.
0
0 / 0 / 0
Регистрация: 25.07.2013
Сообщений: 163
15.12.2013, 10:06  [ТС] 23
Агерон вроде понял что необходимо сделать, я вроде же и схему нарисовал по ней должно быть понятно, скорее сего что бы уменьшить время решения нужно действительно алгоритм другой
0
338 / 327 / 154
Регистрация: 29.10.2012
Сообщений: 949
15.12.2013, 10:22 24
В вашем исходном коде если строки с 11 по 17 заменить вот на этот участок кода, то должно все заработать, теоретически, в 1,5-2 раза быстрее:
C#
1
2
3
4
5
6
7
8
9
10
11
for (int l = pxe; l < (pxe + 104)/2; l++)
{
    summa_FragmentMassiv1 += Massiv1[o, l] * VesPF[ert, egb];
    summa_FragmentMassiv2 += Massiv2[o, l] * VesPF[ert, egb];
    l++; 
    egb++;
    summa_FragmentMassiv1 += Massiv1[o, l] * VesPF[ert, egb];
    summa_FragmentMassiv2 += Massiv2[o, l] * VesPF[ert, egb];
    egb++;
}
ert++;
Но только если у Вас pxe четное.
0
Master of Orion
Эксперт .NET
6100 / 4956 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
15.12.2013, 13:06 25
kmaffa, и в чем разница? Экономится одна оперция сравнения? Зато появляется деление в условии. Этот код может быть даже дольше выполняться...

Добавлено через 58 секунд
Кстати условие неправильно поменяли, его вообще трогать не стоило.

Добавлено через 9 минут
kmaffa, если сравнивать конкретно приведенный пример, то ускорить можно было почти в миллион раз и без расписывания подобного китайского кода. И кстати в вашем примере также ошибка, условия не надо менять было.

Добавлено через 12 минут
Кликните здесь для просмотра всего текста
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
using System;
using System.Diagnostics;
 
namespace ConsoleApplication71
{
    internal class Program
    {
        private static void Main()
        {
            double[,] arr = new double[100, 100];
            double[] v = new double[100];
            Random r = new Random();
            for (int i = 0; i < arr.GetLength(0); i++)
            {
                for (int j = 0; j < arr.GetLength(1); j++)
                    arr[i, j] = (double) r.Next(100000, 10000000)/1000;
                v[i] = (double) r.Next(100000, 10000000)/1000;
            }
            double result, result2;
            var span = Foo(arr, v, out result);
            var span2 = Foo2(arr, v, out result2);
            GC.Collect(2, GCCollectionMode.Forced);
            GC.WaitForPendingFinalizers();
            GC.Collect(2, GCCollectionMode.Forced);
 
            span = Foo(arr, v, out result);
            GC.Collect(2, GCCollectionMode.Forced);
            GC.WaitForPendingFinalizers();
            GC.Collect(2, GCCollectionMode.Forced);
 
            span2 = Foo2(arr, v, out result2);
 
            Console.WriteLine("Result 1 time = {0}, result = {1}", span, result);
            Console.WriteLine("Result 1 time = {0}, result = {1}", span2, result2);
            Console.ReadKey();
        }
 
        private static TimeSpan Foo(double[,] arr, double[] v, out double sum)
        {
            Stopwatch stopwatch = Stopwatch.StartNew();
            sum = 0;
            for (int k = 0; k < 100000; k++)
                for (int i = 0; i < arr.GetLength(0); i++)
                    for (int j = 0; j < arr.GetLength(1); j++)
                    {
                        sum += arr[i, j]*v[j];
                        j++;
                        sum += arr[i, j]*v[j];
                        j++;
                        sum += arr[i, j]*v[j];
                        j++;
                        sum += arr[i, j]*v[j];
                        j++;
                        sum += arr[i, j]*v[j];
                        j++;
                        sum += arr[i, j]*v[j];
                        j++;
                        sum += arr[i, j]*v[j];
                        j++;
                        sum += arr[i, j]*v[j];
                        j++;
                        sum += arr[i, j]*v[j];
                        j++;
                        sum += arr[i, j]*v[j];
                    }
            stopwatch.Stop();
            return stopwatch.Elapsed;
        }
 
        private static TimeSpan Foo2(double[,] arr, double[] v, out double sum)
        {
            Stopwatch stopwatch = Stopwatch.StartNew();
            sum = 0;
            for (int i = 0; i < arr.GetLength(0); i++)
            {
                for (int j = 0; j < arr.GetLength(1); j++)
                {
                    sum += arr[i, j]*v[j];
                }
            }
            sum *= 100000;
            stopwatch.Stop();
            return stopwatch.Elapsed;
        }
    }
}

на моем компе ваш вариант: 00:05:29.1117318
мой : 00:00:00.0053774
1
338 / 327 / 154
Регистрация: 29.10.2012
Сообщений: 949
15.12.2013, 13:54 26
По поводу операции деления в условии, так ее можно вынести за рамки цикла, а в условие подставлять уже вычисленную переменную .

Тяжелый случай.
Пробую объяснить еще раз.

Экономия происходит не на операциях вычисления, а на запуске цикла for!
Попробуйте ради интереса запустить пустой цикл 1'000 и 10'000 раз, у меня время в 9 отличается.
Миниатюры
Оптимизация кода с массивом  
0
Master of Orion
Эксперт .NET
6100 / 4956 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
15.12.2013, 14:01 27
kmaffa, это не оптимизации, а быдлокод какой-то. Пишите на С, подключайте - профит будет намного больше .Я уж молчу про то, что я сказал, никто внимания не обратил: мой код получает тот же ответ в миллион раз лучше. Вы будете для такого профита переписывать ВЕСЬ цикл вручную?
0
1195 / 588 / 88
Регистрация: 20.09.2012
Сообщений: 1,881
15.12.2013, 14:29 28
Цитата Сообщение от kmaffa Посмотреть сообщение
Попробуйте ради интереса запустить пустой цикл 1'000 и 10'000 раз, у меня время в 9 отличается.
Попробуйте ради интереса запустить не сферический пустой цикл, а выполнить 100000 умножений по 1 умножению в цикле http://ideone.com/PlXocg и по 10 (чтоб ""время на запуск цикла" не тратить) http://ideone.com/CVhY6o.
Где обещанная разница в разы?
И да, время в вашем "школьном примере" уменьшилось в 9.46 раз из-за грубейшей ощибки в коде.
1
338 / 327 / 154
Регистрация: 29.10.2012
Сообщений: 949
15.12.2013, 14:33 29
Не по теме:
Это Ваше мнение, спорить нет желания. Про применение других языков, почему тогда не машинные коды?
Было предложено как уменьшить время исполнения, без оценки качества кода. Все.
0
Master of Orion
Эксперт .NET
6100 / 4956 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
15.12.2013, 14:41 30
kmaffa, этот способ не уменьшает время выполнения кода, а скорее увеличивает, так как мешает компилятору оптимизировать цикл.
0
0 / 0 / 0
Регистрация: 25.07.2013
Сообщений: 163
16.12.2013, 10:50  [ТС] 31
Спасибо, я только не понял почему у вас исходный массив 100х100 и 100

Добавлено через 8 минут
А у меня Massiv1(2) - 1103x1103; VesPF- 104x104
0
208 / 164 / 29
Регистрация: 11.09.2013
Сообщений: 445
16.12.2013, 11:23 32
Вы каждый раз считаете новую сумму, вот и куча лишних операций (9900 на каждой итерации, т.е. можно ускорить примерно в 100 раз). предлагаю такой оптимизированный алгоритм:

после каждой итерации запоминаете сумму всего окна (она у Вас складывается в массив-результат, вот и хорошо) и первого стоблца/первой строки (если движетесь влево/вниз соответственно). на следующей итерации вместо того, чтобы вычислять заново, вычитаете из общей суммы окна сумму первого столбца, затем рассчитываете сумму очередного столбца и добавляете к общей сумме. результат - как раз значение суммы для "смещенного" окна. для работы алгоритма потребуется дополнительная память в виде массива, хранящего суммы отдельных строк/столбцов.

развивая идею, можно сначала свернуть всю матрицу для сумм столбцов/строк (используя эту же оптимизацию при их расчете), а затем по этим суммам рассчитать итоговую свертку, опять же не забывая о принципах работы с перекрывающимися интервалами
0
0 / 0 / 0
Регистрация: 25.07.2013
Сообщений: 163
16.12.2013, 14:30  [ТС] 33
Понял вашу идею, нужно попробовать, но сначала хочу разобраться с вариантом Psilona

Добавлено через 2 часа 54 минуты
Этот вариант подойдет только для суммы а у меня еще на фильтр умножается
0
1195 / 588 / 88
Регистрация: 20.09.2012
Сообщений: 1,881
16.12.2013, 14:48 34
Сделайте уже внешний цикл в своем исходном примере через Parallel.For и не мучайтесь.
0
0 / 0 / 0
Регистрация: 25.07.2013
Сообщений: 163
16.12.2013, 15:01  [ТС] 35
Все равно достаточно долго получается
0
1195 / 588 / 88
Регистрация: 20.09.2012
Сообщений: 1,881
16.12.2013, 15:10 36
Ну тогда CUDA (где то даже CUDA.Net светился)
0
Master of Orion
Эксперт .NET
6100 / 4956 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
16.12.2013, 16:35 37
pycture, а на AMD картах сосем лапу, получается?
sezada, я думал о подобном, но не придумал, как можно посчитать сумму, т.к. коэффициенты каждый раз различные.
0
208 / 164 / 29
Регистрация: 11.09.2013
Сообщений: 445
16.12.2013, 17:05 38
Psilon, свой класс тогда. идея все равно остается идеей, остальное - дело реализации
0
1195 / 588 / 88
Регистрация: 20.09.2012
Сообщений: 1,881
16.12.2013, 17:34 39
Цитата Сообщение от Psilon Посмотреть сообщение
pycture, а на AMD картах сосем лапу, получается?
А на AMD медитируем на OpenCL & AMD Accelerated Parallel Processing (APP) SDK.
0
0 / 0 / 0
Регистрация: 25.07.2013
Сообщений: 163
16.12.2013, 17:38  [ТС] 40
А если делаю на компьютере с nvidia а где использоваться будет может и ати стоять, так что не вариант
0
16.12.2013, 17:38
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
16.12.2013, 17:38
Помогаю со студенческими работами здесь

Оптимизация кода
Есть такая статья http://habrahabr.ru/post/165729/. Но в ней перечислена лишь малая часть возможных...

Оптимизация кода
Доброго времени суток. Прошу прощения, если буду ошибаться в терминах, но постараюсь правильно...

Оптимизация кода
Возможно ли заменить быдло-код проверки - пуста ли строка и появления картинки возле неё? ...

Оптимизация кода
Добрый вечер, господа! В данный момент я пишу тулзу для демонстрации алгоритмов оценки движения и...


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

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Новые блоги и статьи
Что такое HCL Notes и как с ним работать
InfoMaster 10.01.2025
HCL Notes (ранее известный как IBM Notes и Lotus Notes) представляет собой комплексную платформу для совместной работы и обмена информацией в корпоративной среде. Это многофункциональное решение,. . .
Как работать с Git из Windows и Visual Studio
InfoMaster 10.01.2025
Работа с Git в Windows Работа с Git в операционной системе Windows может быть осуществлена с помощью различных инструментов, каждый из которых обладает своими уникальными возможностями и. . .
Аналог оператора switch case в Python
InfoMaster 10.01.2025
Оператор switch case используется в программировании для выбора одного из нескольких вариантов исполнения кода. Однако в языке Python этот оператор отсутствует. Понимание аналогов switch case в. . .
Отличия абстрактного класса от интерфейса
InfoMaster 10.01.2025
В современной разработке программного обеспечения существуют два основных механизма реализации абстракции: абстрактные классы и интерфейсы. Эти инструменты, хотя и схожи в своей основной цели -. . .
Как работать в Git
InfoMaster 10.01.2025
Git — это одна из наиболее популярных систем контроля версий, которая активно используется разработчиками по всему миру. Она позволяет эффективно управлять изменениями в коде, координировать работу. . .
Реализация передвижения персонажа в Unity3d на C#
InfoMaster 10.01.2025
Реализация передвижения персонажа в Unity3D начинается с правильной настройки проекта. Этот этап критически важен для создания отзывчивого и плавного управления. Рассмотрим основные шаги для создания. . .
Docker: руководство для начинающих
InfoMaster 10.01.2025
В современном мире разработки программного обеспечения контейнеризация стала неотъемлемой частью процесса создания и развертывания приложений. Docker, как ведущая платформа контейнеризации, произвела. . .
Книги и учебные ресурсы по C#
InfoMaster 08.01.2025
Базовые учебники и руководства Одной из лучших книг для начинающих является "C# 10 и . NET 6 для начинающих" Эндрю Троелсена и Филиппа Джепикса . Книга последовательно раскрывает основные концепции. . .
Что такое NullReferenceEx­­­ception и как исправить?
InfoMaster 08.01.2025
NullReferenceException - одно из самых распространенных исключений, с которым сталкиваются разработчики на C#. Это исключение возникает при попытке обратиться к членам объекта (методам, свойствам или. . .
Что такое Null Pointer Exception (NPE) и как это исправить?
InfoMaster 08.01.2025
Null Pointer Exception (NPE) - это одно из самых распространенных исключений в Java, которое возникает при попытке использовать ссылку на объект, значение которой равно null. Это исключение относится. . .
Русский язык в консоли C++
InfoMaster 08.01.2025
При разработке программ на C++ одной из частых проблем, с которой сталкиваются русскоязычные программисты, является корректное отображение кириллицы в консольных приложениях. Эта проблема особенно. . .
Telegram бот на C#
InfoMaster 08.01.2025
Разработка ботов для Telegram стала неотъемлемой частью современной экосистемы мессенджеров. C# предоставляет мощный и удобный инструментарий для создания разнообразных ботов, от простых. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru