Как ускорить выполнение программы? Опции

[SAB]

В программе есть цикл, обрабатывающий данные из файла:

Код

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 18:03

[Nightmare]

Информации, конечно менее, чем необходимо, но попробуем разобраться.
1.

Код

A1:=d.Zn*c1;
SA:=SA+A1;

заменить на

Код

SA := SA + d.Zn*c1;

2.

Код

k:=k+1;

заменить на

Код

Inc(k);

Это так, навскидку.
Далее: здесь самая медленная операция - чтение из типизованного файла одного значения, очевидно типа Record. Если есть возможность, нужно убрать это из цикла.
Обычно, если идет неоднократное обращение к данным, разделяют загрузку и обработку, но мне почему-то кажется, что здесь это неприменимо. А посему придётся или смириться или давать больше информации.

Сообщение отредактировано: volvo - 5.01.2005 18:04

[SAB]

Из файла читается запись (record), состоящая из двух полей типа real. Предварительное копирование данных из файла в массив, а затем работа с этим массивом не помогают. Правда я делал массив того же типа, что и файл, то есть record'а.

Добавлено (11.10.03 5:11):
А как выполняется inc(k)? Может там внутри все равно преобразуется в k:=k+1, только выполняется еще медленнее.

[___ALex___]

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]

Из файла читается запись (record), состоящая из двух полей типа real. Предварительное копирование данных из файла в массив, а затем работа с этим массивом не помогают.

Я повторюсь:
Если ты разделяешь загрузку и обработку, то обработка выполняется быстрее, поскольку память, по определению, быстрее диска. Поэтому если заменить чтение из файла  на доступ к массиву, время выполнения этого цикла ощутимо уменьшится.

[zx1024]

Ничего странного.
Inc (n) - процедура.
n + 1 - функция и может использоваться в выражениях. Чтобы не разбирать каждое выражение, сделали стандарт, который подходит для всех (или многих) вариантов.

[___ALex___]

zx1024
охинея
Inc - это никакая не процедура, это макрос такой
было бы большой глупостью делать её процедурой, знающие люди бы её никогда не стали пользоваться

[zx1024]

___ALex___
А что ж ты не написал, что n+1 не функция?
До конца не дочитал?
Термины "процедера" и "функция" я применил для большей понятности СМЫСЛА, на который и следовало бы обратить внимание. (Здесь имеется ввиду отличие процедуры от функции - возможность применение последней в выражениях).

[___ALex___]

zx1024
это не ф-ия - это выражение

[SAB]

Я повторюсь:
Если ты разделяешь загрузку и обработку, то обработка выполняется быстрее, поскольку память, по определению, быстрее диска. Поэтому если заменить чтение из файла  на доступ к массиву, время выполнения этого цикла ощутимо уменьшится.

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

[zx1024]

Вчитайся в текст.
Если ты разделяешь загрузку и обработку, то ОБРАБОТКА выполняется быстрее.
Всё вместе (загрузка и обработка) будет идти с той же скоростью.
Это применимо, когда обработка тех же данных происходит неоднократно.
Для данного примера, если сущ-ет j (возможно, даже k или N, целого кода то нет), для которой повторно читается одна и та же запись из файла, то есть смысл в разделении. Если нет, то перепиши всё на асме - по крайней мере будешь уверен, что быстрее уже не куда.

[trminator]

а pi... это ж вроде функция. Может, сделать ее константой? А то не получается ли так, что мы 50000 раз вычисляем значение Пи

[mj]

Виндоза не кеширует файлы по умолчанию, как это некоторые думают...
и даже в 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]

Загрузить весь файл в поток, а затем работать - если дашь файл - я напишу. Время тратится здесь не на вычисление а на чтение из файла

[SAB]

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

P.S. Кстати насчёт представления j*2*pi/N в виде константы, вычисляемой вне цикла - очень интересная мысль, и как я сам не допёр.

Сообщение отредактировано: volvo - 5.01.2005 18:05

[Vit]

Привожу 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 килобайт ) Кол-во скачиваний: 601

 cplxfft1.pas ( 1.91 килобайт ) Кол-во скачиваний: 613

 DemoForm.pas ( 1.63 килобайт ) Кол-во скачиваний: 596



**** Версия для работы с реальными числами:

 cplxfft2.pas ( 2.46 килобайт ) Кол-во скачиваний: 607

 demofrm.pas ( 1.99 килобайт ) Кол-во скачиваний: 603


Взято с www.delphiworld.narod.ru

[SAB]

Vit
Пограммы конечно интересные. Особенно идея насчет работы с указателями. Только уж больно в них математика сложная. Моя программа попроще будет, хоть и работает меделеннее. Кстати за счет упрощения цикла и пожертвовав интерфейсныим возможностями её удалось ускорить в 8 раз.