Как ускорить выполнение программы? |
Прежде чем задать вопрос, смотрите FAQ.
Рекомендуем загрузить DRKB.
Как ускорить выполнение программы? |
SAB |
10.10.2003 10:50
Сообщение
#1
|
Новичок Группа: Пользователи Сообщений: 23 Репутация: 0 |
В программе есть цикл, обрабатывающий данные из файла:
Код repeat Read(f_in,d); SinCos(j*2*pi*k/N,s1,c1); A1:=d.Zn*c1; SA:=SA+A1; B1:=d.Zn*s1; SB:=SB+B1; k:=k+1; until k>N-1; В файле более 50000 значений. Такой цикл выполняется несколько томительных секунд. Может кто знает: как ускорить его выполнение? Сообщение отредактировано: volvo - 5.01.2005 14:03 -------------------- Человек должен думать, а компьютер работать.
|
Nightmare |
10.10.2003 13:24
Сообщение
#2
|
Новичок Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация: 1 |
Информации, конечно менее, чем необходимо, но попробуем разобраться.
1. Код A1:=d.Zn*c1; SA:=SA+A1; заменить на Код SA := SA + d.Zn*c1; 2. Код k:=k+1; заменить на Код Inc(k); Это так, навскидку. Далее: здесь самая медленная операция - чтение из типизованного файла одного значения, очевидно типа Record. Если есть возможность, нужно убрать это из цикла. Обычно, если идет неоднократное обращение к данным, разделяют загрузку и обработку, но мне почему-то кажется, что здесь это неприменимо. А посему придётся или смириться или давать больше информации. Сообщение отредактировано: volvo - 5.01.2005 14:04 |
SAB |
11.10.2003 6:07
Сообщение
#3
|
Новичок Группа: Пользователи Сообщений: 23 Репутация: 0 |
Из файла читается запись (record), состоящая из двух полей типа real. Предварительное копирование данных из файла в массив, а затем работа с этим массивом не помогают. Правда я делал массив того же типа, что и файл, то есть record'а.
Добавлено (11.10.03 5:11): А как выполняется inc(k)? Может там внутри все равно преобразуется в k:=k+1, только выполняется еще медленнее. -------------------- Человек должен думать, а компьютер работать.
|
___ALex___ |
11.10.2003 8:16
Сообщение
#4
|
Бывалый Группа: Пользователи Сообщений: 282 Репутация: 0 |
SAB
в паскале если не ошибаюсь n := n + 1 реализуется инструкцией ADD, а Inc(n) инстр-ей INC в Delphi же без разницы, разве что Inc-ом получается компактнее а вообще надо оптимизировать не цикл, а алгоритм Добавлено (11.10.03 7:38): в турбо Паскале 7.0 Inc(n) компилится в INC BYTE PTR [PROGRAM.N] n := n + 1 в MOV AL, [PROGRAM.N] XOR AH, AH INC AX MOV [PROGRAM.N], AL (n типа Byte) делай выводы... P.S. я был лучшего мнения о паскалевском компиляторе... |
Nightmare |
11.10.2003 10:14
Сообщение
#5
|
Новичок Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация: 1 |
Цитата Из файла читается запись (record), состоящая из двух полей типа real. Предварительное копирование данных из файла в массив, а затем работа с этим массивом не помогают. Я повторюсь: Если ты разделяешь загрузку и обработку, то обработка выполняется быстрее, поскольку память, по определению, быстрее диска. Поэтому если заменить чтение из файла на доступ к массиву, время выполнения этого цикла ощутимо уменьшится. |
zx1024 |
11.10.2003 10:20
Сообщение
#6
|
Пионер Группа: Пользователи Сообщений: 119 Пол: Мужской Репутация: 0 |
Ничего странного.
Inc (n) - процедура. n + 1 - функция и может использоваться в выражениях. Чтобы не разбирать каждое выражение, сделали стандарт, который подходит для всех (или многих) вариантов. |
___ALex___ |
11.10.2003 20:48
Сообщение
#7
|
Бывалый Группа: Пользователи Сообщений: 282 Репутация: 0 |
zx1024
охинея Inc - это никакая не процедура, это макрос такой было бы большой глупостью делать её процедурой, знающие люди бы её никогда не стали пользоваться |
zx1024 |
12.10.2003 19:40
Сообщение
#8
|
Пионер Группа: Пользователи Сообщений: 119 Пол: Мужской Репутация: 0 |
___ALex___
А что ж ты не написал, что n+1 не функция? До конца не дочитал? Термины "процедера" и "функция" я применил для большей понятности СМЫСЛА, на который и следовало бы обратить внимание. (Здесь имеется ввиду отличие процедуры от функции - возможность применение последней в выражениях). |
___ALex___ |
12.10.2003 20:49
Сообщение
#9
|
Бывалый Группа: Пользователи Сообщений: 282 Репутация: 0 |
zx1024
это не ф-ия - это выражение |
SAB |
13.10.2003 8:11
Сообщение
#10
|
Новичок Группа: Пользователи Сообщений: 23 Репутация: 0 |
Цитата Я повторюсь: Если ты разделяешь загрузку и обработку, то обработка выполняется быстрее, поскольку память, по определению, быстрее диска. Поэтому если заменить чтение из файла на доступ к массиву, время выполнения этого цикла ощутимо уменьшится. Дело всё в том, что Виндуза всё равно загружает обрабатываемые файлы впамять, поэтому получается не фиг быстро. -------------------- Человек должен думать, а компьютер работать.
|
zx1024 |
13.10.2003 8:34
Сообщение
#11
|
Пионер Группа: Пользователи Сообщений: 119 Пол: Мужской Репутация: 0 |
Вчитайся в текст.
Если ты разделяешь загрузку и обработку, то ОБРАБОТКА выполняется быстрее. Всё вместе (загрузка и обработка) будет идти с той же скоростью. Это применимо, когда обработка тех же данных происходит неоднократно. Для данного примера, если сущ-ет j (возможно, даже k или N, целого кода то нет), для которой повторно читается одна и та же запись из файла, то есть смысл в разделении. Если нет, то перепиши всё на асме - по крайней мере будешь уверен, что быстрее уже не куда. |
trminator |
13.10.2003 15:10
Сообщение
#12
|
Четыре квадратика Группа: Пользователи Сообщений: 579 Пол: Мужской Репутация: 4 |
а pi... это ж вроде функция. Может, сделать ее константой? А то не получается ли так, что мы 50000 раз вычисляем значение Пи
-------------------- Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала |
mj |
15.10.2003 13:27
Сообщение
#13
|
Adminь Группа: Администраторы Сообщений: 803 Пол: Мужской Реальное имя: Евгений Репутация: 5 |
Виндоза не кеширует файлы по умолчанию, как это некоторые думают...
и даже в 32 битных приложениях я читаю как минимум порциями по 64 Kb, а если это же читать по 10 байт, будет в 100 раз медленнее... pi это константа... SinCos(j*2*pi*k/N,s1,c1); можно упростить до SinCos(ес*k,s1,c1); ec вычесляется за пределами цыкла и равна она будет j*2*pi/N... Если так упростить, будет выполнятся кк минимум в 2 раза быстрее... |
Vit |
17.10.2003 17:27
Сообщение
#14
|
Бывалый Группа: Пользователи Сообщений: 156 Пол: Мужской Репутация: 0 |
Загрузить весь файл в поток, а затем работать - если дашь файл - я напишу. Время тратится здесь не на вычисление а на чтение из файла
-------------------- With the best regards Vit
Все всегда уезжают навсегда. Вернуться невозможно-вместо нас всегда возвращается кто-то другой |
SAB |
18.10.2003 5:38
Сообщение
#15
|
Новичок Группа: Пользователи Сообщений: 23 Репутация: 0 |
Вообще-то это кусок из программы, выполняющей преобразование Фурье для некоторой дискретной функции (разложение на гармонические составляющие, разложение сигнала в спектр и т.д. кому как больше нравится). В данном случае оно выполняется в лоб. Но может кто знает алгоритм "быстрого преобразования Фурье". Говорят есть такое. P.S. Кстати насчёт представления j*2*pi/N в виде константы, вычисляемой вне цикла - очень интересная мысль, и как я сам не допёр. Сообщение отредактировано: volvo - 5.01.2005 14:05 -------------------- Человек должен думать, а компьютер работать.
|
Vit |
20.10.2003 19:58
Сообщение
#16
|
Бывалый Группа: Пользователи Сообщений: 156 Пол: Мужской Репутация: 0 |
Привожу FFT-алгоритм, позволяющий оперировать 256 точками данных примерно за 0.008 секунд на P66 (с 72MB, YMMV). Создан на Delphi.
Данный алгоритм я воспроизвел где-то около года назад. Вероятно он не самый оптимальный, но для повышения скорости расчета наверняка потребуются более мощное аппаратное обеспечение. Но я не думаю что алгоритм слишком плох, в нем заложено немало математических трюков. Имеется некоторое количество рекурсий, но они занимается не копированием данных, а манипуляциями с указателями, если у нас есть массив размером N = 2^d, то глубина рекурсии составит всего d. Возможно имело бы смысл применить развертывающуюся рекурсию, но не пока не ясно, поможет ли ее применение в данном алгоритме. (Но вероятно мы смогли бы достаточно легко получить надежную математическую модель, развертывая в рекурсии один или два нижних слоя, то есть проще говоря: if Depth < 2 then {производим какие-либо действия} вместо текущего 'if Depth = 0 then...' Это должно устранить непродуктивные вызовы функций, что несомненно хорошо в то время, пока развертывающая рекурсия работает с ресурсами.) Имеется поиск с применением таблиц синусов и косинусов; здесь использован метод золотой середины: данный алгоритм весьма трудоемок, но дает отличные результаты при использовании малых и средних массивов. Вероятно в машине с большим объемом оперативной памяти следует использовать VirtualAlloc(... PAGE_NOCACHE) для Src, Dest и таблиц поиска. Если кто-либо обнаружит неверную на ваш взгляд или просто непонятную в данном совете функцию пожалуйста сообщите мне об этом. Что делает данная технология вкратце. Имеется несколько FFT, образующих 'комплексный FT', который понимает и о котором заботится моя технология. Это означает, что если N = 2^d, Src^ и Dest^ образуют массив из N TComplexes, происходит вызов FFT(d, Src, Dest) , далее заполняем Dest с применением 'комплексного FT' после того, как результат вызова Dest^[j] будет равен 1/sqrt(N) * Sum(k=0.. N - 1 ; EiT(2*Pi(j*k/N)) * Src^[k]) , где EiT(t) = cos(t) + i sin(t) . То есть, стандартное преобразование Фурье. Публикую две версии: в первой версии я использую TComplex с функциями для работы с комплексными числами. Во второй версии все числа реальные - вместо массивов Src и Dest мы используем массивы реальных чисел SrcR, SrcI, DestR, DestI (в блоке вычислений реальных чисел), и вызовы всех функций осуществляются линейно. Первая версия достаточна легка в реализации, зато вторая - значительно быстрее. (Обе версии оперируют 'комплексными FFT'.) Технология работы была опробована на алгоритме Plancherel (также известным как Parseval). Обе версии работоспособны, btw: если это не работает у вас - значит я что-то выбросил вместе со своими глупыми коментариями :-) Итак, сложная версия: cplx.pas ( 1.71 килобайт ) Кол-во скачиваний: 387 cplxfft1.pas ( 1.91 килобайт ) Кол-во скачиваний: 426 DemoForm.pas ( 1.63 килобайт ) Кол-во скачиваний: 425 **** Версия для работы с реальными числами: cplxfft2.pas ( 2.46 килобайт ) Кол-во скачиваний: 413 demofrm.pas ( 1.99 килобайт ) Кол-во скачиваний: 401 Взято с www.delphiworld.narod.ru -------------------- With the best regards Vit
Все всегда уезжают навсегда. Вернуться невозможно-вместо нас всегда возвращается кто-то другой |
SAB |
30.10.2003 11:40
Сообщение
#17
|
Новичок Группа: Пользователи Сообщений: 23 Репутация: 0 |
Vit
Пограммы конечно интересные. Особенно идея насчет работы с указателями. Только уж больно в них математика сложная. Моя программа попроще будет, хоть и работает меделеннее. Кстати за счет упрощения цикла и пожертвовав интерфейсныим возможностями её удалось ускорить в 8 раз. -------------------- Человек должен думать, а компьютер работать.
|
Текстовая версия | 21.06.2024 16:03 |