IPB
ЛогинПароль:

> Внимание! Действует предмодерация

Подраздел FAQ (ЧАВО, ЧАстые ВОпросы) предназначен для размещения готовых рабочих программ, реализаций алгоритмов. Это нечто вроде справочника, он наполнялся в течение 2000х годов. Ваши вопросы, особенно просьбы решить задачу, не пройдут предмодерацию. Те, кто наполнял раздел, уже не заходят на форум, а с теми, кто на форуме сейчас, лучше начинать общение в других разделах. В частности, решение задач — здесь.

3 страниц V  1 2 3 >  
 Ответить  Открыть новую тему 
> Улучшение кода, Уменьшение времени работы программ
сообщение
Сообщение #1


Ищущий истину
******

Группа: Пользователи
Сообщений: 4 825
Пол: Мужской
Реальное имя: Олег

Репутация: -  45  +


Быстрые циклы.

Всего тестировалось 4 конструкции:
  • "FOR ... TO ... Do...",
  • "WHILE... do...",
  • "REPEAT ... until ...",
  • " If... Then GOTO ..."

Проведение теста:
сортировка массива (array[1..20] of integer) методом пузырька.
Всего было проведено 30 тестов :
10 c n= 10^4;
10 c n= 10^5;
10 c n= 10^6;
и один тест с n=10^7 (один, т.к. с увеличением степени n на 1, время проведения теста увеличивается соответственно в 10 раз)


Результат:
Во всех случаях (каждый тест - новый массив) самой быстрой конструкцией оказалась "While ... do...", следом за ней "If ... then Goto..."


Прикрепленные файлы
Прикрепленный файл  test.pas ( 1.76 килобайт ) Кол-во скачиваний: 441


--------------------
Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Adminь
****

Группа: Пользователи
Сообщений: 803
Пол: Мужской
Реальное имя: Евгений

Репутация: -  5  +


на процессорах P2 и ниже
FOR быстрее чем WHILE должно работать на новых процах наоборот,
это связано с внутренней конструкцией процессора.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Прогрессор
****

Группа: Пользователи
Сообщений: 602
Пол: Мужской
Реальное имя: Михаил

Репутация: -  9  +


И Да ЗдравствуетИтерация! Пример: старая добрая задачка о Ханойской башне (нерекурсивный вариант).

Сообщение отредактировано: Atos -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Четыре квадратика
****

Группа: Пользователи
Сообщений: 579
Пол: Мужской

Репутация: -  4  +


Ускорение вычислений mod

Програма считает 50 - 55 секунд (!), до 8 000 000 экспериментов.
Вычисления типа:
c0 := (a * c0 + B) mod m

где m = 2^24 (генератор случайных чисел, если кому интересно)

Код быстрее:
c0 := (a * c0 + B) and (m - 1)


Ускорение -- более чем в 50 раз. Вот так... Прога работает около секунды - полутора.
Когда берем остаток от деления (на степень двойки!), фактически, мы просто оставляем последние m-1 бит числа. А это можно сделать и and'ом


--------------------
Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Бывалый
***

Группа: Пользователи
Сообщений: 180
Пол: Мужской

Репутация: -  2  +


Деление на степень двойки

Аналогично быстрое деление на степень двойки - shr, а умножение - shl

если мне не изменяет память,
на команду DIV (деление) 486-е процы тратили до 70-ти тактов!
(для сравнения - битовые команды типа AND/OR и сдвиги выполняются за 1-2 такта)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Бывалый
***

Группа: Пользователи
Сообщений: 180
Пол: Мужской

Репутация: -  2  +


Разворачивание циклов. -=loops unrolling=-

Один из методов оптимизации больших циклов - loops unrolling - "разворачивание"... тело цикла можно скопировать два/четыре раза, уменьшив во столько же раз кол-во итераций... глядишь, процессору удасться их распараллелить, да и на jump-ы время меньше тратится...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Четыре квадратика
****

Группа: Пользователи
Сообщений: 579
Пол: Мужской

Репутация: -  4  +


P@sh@, сомневаюсь, что игра стОит свеч. Хотя попробовать можно... на jump'ы тратится не только время на их выполнение, если еще учесть, что может неверно сработать "предсказание" процессором, какую команду пускать на конвейер. Хотя это уже оптимизация будет не "качественная", а какая-то "количественная"...

ЗЫ: я ее все равно уже сдал...


--------------------
Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Ищущий истину
******

Группа: Пользователи
Сообщений: 4 825
Пол: Мужской
Реальное имя: Олег

Репутация: -  45  +


Процедуры FAR

Все процедуры в модулях, пишутся в расчете на дальнюю модель памяти.
При этом тратится 1 байт и несколько милисекунд на запуск такой процедуры.


--------------------
Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






Специально для Oleg_Z:
В BP есть такая возможность при компиляции модуля указать, что тот может быть оверлейным ({$O+}). Тогда в проге можно будет использовать его таким образом:
[PROGRAM][OVERLAY BUFFER]
[PROGRAM][UNIT1][Y BUFFER]
[PROGRAM][U2][RLAY BUFFER]
Т. е. модули остаются неприкомпиленными, а извращёнными (компилятся в .ovr, вроде) и их надо тягать с собой (как .bgi), а когда надо вызвать чего-нибудь, то прога подгружает нужный модуль в память и работает с ним. Управлять буфером можно функциями из модуля Overlay.
Короче отстой полный.

Цитата
Ну это не разработки борланда, это и в асме есть.

Покажешь где?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гость






Описалова в книгах достаточно. Посмотрю чего - завтра отпишу. На самом деле, если в разных модулях находятся 2 частовызываемые функции, то на загрузке/выгрузке потеря будет...
А кто автор вот этой загадочной книги по Asm'у?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Четыре квадратика
****

Группа: Пользователи
Сообщений: 579
Пол: Мужской

Репутация: -  4  +


Как нам говорили на лекции по ОС, оверлей - аналог страничной организации памяти, когда неиспользуемые страницы можно скинуть на диск (swap, pagefile) Так что не совсем dll


--------------------
Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Четыре квадратика
****

Группа: Пользователи
Сообщений: 579
Пол: Мужской

Репутация: -  4  +


А про использование AssignCRT вместо Assign для записи в текстовый файл уже говорили? smile.gif по Фаронову, наного быстрее


--------------------
Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Гость






Ну и зкономии ради можно (олимпиадныю трюк) воспользоваться
Assing(Input,'In.Txt');
Reset(Input);
Assign(Output,'Out.Txt');
ReWrite(Output);
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Ищущий истину
******

Группа: Пользователи
Сообщений: 4 825
Пол: Мужской
Реальное имя: Олег

Репутация: -  45  +


Просто есть файловая переменная Input и output только это не ускорит и не уменьшит размера.


--------------------
Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Четыре квадратика
****

Группа: Пользователи
Сообщений: 579
Пол: Мужской

Репутация: -  4  +


Про сортировку. Понятно, что пузырек и компания никуда не годятся smile.gif хотя если нужно отсортировать десяток элементов, самое оно smile.gif

Есть распространенное мнение, что лучшая сортировка -- quicksort. Да, лучшая. В среднем (O(n*log(n))). В худшем случае ее время -- O(n*n). Если вам нужна гарантия, что ваша сортировка ВСЕГДА выполняется за нлогн, ИМХО, лучше выкинуть быструю сортировку.

Кстати, помогите идентифицировать сортировку. Кажется, это -- пирамидальная:
Код

procedure swap (i, j : word);
var t : integer;
begin
    t := a[i]; a[i] := a[j]; a[j] := t;
end;

procedure sort (n, t : word);
begin
    while ((t shl 1+1 <= n) and (a[t shl 1+1] > a[t]) or
        (t shl 1 <= n) and (a[t shl 1] > a[t])) do
     if (a[t shl 1+1] >= a[t shl 1]) and (t shl 1 +1 <= n) then begin
       swap (t shl 1 +1, t); t := t shl 1+1;
   end else begin
       swap (t shl 1, t); t := t shl 1;
   end;
end;

Раскопал ее в развалинах своего винта. Она работает smile.gif


--------------------
Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Гость






trminator, да похоже на пирамидку.
Oleg_Z, использование Input и OutPut действительно ничего не ускорят, но вот размер на объявлении двух новых ФАЙЛОВЫХ переменных сэкономит.
Oleg_Z, извиняй, что так завис с Overlay'ем - малой мой книгу мне только сегодня выделил, а сутра мне не до этого было. Пока чай пил я пролистал главу про эту фигню и нашёл кое-что интересное. Во-первых .Ovr могут прилинковываться к EXE-шнику, но загружаться только по требованию,а во-вторых стандартный модуль Overlay умеет работать с EMS! Т. е. при загрузке программы все модули можно закачать в EMS, а оттуда по требованию скидывать в обычную память и работать с ними.
Кратко о использовании. Оверлейным может быть только модуль откомпилированный с {$O+}, а так же ВСЕ(!) экспортируемые функции должны быть FAR. Т. е. проще дописать и {$F+}. Из стандартных оверлейными, вроде, могут быть только DOS и Printer. Как подключить такой модуль? Вот так:
Код

Uses MyOvrU;
{$O MyOvrU}

Но проблема в том, что НИКАКОЙ инициализации не может быть в таких модулях до инициализации менеджера оверлеев. Но, вобщем, и это не проблема. Давай вспомним, что происходит при запуске такой вот программы:
Код

Uses U1,U2,U3;
Begin
End.

Вызывается стандартный загрузчик Pascal'я, который дописывается в прогу как Entry Point, а затем поочерёдно запускаются блоки инициализации модулей U1,U2,U3 и именно в этом(!) порядке. Затем выполняется Begin-End, после чего управление переходит к Pascal'евском "завершителю". Так вот, если применить такой вот нехитрый трюк и создать модуль типа OvrInit, в котором будет инициализироваться менеджер оверлеев, а в программе записать его первым в списке используемых Unit'ов, то проблема инициализации снимается. Вот так.
Это всё так, на словах, без единой функции модуля Overlay. Не буду их упоминать, т. к. не уверен, что вспомню в точности имена и параметры, но общий принцип таков. Сегодня вечером точно отпишу.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Четыре квадратика
****

Группа: Пользователи
Сообщений: 579
Пол: Мужской

Репутация: -  4  +


Так... я не закончил про сортировки smile.gif
ИМХО, использовать, так пирамиду. Мои аргументы:
* Обратите внимание на размер той процедуры, что я привел (я уже уверен, что это -- пирамида =). И сравните ее с размером quicksort'a. Что проще написАть по памяти? smile.gif
* Как я уже говорил, неплохо бы иметь гарантию, что ваша сортировка выполняется за n*log(n), а не за великий и ужастный n*n Особенно если вы участвуете в олимпиадах. И особенно если задачи составлял тов. Лопатин. Он любит quicksort smile.gif

Ну и недостатки у пирамидки тоже есть smile.gif как же без них. В среднем quicksort все же быстрее -- внутренний цикл у него самый быстрый.


--------------------
Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Гость






trminator, по памяти, может, её и проще, но на рефлексах пишется и пузырёк и QuickSort smile.gif
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Гость






Oleg_Z, вот чего у меня в книге есть:
Функции Overlay'а:
OvrClearBuf - очищает буфер smile.gif
OvrGetBuf - возвр. размер буфера
OvrGetRetry - возвр. размер области испытаний (что за она не въехал, но по-умолчанию тут 0).
OvrInit - инициализирует систему Overla'ев и открывает оверлейный файл.
OvrInitEMS - загружает оверлейный файл в память EMS, если это возможно.
OvrSetBuf - устанавливает размер буфера
OvrSetRetry - догадайся сам, хотя не стоит smile.gif
Так же тут описана переменная OvrResult:Integer, которая может быть
OvrOK(0) - всё пучком
OvrError(-1) - что-то не пучком
OvrNotFound(-2) - файл не нашёл
OvrNoMemory(-3) - досадно как...
OvrIOError(-4) - файл есть, атолку нет
ObrNoEMSDriver(-5) - и такое бывает
OvrNoEMSMemory(-6) - а драйвер тогда зачем?
Ещё в модуле есть возможность переопределить такую фигню:
Type
OvrReadFunc=Function(OvrSeg:Word):Integeer;
Var
OvrReadBuf:OvrReadFunc; { *** }
OvrFileMode:Byte;

Но зачем и что тут к чему я тоже что-то не того...
А ещё в System есть стадо переменных предназначенных для Overlay'а:
OvrCodeList:Word=0 - список сегментов кода
OvrDebugPtr:Pointer=Nil - для отладчика
OvrDOSHandle:Word=0 - для админа (скорее всего Handle файла)
OvrEMSHandle:Word=0 - Handle EMS-куска
OvrHeapEnd,OvrHeadOrg,OvrHeadPtr,OvrHeapSize:Word=0 - это если без EMS
OvrLoadList:Word=0 - "используется администратором оверлеев". И без коментариев.
Потешное замечание сделано в этой книге: не надо размещать в Overla'ях обработчики прерываний и данные для RegisterBGIDriver и RegisterBGIFont smile.gif

Далее идёт пример:
{$M 16384,65536,655360}
{$D-,F+}
{D- для того, чтобы Deug-Data не скидывались в Exe-шник. Тогда можно .Ovr приаттачить к самому .Exe}

Uses Crt,Overlay,Ovr_Init,Ovr1,Ovr2;

Var
 ch:Char;

Procedure UseOverlay;
Begin
 OutPut1 {Из Ovr1}
End;

Begin
 Repeat
   clrScr;
   Write('Press any key to start ovrlays or ESC to quit');
   ch:=ReadKey;
   WriteLn;
   If ch<>#27 Then
     UseOverlay
 Until ch=#27
End.


Unit OvrInit;
Interface
Implementation
Uses Overlay,Crt;
CONST
 OvrBufSize=100000;
Begin
 ClrScr;
 OvrInit(ParamStr(0)); {!!! Предполагается, что .Ovr прилеплен к .Exe}
 If OvrResult<>OvrOk Then
 Begin
   WriteLn('ERROR!!!);
   Halt
 End;
 OvrInitEMS;
 If OvrResult<>OvrOk Then
 Begin
   WriteLn('ERROR!!!);
   Halt
 End;
 OvrSetBuf(OvrBufSize);
 If OvrResult<>OvrOk Then
 Begin
   WriteLn('ERROR!!!);
   Halt
 End;
 OvrSetRetry(OvrBufSize Div 3) {Div 3 - оптимальный вариант, но всё ещё не понятно, что за область такая}
End.

Далее берём и Build'им саму прогу. А потом выходим из BP и пишем в cmd Copy /B Proga.Exe+Overlay.Ovr (или что-то типа того). Всё теперь можно запускать.
Хотя рекомендуется не использовать Overlay во время Debug'а (какой геморрой надо преодолеть, чтобы запустить прогу).
Вот так вот. Если ещё чего - спрашивай, может найду...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Ищущий истину
******

Группа: Пользователи
Сообщений: 4 825
Пол: Мужской
Реальное имя: Олег

Репутация: -  45  +


Цитата
Oleg_Z, использование Input и OutPut действительно ничего не ускорят, но вот размер на объявлении двух новых ФАЙЛОВЫХ переменных сэкономит

То есть ты хочешь сказать, что если описать :
Код

var
f:file;
f1:file;
f2:file
...

и если использовать только один, то под остальные будет память выделятся?
Не может компилятор быть таким глупым.

-------------
А как подсчитывать количество обращений, скажем к массиву, или к файлу, или к прерыванию?
-------------

Кстати, пока не забыл - здесь говорили что-то о {$M}, так вот если в модуле, то компилер просто игнорирует!

Сообщение отредактировано: Oleg_Z -


--------------------
Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

3 страниц V  1 2 3 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 24.11.2020 0:22
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name