Подраздел 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..."
{этой функции черт знает сколько лет. Ее я взял из программы 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;
--------------------
Romiras HomeLab- материалы и статьи по разработке ПО, моделирование алгоритмов, обработка и анализ информации, нейронные сети, машинное зрение и прочее.
Begin и end лишние видимо я поставил, а вот объединить два промежутка, это мысль. romtek, а скорость увеличится? ИМХО так только нагляднее, а сорость не увеличится.
--------------------
Помогая друг другу, мы справимся с любыми трудностями! "Не опускать крылья!" (С)
Почему-то существует повальное мнение, что кроме применения ассемблера никак нельзя достигнуть увеличения скорости.
Нет, ассемблер нужно применять только для шлифовки критических участков кода (черт, это не моя фраза, и не помня откуда она ) Чаще сам алгоритм можно переработать используя только стандартные средства. Кстати конструкция if a and b then хуже, чем if a then if b then, т.к. в случае провала первой подцели (а), второя не будет проверятся!
--------- APAL, ИМХО пора бы эту тему закрепить.
Сообщение отредактировано: Oleg_Z -
--------------------
Помогая друг другу, мы справимся с любыми трудностями! "Не опускать крылья!" (С)
т.к. в случае провала первой подцели (а), второя не будет проверятся!
Complete boolean evaluation (compiler option)
Сообщение отредактировано: romtek -
--------------------
Romiras HomeLab- материалы и статьи по разработке ПО, моделирование алгоритмов, обработка и анализ информации, нейронные сети, машинное зрение и прочее.
Да уж, Oleg_Z, это действительно отключается директивами. Другое дело - преобразование сложных логических вычислений. Например: (a And Not B) Or (Not a And B) = a Xor b.
BlackShadow, в следующий раз оформляй логические выражения в тег кода. Насчет преобразования сложных логических вычислений - а все ли логические функции выполняются с одинаковай скоростью ??? Или есть смысл упрощать сложные логические конструкции? Например если 10^n раз проверяется
Код
Not(A and B)
То может это заменить на
Код
(Not a) or (not b)
Тогда мы избавляемся от and. Только есть ли в этом смысл? Думаю, что нет, а если есть, то при очень большом количестве повторов.
--------------------
Помогая друг другу, мы справимся с любыми трудностями! "Не опускать крылья!" (С)
Romiras HomeLab- материалы и статьи по разработке ПО, моделирование алгоритмов, обработка и анализ информации, нейронные сети, машинное зрение и прочее.
Вот еще: Если в программе используется 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- - отключить информацию для отладки (пропадает возможность отлаживать программу!!!)
(взял с сурсов.) Очень полезные директивы. Только две первые не влияют на размер.
Сообщение отредактировано: Oleg_Z -
--------------------
Помогая друг другу, мы справимся с любыми трудностями! "Не опускать крылья!" (С)
Oleg_Z Real потому медленнее, что у него размер нестандартный - 48 бит, кто его такой выдумал, интересно ? а все более-менее современные процы оптимизированы на работу с 32/64-бит данными. к тому же этот тип не поддерживается сопроцессором, поэтому его либо надо переконвертать в нормальный, либо эмулировать...
насчет директив - все они есть в диалоговом окошке "Опции компилятора" или как его там. если убрать все проверки, тогда конечно меньше будет объем кода, да и быстрее чуть-чуть, а почему первые две не влияют на размер ? видимо мат.функции хоть и в двух версиях написаны (с сопроцессором и софтварно), но компилируются всегда вместе...
Int64 появился только в 32-битных компиляторах. По своей сути он - то же самое, что LongInt для BP: работа в EAX и EDX вместо AX и DX. Скорость сравнима... А вот Real - это либо эмуляция либо содвижок...
А вот это, мне кажется, интересно: Простой пример: итерация по большому двумерному массиву может идти с совершенно разной скоростью, смотря как он обходится: горизонтально или вертикально. Как и в случае с поленом, которое легче раскалывать вдоль волокна, а не поперёк, одно направление может вызывать значительно больше отказов памяти, чем другое, а отказы обслуживаются долго. Даже программистам на ассемблере приходится делать вид, что у компьютера большая плоская память, но в системе виртуальной памяти это всего лишь абстракция, в которой при отказе памяти образуется дырка, так что отдельные обращения к памяти могут занимать значительно больше наносекунд, чем обычно.
Atos, ну это и лосю понятно. При последовательном переборе ячеек примитивная оптимизация позволяет конкретно сэкономить на загрузки в регистры новых адресов.
З. Ы. : лучший способ инициализации "любомерного" массива одинаковыми значениями - это Fillchar (если меня память не подводит, то в Pascal'е эта функция называется так).
Нет, в принципе, интуитивно понятно, что вроде бы на следующий элемент переходить удобнее, чем на n-й, но почему такой большой выигрыш? Тут увеличиваем смещение на единицу, там - на некоторое чиcло... Или для считывания слеующего элемента есть более быстрая команда? Хотя, наверное, я чушь порю... асм только-только начал трогать. Нельзя ли объяснить "на пальцах", как в обоих случаях будет действовать компилтор?
Действительно... Просто никогда её не использовал. Во всех примерах, на которых нас обучали, это делалось в цикле. Как-то прошёл мимо неё, хотя был уверен, что все основные функции помню. К тому же в описании не конкретно про массив, а просто про байты некоторой переменной говорилось. Будем знать.
Про оптимизацию я, кажется, понял. Она может достигаться применением цепочечных команд, которые позволяют процессору одновременно и работать и с регистром, и со счётчиком(как раз сегодня у нас лекция была). Так? Но, интересно, компилятор Паскаля знает, когда выгодней их использовать? Или только ассемблерными вставками?
Странно, тестирую бытсрую и пирамидальную на скорость, первая бысрее... может я ошибся где-то ? Вот код:
Код
{$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.
--------------------
Помогая друг другу, мы справимся с любыми трудностями! "Не опускать крылья!" (С)