Подраздел FAQ (ЧАВО, ЧАстые ВОпросы) предназначен для размещения готовых рабочих программ, реализаций алгоритмов. Это нечто вроде справочника, он наполнялся в течение 2000х годов. Ваши вопросы, особенно просьбы решить задачу, не пройдут предмодерацию. Те, кто наполнял раздел, уже не заходят на форум, а с теми, кто на форуме сейчас, лучше начинать общение в других разделах. В частности, решение задач — здесь.
Проведение теста: сортировка массива (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..."
Програма считает 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'ом
--------------------
Закон добровольного труда Зимерги: Люди всегда согласны сделать работу, когда необходимость в этом уже отпала
Аналогично быстрое деление на степень двойки - shr, а умножение - shl
если мне не изменяет память, на команду DIV (деление) 486-е процы тратили до 70-ти тактов! (для сравнения - битовые команды типа AND/OR и сдвиги выполняются за 1-2 такта)
Один из методов оптимизации больших циклов - loops unrolling - "разворачивание"... тело цикла можно скопировать два/четыре раза, уменьшив во столько же раз кол-во итераций... глядишь, процессору удасться их распараллелить, да и на jump-ы время меньше тратится...
P@sh@, сомневаюсь, что игра стОит свеч. Хотя попробовать можно... на jump'ы тратится не только время на их выполнение, если еще учесть, что может неверно сработать "предсказание" процессором, какую команду пускать на конвейер. Хотя это уже оптимизация будет не "качественная", а какая-то "количественная"...
ЗЫ: я ее все равно уже сдал...
--------------------
Закон добровольного труда Зимерги: Люди всегда согласны сделать работу, когда необходимость в этом уже отпала
Специально для Oleg_Z: В BP есть такая возможность при компиляции модуля указать, что тот может быть оверлейным ({$O+}). Тогда в проге можно будет использовать его таким образом: [PROGRAM][OVERLAY BUFFER] [PROGRAM][UNIT1][Y BUFFER] [PROGRAM][U2][RLAY BUFFER] Т. е. модули остаются неприкомпиленными, а извращёнными (компилятся в .ovr, вроде) и их надо тягать с собой (как .bgi), а когда надо вызвать чего-нибудь, то прога подгружает нужный модуль в память и работает с ним. Управлять буфером можно функциями из модуля Overlay. Короче отстой полный.
Описалова в книгах достаточно. Посмотрю чего - завтра отпишу. На самом деле, если в разных модулях находятся 2 частовызываемые функции, то на загрузке/выгрузке потеря будет... А кто автор вот этой загадочной книги по Asm'у?
Как нам говорили на лекции по ОС, оверлей - аналог страничной организации памяти, когда неиспользуемые страницы можно скинуть на диск (swap, pagefile) Так что не совсем dll
--------------------
Закон добровольного труда Зимерги: Люди всегда согласны сделать работу, когда необходимость в этом уже отпала
Про сортировку. Понятно, что пузырек и компания никуда не годятся хотя если нужно отсортировать десяток элементов, самое оно
Есть распространенное мнение, что лучшая сортировка -- 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;
Раскопал ее в развалинах своего винта. Она работает
--------------------
Закон добровольного труда Зимерги: Люди всегда согласны сделать работу, когда необходимость в этом уже отпала
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. Не буду их упоминать, т. к. не уверен, что вспомню в точности имена и параметры, но общий принцип таков. Сегодня вечером точно отпишу.
Так... я не закончил про сортировки ИМХО, использовать, так пирамиду. Мои аргументы: * Обратите внимание на размер той процедуры, что я привел (я уже уверен, что это -- пирамида =). И сравните ее с размером quicksort'a. Что проще написАть по памяти? * Как я уже говорил, неплохо бы иметь гарантию, что ваша сортировка выполняется за n*log(n), а не за великий и ужастный n*n Особенно если вы участвуете в олимпиадах. И особенно если задачи составлял тов. Лопатин. Он любит quicksort
Ну и недостатки у пирамидки тоже есть как же без них. В среднем quicksort все же быстрее -- внутренний цикл у него самый быстрый.
--------------------
Закон добровольного труда Зимерги: Люди всегда согласны сделать работу, когда необходимость в этом уже отпала
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 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
Далее идёт пример:
{$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'а (какой геморрой надо преодолеть, чтобы запустить прогу). Вот так вот. Если ещё чего - спрашивай, может найду...
Правила форума
Внимание! Действует предмодерация
по Фаронову, наного быстрее