|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
27.06.2010, 14:28 | #1 |
Пользователь
Регистрация: 27.06.2010
Сообщений: 44
|
Вопросы в основном по оптимизации быстродействия.
Здравствуйте, новичок и пишу программу которая будет выполняться несколько дней. никаких понятий сложнее матриц в ней нет, так что хочется сделать ее как можно более быстрой, пусть и в ущерб удобочитаемости. В связи с этим несколько вопросов:
1)Слышал, что обращение к оперативке на порядок дольше, чем обращение к регистрам процессора. Работа с последними возможна на ассемблере. А на с++? 2) вроде бы есть несколько видов оперативной памяти по скорости работы. какие комманды типа сallock позволяют с ними работать? 3)насколько быстро работает reallock и правильно ли я понимаю, что лучше выделять сразу и много, чем немного и по частям? 4) Можно ли быстро узнать размер массива без записывания его размера в другую переменную? 5)Слышал, что вызов функции сам по себе занимает определенное время и в некоторых случаях чтобы этого избежать надо использовать некие макросы. что это значит? 6)я связанные списки делаю так: выделяю массив структур. в структуре две переменные-собственно значение и номер элемента в массиве в котором записан следующий по списку элемент.но ведь, если я понимаю правильно, каждый раз компьютеру приходится вычислять адрес следующего элемента. Как сделать связанный список более естественно, у меня не получается объявить структуру в которой будет указатель на нее же. типа Код:
Заранее спасибо за ответы! |
27.06.2010, 14:34 | #2 |
JAVA BEAN
Участник клуба
Регистрация: 22.04.2007
Сообщений: 1,329
|
А у меня всего один вопрос: ваша программа тормозит что ли? Зачем так со скоростью заморачиваться?
|
27.06.2010, 16:39 | #3 |
Пользователь
Регистрация: 27.06.2010
Сообщений: 44
|
Тормозит для нее не тот термин=) просто очень долго выполняется порядка 10-ти дней. и сократить это время хотя бы на пол дня (5%) уже было бы здорово
|
27.06.2010, 16:42 | #4 | ||||||
Старожил
Регистрация: 22.05.2007
Сообщений: 9,065
|
Цитата:
Цитата:
int i - создаёт переменную на стеке. int * i = new int; - в куче Цитата:
Цитата:
Код:
Цитата:
Цитата:
Код:
Вообще преждевременная оптимизация - зло. Сделайте хоть что-то хоть как-то, а уже если будет медленно работать, то искать узкие места в коде и переписывать их на ассемблере или еще какую оптимизацию проводить. На макросах я бы вообще оптимизировать не стал, да и на ассемблере. Судя по вопросам, с асмом не знакомы, а значит лучше оптимизатора код не напишите. Отдайте код компилятору и пусть он с ним делает то, что посчитает нужным. Современные оптимизаторы умеют функции самостоятельно делать inline или оставлять "нормальными" на основе времени исполнения тела функции. В общем, не заморачивайтесь раньше времени. Уверены, что нужно оптимизировать не алгоритм, а именно доступ к памяти, её выделение и т.п.? |
||||||
27.06.2010, 16:56 | #5 |
Не
Участник клуба
Регистрация: 29.10.2009
Сообщений: 1,456
|
это что же за программа такая, что работает 10 дней о_О. Сортировка матриц 1000 на 1000 методом пузырька?))
Простейшие программы выполняются доли секунд, че у вас за прога такая? Интересно посмотреть на исходник. Может там что-то типо Sleep(900000000); =)) Последний раз редактировалось NiCola999; 27.06.2010 в 17:05. |
27.06.2010, 17:15 | #6 |
JAVA BEAN
Участник клуба
Регистрация: 22.04.2007
Сообщений: 1,329
|
Если приспичило оптимизировать. То нужно начинать с самого медленного:
1) сеть, операции ввода/вывода, межпроцессовое взаимодействие 2) возможно что-то можно распараллелить 3) оптимизация циклов 4) оптимизация памяти 5) оптимизиция операций Не надо сразу лезть переписывать на асме. Вы рискуете заниматься секасом неделю и больше. А в итоге прироста в скорости не заметить. Компилятор ведь тоже не пальцем делан. Кстати, покопайтесь в его настройках. Может как оптимизируете самые тяжёлые участки, остальное уже нафиг не нужны. Что всё-таки за задача? Что она использует? Может мы чем поможем? Просто вы нам перечислили то, что нужно оптимизировать, если ничего не помогает. И таки да, может у вас просто алгоритм кривой. |
27.06.2010, 17:17 | #7 |
Участник клуба
Регистрация: 15.07.2008
Сообщений: 1,933
|
В общем согласен с pu4koff, попробуйте воспользоваться стандартной библиотекой, это будет проще и довольно быстро. Если есть возможность, то в 2010 студии, так как она там получше оптимизирована. Некоторую долю производительности можно выиграть за счёт ключей компилятора, например включить использование SSE. Безусловно компилировать окончательный результат нужно в Release-сборке. Из других оптимизаций, можно вручную разворачивать циклы, ну или писать так, чтобы их хорошо смог развернуть компилятор. Также можете воспользоваться профайлерами, дабы увидеть, на какую часть программы уходит больше всего процессорного времени и максимально оптимизировать этот участок
|
27.06.2010, 18:52 | #8 | ||||
Пользователь
Регистрация: 27.06.2010
Сообщений: 44
|
Цитата:
Цитата:
Цитата:
Код:
Цитата:
|
||||
27.06.2010, 19:07 | #9 |
Пользователь
Регистрация: 27.06.2010
Сообщений: 44
|
Опишу подробно задачу, может кто-то и сталкивался и подскажет.
Программа решает 10 000 различных систем уравнений с разряженными матрицами, а потом комбинирует решения. системы имеют вид Ax=kBx, где A и B разряженные матрицы(несиммитричные, но если ij элемент не равен нулю, то и ji тоже не равен нулю, хотя они и различные),x-искомый вектор решение, а k коэффициент, который тоже должен быть таким, чтобы уравнение решалось. В оригинальной программе (которая работает 10 дней) и k и решение ищутся как то при помощи последовательных приблежений используя умножение вектора на матрицу, что в разряженном случае довольно быстро, но сам поиск занимает жуткие 1.5 минуты каждый раз. мне не нравится эта идея, ведь если бы k было известно, то найти решение и точно можно очень быстро при помощи алгоритма гаусса, в котором, конечно, работа идет только с ненулевыми элементами. Разряженные матрица храняться в виде массива связанных списков. Для разряженных матриц можно составить алгоритм гаусса в котором после зануления каждого столбца надо переставлять некоторые строки местами так, чтобы количество образующихся ненулевых элементов после очереднго зануления столбца было минимальным. причем для всех 10000 матриц этот алгоритм один и тот же. составить его надо один единственный раз. проблема найти k для каждого случая. я не нашел ничего лучше чем найти определитель от A-kB в виде полинома от k, а потом найти его нули. определитель раскрываю рекурсией - разложением по строке в виде суммы определителей n-1 го порядка .причем каждый раз выбираю такую строку, что бы в ней было поменьше элементов+ надо некоторые результаты запонимать, так как некоторые из подопределителей равны и не стоит их 2 раза вычислять+надо запонимать строки и столбцы, которые вычеркнул так что постоянно есть массивы которые ты все время перезаписываешь, поэтому работа с памятью очень критична. последовательность строк по которым расклыдваешь тоже одна для всех матриц. Вот это меня и привлекает. если получится сделать так, чтобы нахождение k раскрытием определителя + решение алгоритмом гаусса конечной системы будет занимать меньше чем 1.5 минуты, для матриц ранга примерно 10 000 (хотя ненулевых элементов всего лишь 16 в каждой строке), то буду считать миссию выполненой. спасибо за ответы! Последний раз редактировалось Morkonwen; 27.06.2010 в 19:15. |
27.06.2010, 21:01 | #10 |
Старожил
Регистрация: 22.05.2007
Сообщений: 9,065
|
Операции с матрицами как правило хорошо параллелятся (см. OpenMP)
Так же возможно есть смысл посмотреть на CUDA. В плане хранения данных я бы не заморачивался и использовал готовые классы из STL (vector, list). Тут вся загвоздка идёт в алгоритмах поиска решения. Учитывая, что строки нужно менять местами, то матрицу лучше делать как список строк. У меня с математикой плохо, поэтому более конкретно тут ничего не скажу. Несколько раз встретилось упоминание о нулевых и ненулевых элементах. Вероятно, тут вырисовывается проверка на равенство нулю. Эта мелочная проверка в цикле вырастает в достаточно высокую лишнюю нагрузку на процессор. Тут уже нужно смотреть как эту проверку можно выкинуть из цикла или вообще, может как-то помечать строки из нулей, если их будет много, чтобы впоследствии не обрабатывать. В ассемблер даже не лезьте, оптимизатор это сделает лучше, они и циклы умеют разворачивать и много всего интересного. Я бы сначала реализовал всё как получится, а потом профайлером выискивал узкие места и думал над их оптимизацией. И посмотрите еще на многообразие алгоритмов сортировки и поиска и преимущества каждого из них. Мне они в своё время достаточно наглядно показали примерный ход мышления в процессе оптимизации алгоритмов. |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Вопрос быстродействия | _Денис | C++ Builder | 1 | 14.11.2009 17:00 |
Создание логических разделов на основном | Kreadlling | Операционные системы общие вопросы | 3 | 12.09.2009 14:39 |
Кто что в основном программирует | Rekky | Свободное общение | 24 | 05.05.2009 16:25 |
Вопросы о оптимизации работы с СУБД | Stilet | БД в Delphi | 8 | 21.07.2008 11:29 |
Вопросы по оптимизации скорости | Иллидан | Общие вопросы Delphi | 9 | 11.07.2008 23:46 |