Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ FAQ _ Улучшение кода

Автор: Altair 7.03.2004 17:39

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

Всего тестировалось 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..."


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

Автор: mj 13.03.2004 22:09

на процессорах P2 и ниже
FOR быстрее чем WHILE должно работать на новых процах наоборот,
это связано с внутренней конструкцией процессора.

Автор: Atos 16.03.2004 18:44

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

Автор: trminator 15.05.2004 22:53

Ускорение вычислений 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@ 16.05.2004 0:08

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

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

если мне не изменяет память,
на команду DIV (деление) 486-е процы тратили до 70-ти тактов!
(для сравнения - битовые команды типа AND/OR и сдвиги выполняются за 1-2 такта)

Автор: P@sh@ 17.05.2004 22:42

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

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

Автор: trminator 19.05.2004 23:35

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

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

Автор: Altair 25.05.2004 18:28

Процедуры FAR

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

Автор: BlackShadow 25.05.2004 20:26

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

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

Покажешь где?

Автор: BlackShadow 26.05.2004 2:46

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

Автор: trminator 27.05.2004 22:30

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

Автор: trminator 27.05.2004 22:37

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

Автор: BlackShadow 28.05.2004 1:40

Ну и зкономии ради можно (олимпиадныю трюк) воспользоваться
Assing(Input,'In.Txt');
Reset(Input);
Assign(Output,'Out.Txt');
ReWrite(Output);

Автор: Altair 28.05.2004 1:44

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

Автор: trminator 28.05.2004 3:04

Про сортировку. Понятно, что пузырек и компания никуда не годятся 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

Автор: BlackShadow 28.05.2004 15:36

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 29.05.2004 19:32

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

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

Автор: BlackShadow 31.05.2004 15:08

trminator, по памяти, может, её и проще, но на рефлексах пишется и пузырёк и QuickSort smile.gif

Автор: BlackShadow 31.05.2004 15:43

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'а (какой геморрой надо преодолеть, чтобы запустить прогу).
Вот так вот. Если ещё чего - спрашивай, может найду...

Автор: Altair 31.05.2004 19:44

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

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

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

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

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

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

Автор: BlackShadow 31.05.2004 20:04

Цитата
Не может компилятор быть таким глупым

А, если ты напишешь так:
Код

Var
 a,b:Integer;
Begin
 a:=5;
 If a=1 Then
   b:=3
End.

Думаешь он под b ничего не выделит?
А не веришь - проверь.
Код

Var
 a,b,c,d,e,f:File;
 q:Integer;
 Addra,Addrq:LongInt;
Begin
 Addrq:=(Seg(q) Shl 4) + Ofs(q);
 Addra:=(Seg(a) Shl 4) + Ofs(a);
 WriteLn(SizeOf(a));
 WriteLn(Addrq-Addra)
End.

Сколько пишет?

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

1). Ты же за FPC взялся? Помнишь я тебе про свойства говорил? Вот так и подсчитать.
2). См п. 1
3). Перехватить и увеличивать счётчик.

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

Возможно.

Автор: Romtek 8.06.2004 2:25

Взято из http://forum.pascal.net.ru/index.php?act=ST&f=18&t=2085&hl=PWLHack&view=findpost&p=17726

Цитата
{этой функции черт знает сколько лет. Ее я взял из программы
PWLHack, старой прогрммы для взлома PWL, она хороша тем, что максимально
оптимизированна.}
Код
Function BD.UpStr(S:String):String; {перевод строки в верхний регистр}
Var I:Byte;
Begin
For I:=1 To ORD(S[0]) Do
Begin
Case S[I] Of
 'a'..'z':S[I]:=Chr(Ord(S[I])-$20);
 'а'..'п':S[I]:=Chr(Ord(S[I])-$20);
 'р'..'я':S[I]:=Chr(Ord(S[I])-$50)
End
End;
UpStr:=S
End;

Мой вариант:
Код
Function BD.UpStr(S:String):String; {перевод строки в верхний регистр}
Var I:Byte;
Begin
For I:=1 To ORD(S[0]) Do
Case S[I] Of
 'a'..'z',
 'а'..'п': S[I]:=Dec(S[I], $20);
 'р'..'я': S[I]:=Dec(S[I], $50)
End;
UpStr:=S
End;

Автор: Altair 8.06.2004 17:52

Begin и end лишние видимо я поставил, а вот объединить два промежутка, это мысль.
romtek, а скорость увеличится?
ИМХО так только нагляднее, а сорость не увеличится.

Автор: BlackShadow 15.06.2004 16:32

Вспомнил один момент такой. При работе с дробями, практичнее фразы типа b:=a/10 заменять на b:=a*0.1
Ну, это так, мелочи...

Автор: Altair 15.06.2004 23:27

Цитата
Почему-то существует повальное мнение, что кроме применения ассемблера никак нельзя достигнуть увеличения скорости. 



Нет, ассемблер нужно применять только для шлифовки критических участков кода (черт, это не моя фраза, и не помня откуда она )
Чаще сам алгоритм можно переработать используя только стандартные средства.
Кстати конструкция if a and b then хуже, чем
if a then if b then, т.к. в случае провала первой подцели (а), второя не будет проверятся!

---------
APAL, ИМХО пора бы эту тему закрепить.

Автор: Romtek 16.06.2004 2:08

Цитата(Oleg_Z)
черт, это не моя фраза, и не помня откуда она
моя вроде smile.gif

Цитата(Oleg_Z)
т.к. в случае провала первой подцели (а), второя не будет проверятся!
Complete boolean evaluation (compiler option)

Автор: BlackShadow 16.06.2004 17:42

Да уж, Oleg_Z, это действительно отключается директивами. Другое дело - преобразование сложных логических вычислений. Например:
(a And Not B) Or (Not a And B) = a Xor b.

Автор: Altair 16.06.2004 19:20

BlackShadow, в следующий раз оформляй логические выражения в тег кода. smile.gif
Насчет преобразования сложных логических вычислений - а все ли логические функции выполняются с одинаковай скоростью ???
Или есть смысл упрощать сложные логические конструкции?
Например если 10^n раз проверяется

Код

Not(A and B)

То может это заменить на
Код

(Not a) or (not b)

Тогда мы избавляемся от and.
Только есть ли в этом смысл?
Думаю, что нет, а если есть, то при очень большом количестве повторов.

Автор: Romtek 16.06.2004 20:15

В первом случае имеем 2 операции, а во втором - 3

Автор: Altair 17.06.2004 0:24

Да, но во первых операция NOT ИМХО должна выполняться быстрее, а во вторых есть обратный ход.

Автор: Altair 17.06.2004 17:34

Вот еще:
Если в программе используется write и writeln, то следует убрать последнюю, а использовать только write и управляющие символы.
Доказательство преимущества этого способа:
1 байт с проги снимется, т.к. writeln и write процедуры вне кода описанны, и компилтруются в расчете на FAR.
А так, вместо 2 байт на дальнюю модель памяти (т.е. на адрес процедуры) уйдет только 1 байт!


====== добавил позже =======

Облом. Я проверил все.
1. Логические операции бесполезно упрощать!
2. Writeln работает быстрее, чем write('ddfd',#13,#10), и к тому же на 100 кб(!!) меньше код получается (использовался один раз).
3. Сильно уменьшает код (на 150-200 кб) следующие директивы (применять только на уже оптимизированных программах)

Цитата
N+ - сопроцессор
E+ - эмуляция сопроцессора
I- - отключение проверок ввода/вывода
R- - отключение проверок на границы массивов
S- - отмена проверки на переполнение стека
Q- - отмена проверок на границы типов ­(overflow, underflow­)
B- - быстрое вычисление логических условий
D- - отключить информацию для отладки ­(пропадает возможность отлаживать программу!!!­)

(взял с сурсов.) Очень полезные директивы.
Только две первые не влияют на размер.

Автор: Altair 18.06.2004 18:05

REAL почти в 2 раза медленнее ВСЕХ других числовых типов

доказательство в присоединенном коде.


Прикрепленные файлы
Прикрепленный файл  TEST.PAS ( 3.67 килобайт ) Кол-во скачиваний: 485

Автор: P@sh@ 26.06.2004 11:41

Oleg_Z
Real потому медленнее, что у него размер нестандартный - 48 бит, кто его такой выдумал, интересно ? а все более-менее современные процы оптимизированы на работу с 32/64-бит данными. к тому же этот тип не поддерживается сопроцессором, поэтому его либо надо переконвертать в нормальный, либо эмулировать...

насчет директив - все они есть в диалоговом окошке "Опции компилятора" или как его там. если убрать все проверки, тогда конечно меньше будет объем кода, да и быстрее чуть-чуть, а почему первые две не влияют на размер ? видимо мат.функции хоть и в двух версиях написаны (с сопроцессором и софтварно), но компилируются всегда вместе...

Автор: BlackShadow 2.07.2004 19:23

Int64 появился только в 32-битных компиляторах. По своей сути он - то же самое, что LongInt для BP: работа в EAX и EDX вместо AX и DX. Скорость сравнима...
А вот Real - это либо эмуляция либо содвижок...

Автор: Atos 16.10.2004 12:13

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

Взято из этой статьи:http://russian.joelonsoftware.com/Articles/LeakyAbstractions.html#c4

А эту статью прочитал просто с наслаждением:http://russian.joelonsoftware.com/Articles/BacktoBasics.html

Автор: BlackShadow 19.10.2004 1:24

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

З. Ы. : лучший способ инициализации "любомерного" массива одинаковыми значениями - это Fillchar (если меня память не подводит, то в Pascal'е эта функция называется так).

Автор: Atos 19.10.2004 10:17

Цитата(BlackShadow @ 18.10.04 18:24)
в Pascal'е эта функция называется так).

В каком именно Паскале?

Цитата
Atos, ну это и лосю понятно.

Ну, я же не лось...

Нет, в принципе, интуитивно понятно, что вроде бы на следующий элемент переходить удобнее, чем на n-й, но почему такой большой выигрыш? Тут увеличиваем смещение на единицу, там - на некоторое чиcло... Или для считывания слеующего элемента есть более быстрая команда? Хотя, наверное, я чушь порю... асм только-только начал трогать. Нельзя ли объяснить "на пальцах", как в обоих случаях будет действовать компилтор?

Автор: GoodWind 19.10.2004 16:17

Цитата
В каком именно Паскале?

Borland Turbo Pascal 7.0
TMT pascal
да и во всех других, скорее всего, есть

Автор: Atos 19.10.2004 17:51

Действительно... Просто никогда её не использовал. Во всех примерах, на которых нас обучали, это делалось в цикле. Как-то прошёл мимо неё, хотя был уверен, что все основные функции помню. К тому же в описании не конкретно про массив, а просто про байты некоторой переменной говорилось. Будем знать.

Про оптимизацию я, кажется, понял. Она может достигаться применением цепочечных команд, которые позволяют процессору одновременно и работать и с регистром, и со счётчиком(как раз сегодня у нас лекция была). Так?
Но, интересно, компилятор Паскаля знает, когда выгодней их использовать?
Или только ассемблерными вставками?

Автор: Altair 7.11.2004 19:14

Странно, тестирую бытсрую и пирамидальную на скорость, первая бысрее... может я ошибся где-то ?
Вот код:

Код

{$M 65000, 0, 0}
Const
N=9000;
type
x=array[1..N] of real;
Var
a:x;
i:integer;
T:longint;
G:LongInT;


procedure swap (i, j : word);
var
t : real;
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
begin
 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;
end;
procedure Sort_Quick(var a:x; left,right:integer);
var
l,r:integer;
B:real;
begin
l:=left;
r:=right;
B:=a[l];
repeat
 while (a[r]>=B) and (l<r) do r:=r-1;
 a[l]:=a[r];
 while (a[l]<=B) and (l<r) do l:=L+1;
 a[r]:=a[l]
until r=l;
a[l]:=B;
If left<L-1 then SORT_QUICK(a,left,l-1);
If r+1<right then Sort_Quick(a,r+1,right);
end;

begin
Randomize;
T:=MemL[$0040:$006C];
FOR G:=1 to 100 do
begin
for i := 1 to n do a[i]:=Random(MaxInt);
for i := n downto 1 do sort (n, i);
for i := n downto 1 do
begin
 swap (1, i);
 sort (i-1, 1);
end;
End;
T:=MemL[$0040:$006C]-T;
Writeln(T);
T:=MemL[$0040:$006C];
FOR G:=1 to 100 do
begin
for i := 1 to n do a[i]:=Random(MaxInt);
Sort_Quick(A,1,n);
End;
 T:=MemL[$0040:$006C]-T;
Writeln(T);

end.

Автор: Altair 7.11.2004 20:24

Да, все верно,
пирамида медленнее чем "быстрая сортировка".

Цитата
50 000 элементов: QSort - 13, HeapSort - 18
200 000: 58 и 100 соответственно



---
ЗЫ: спасибо trminator'y за помощь при проведении теста и разбор результатов.

Автор: Dark 9.11.2004 5:23

Просто память физически устроена как конденсаторы [в каком бы то не было виде] в виде матрицы, и поэтому для перехода на следующий элемент требуется изменение только RAS цикла, и перехода считывателя на несколько мм а для перехода на ячейку в другом месте RAS и CAS счетчика...

Могу путать где RAS а где CAS - но при больших объемах используемой памяти значение большое...

Как нам объясняли, кэш нужен для хранения значения ЯПамяти при обновлении ячеек...

Автор: volvo 22.01.2005 23:39

Обмен значений в переменных.

Для увеличения скорости работы программы при обмене значениями двух чисел a и b вместо конструкции

Код
{1}
a := a + b;
b := a - b;
a := a - b;


или конструкции
Код
{2}
a := a xor b;
b := a xor b;
a := a xor b;

желательно использовать буферную переменную:
Код
{3}
T := a;
a := b;
b := T;


Тестируем скорость выполнения операции обмена:
Код
const
 n = 25000;

var
 tm, tm1: longint;
 i, j: longint;
 a, b, T: word;
begin
writeln('n = ', n, ' * ', n);

a := 1; b := 12;
{----- With plus/minus -----}
tm1:= MemL[$0040:$006c];
for i := 1 to n do
  for j := 1 to n do
    begin
      a := a + b; b := a - b; a := a - b;
    end;
tm:= MemL[$0040:$006c];
tm:=tm-tm1;
writeln('#1: ',tm);

a := 1; b := 12;
{----- With xor -----}
tm1:= MemL[$0040:$006c];
for i := 1 to n do
  for j := 1 to n do
    begin
      a := a xor b; b := a xor b; a := a xor b;
    end;
tm:= MemL[$0040:$006c];
tm:=tm-tm1;
writeln('#2: ',tm);

a := 1; b := 12;
{----- With T -----}
tm1:= MemL[$0040:$006c];
for i := 1 to n do
  for j := 1 to n do
    begin
      t := a; a := b; b := t;
    end;
tm:= MemL[$0040:$006c];
tm:=tm-tm1;
writeln('#3: ',tm);
end.


Результаты тестирования:
Цитата
n = 10000 * 10000 (100,000,000 обменов)
#1: 29
#2: 29
#3: 15

n = 12000 * 12000 (144,000,000 обменов)
#1: 41
#2: 42
#3: 22

n = 15000 * 15000 (225,000,000 обменов)
#1: 64
#2: 65
#3: 38

n = 25000 * 25000 (625,000,000 обменов)
#1: 182
#2: 180
#3: 98

n = 45000 * 45000 (2,025,000,000 обменов)
#1: 584
#2: 574
#3: 318