![]() |
![]() |
Altair |
![]()
Сообщение
#1
|
![]() Ищущий истину ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 4 824 Пол: Мужской Реальное имя: Олег Репутация: ![]() ![]() ![]() |
Быстрые циклы.
Всего тестировалось 4 конструкции:
Проведение теста: сортировка массива (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..." Прикрепленные файлы ![]() -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
![]() ![]() |
mj |
![]()
Сообщение
#2
|
![]() Adminь ![]() ![]() ![]() ![]() Группа: Администраторы Сообщений: 803 Пол: Мужской Реальное имя: Евгений Репутация: ![]() ![]() ![]() |
на процессорах P2 и ниже
FOR быстрее чем WHILE должно работать на новых процах наоборот, это связано с внутренней конструкцией процессора. |
Atos |
![]()
Сообщение
#3
|
![]() Прогрессор ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 602 Пол: Мужской Реальное имя: Михаил Репутация: ![]() ![]() ![]() |
И Да ЗдравствуетИтерация! Пример: старая добрая задачка о Ханойской башне (нерекурсивный вариант).
Сообщение отредактировано: Atos - 16.03.2004 14:48 |
trminator |
![]()
Сообщение
#4
|
Четыре квадратика ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 579 Пол: Мужской Репутация: ![]() ![]() ![]() |
Ускорение вычислений 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'ом -------------------- Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала |
P@sh@ |
![]()
Сообщение
#5
|
![]() Бывалый ![]() ![]() ![]() Группа: Пользователи Сообщений: 180 Пол: Мужской Репутация: ![]() ![]() ![]() |
Деление на степень двойки
Аналогично быстрое деление на степень двойки - shr, а умножение - shl если мне не изменяет память, на команду DIV (деление) 486-е процы тратили до 70-ти тактов! (для сравнения - битовые команды типа AND/OR и сдвиги выполняются за 1-2 такта) |
P@sh@ |
![]()
Сообщение
#6
|
![]() Бывалый ![]() ![]() ![]() Группа: Пользователи Сообщений: 180 Пол: Мужской Репутация: ![]() ![]() ![]() |
Разворачивание циклов. -=loops unrolling=-
Один из методов оптимизации больших циклов - loops unrolling - "разворачивание"... тело цикла можно скопировать два/четыре раза, уменьшив во столько же раз кол-во итераций... глядишь, процессору удасться их распараллелить, да и на jump-ы время меньше тратится... |
trminator |
![]()
Сообщение
#7
|
Четыре квадратика ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 579 Пол: Мужской Репутация: ![]() ![]() ![]() |
P@sh@, сомневаюсь, что игра стОит свеч. Хотя попробовать можно... на jump'ы тратится не только время на их выполнение, если еще учесть, что может неверно сработать "предсказание" процессором, какую команду пускать на конвейер. Хотя это уже оптимизация будет не "качественная", а какая-то "количественная"...
ЗЫ: я ее все равно уже сдал... -------------------- Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала |
Altair |
![]()
Сообщение
#8
|
![]() Ищущий истину ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 4 824 Пол: Мужской Реальное имя: Олег Репутация: ![]() ![]() ![]() |
Процедуры FAR
Все процедуры в модулях, пишутся в расчете на дальнюю модель памяти. При этом тратится 1 байт и несколько милисекунд на запуск такой процедуры. -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
BlackShadow |
![]()
Сообщение
#9
|
Гость ![]() |
Специально для Oleg_Z:
В BP есть такая возможность при компиляции модуля указать, что тот может быть оверлейным ({$O+}). Тогда в проге можно будет использовать его таким образом: [PROGRAM][OVERLAY BUFFER] [PROGRAM][UNIT1][Y BUFFER] [PROGRAM][U2][RLAY BUFFER] Т. е. модули остаются неприкомпиленными, а извращёнными (компилятся в .ovr, вроде) и их надо тягать с собой (как .bgi), а когда надо вызвать чего-нибудь, то прога подгружает нужный модуль в память и работает с ним. Управлять буфером можно функциями из модуля Overlay. Короче отстой полный. Цитата Ну это не разработки борланда, это и в асме есть. Покажешь где? |
BlackShadow |
![]()
Сообщение
#10
|
Гость ![]() |
Описалова в книгах достаточно. Посмотрю чего - завтра отпишу. На самом деле, если в разных модулях находятся 2 частовызываемые функции, то на загрузке/выгрузке потеря будет...
А кто автор вот этой загадочной книги по Asm'у? |
trminator |
![]()
Сообщение
#11
|
Четыре квадратика ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 579 Пол: Мужской Репутация: ![]() ![]() ![]() |
Как нам говорили на лекции по ОС, оверлей - аналог страничной организации памяти, когда неиспользуемые страницы можно скинуть на диск (swap, pagefile) Так что не совсем dll
-------------------- Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала |
trminator |
![]()
Сообщение
#12
|
Четыре квадратика ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 579 Пол: Мужской Репутация: ![]() ![]() ![]() |
А про использование AssignCRT вместо Assign для записи в текстовый файл уже говорили?
![]() -------------------- Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала |
BlackShadow |
![]()
Сообщение
#13
|
Гость ![]() |
Ну и зкономии ради можно (олимпиадныю трюк) воспользоваться
Assing(Input,'In.Txt'); Reset(Input); Assign(Output,'Out.Txt'); ReWrite(Output); |
Altair |
![]()
Сообщение
#14
|
![]() Ищущий истину ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 4 824 Пол: Мужской Реальное имя: Олег Репутация: ![]() ![]() ![]() |
Просто есть файловая переменная Input и output только это не ускорит и не уменьшит размера.
-------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
trminator |
![]()
Сообщение
#15
|
Четыре квадратика ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 579 Пол: Мужской Репутация: ![]() ![]() ![]() |
Про сортировку. Понятно, что пузырек и компания никуда не годятся
![]() ![]() Есть распространенное мнение, что лучшая сортировка -- 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; Раскопал ее в развалинах своего винта. Она работает ![]() -------------------- Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала |
BlackShadow |
![]()
Сообщение
#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. Не буду их упоминать, т. к. не уверен, что вспомню в точности имена и параметры, но общий принцип таков. Сегодня вечером точно отпишу. |
trminator |
![]()
Сообщение
#17
|
Четыре квадратика ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 579 Пол: Мужской Репутация: ![]() ![]() ![]() |
Так... я не закончил про сортировки
![]() ИМХО, использовать, так пирамиду. Мои аргументы: * Обратите внимание на размер той процедуры, что я привел (я уже уверен, что это -- пирамида =). И сравните ее с размером quicksort'a. Что проще написАть по памяти? ![]() * Как я уже говорил, неплохо бы иметь гарантию, что ваша сортировка выполняется за n*log(n), а не за великий и ужастный n*n Особенно если вы участвуете в олимпиадах. И особенно если задачи составлял тов. Лопатин. Он любит quicksort ![]() Ну и недостатки у пирамидки тоже есть ![]() -------------------- Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала |
BlackShadow |
![]()
Сообщение
#18
|
Гость ![]() |
trminator, по памяти, может, её и проще, но на рефлексах пишется и пузырёк и QuickSort
![]() |
BlackShadow |
![]()
Сообщение
#19
|
Гость ![]() |
Oleg_Z, вот чего у меня в книге есть:
Функции Overlay'а: OvrClearBuf - очищает буфер ![]() OvrGetBuf - возвр. размер буфера OvrGetRetry - возвр. размер области испытаний (что за она не въехал, но по-умолчанию тут 0). OvrInit - инициализирует систему Overla'ев и открывает оверлейный файл. OvrInitEMS - загружает оверлейный файл в память EMS, если это возможно. OvrSetBuf - устанавливает размер буфера OvrSetRetry - догадайся сам, хотя не стоит ![]() Так же тут описана переменная OvrResult:Integer, которая может быть OvrOK(0) - всё пучком OvrError(-1) - что-то не пучком OvrNotFound(-2) - файл не нашёл OvrNoMemory(-3) - досадно как... OvrIOError(-4) - файл есть, атолку нет ObrNoEMSDriver(-5) - и такое бывает OvrNoEMSMemory(-6) - а драйвер тогда зачем? Ещё в модуле есть возможность переопределить такую фигню: Type Но зачем и что тут к чему я тоже что-то не того... А ещё в 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 ![]() Далее идёт пример: {$M 16384,65536,655360} Unit OvrInit; Далее берём и Build'им саму прогу. А потом выходим из BP и пишем в cmd Copy /B Proga.Exe+Overlay.Ovr (или что-то типа того). Всё теперь можно запускать. Хотя рекомендуется не использовать Overlay во время Debug'а (какой геморрой надо преодолеть, чтобы запустить прогу). Вот так вот. Если ещё чего - спрашивай, может найду... |
Altair |
![]()
Сообщение
#20
|
![]() Ищущий истину ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 4 824 Пол: Мужской Реальное имя: Олег Репутация: ![]() ![]() ![]() |
Цитата Oleg_Z, использование Input и OutPut действительно ничего не ускорят, но вот размер на объявлении двух новых ФАЙЛОВЫХ переменных сэкономит То есть ты хочешь сказать, что если описать : Код var f:file; f1:file; f2:file ... и если использовать только один, то под остальные будет память выделятся? Не может компилятор быть таким глупым. ------------- А как подсчитывать количество обращений, скажем к массиву, или к файлу, или к прерыванию? ------------- Кстати, пока не забыл - здесь говорили что-то о {$M}, так вот если в модуле, то компилер просто игнорирует! Сообщение отредактировано: Oleg_Z - 31.05.2004 15:49 -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
![]() ![]() |
![]() |
Текстовая версия | 28.06.2024 6:01 |