Здравствуйте! Есть задача - написать оптимизированную по размеру исполняемого файла без ассемблерных вставок(можно использовать прерывания) программу для заполнения матрицы по спирали для случаев от 1 до 9. Задачу решил и написал самый оптимизированный алгоритм, который я смог из себя выдавить. Скажите, что ещё здесь можно оптимизировать или уже стоит приступать к замене ввода на безэховый и вывода через прерывания? Может от каких переменных избавиться? Или циклы оптимизировать можно?
program spiral; var m: array [1..9, 1..9] of word; //Сама матрица n: word; //Размерность матрицы i: word; //Индексы матрицы j: word; c: word; //Вводимое число l: word; //Длина стороны s: integer; //Флаг меняющийся между значениями -1 и 1 t: word; //Координата поворота p: ^word; //Указатель на координаты begin readln(n); l := n; t := n; s := 1; i := 1; p := @j; repeat p^ := p^ + s; c := c + 1; //Если достигнута точка поворота if p^ = t then begin //Меняем изменяемую координату if p = @j then begin p := @i; l := l - 1; end else begin p := @j; s := -s; end; //Узнаём координату следующего поворота t := p^ + s*(l); end; m[i,j] := c; until l = 0; //Обычный вывод for i:=1 to n do begin for j:=1 to n do write(m[i,j]:3); writeln; end; end.
Какая-то довольно специфическая оптимизация. На фоне рантайма размер кода изчезающе мал, мне кажется.
Предположу, что если вынести массив в локальные переменные процедуры, то он перестанет занимать место в сегменте данных. И не факт, что эту разницу можно будет замететить. После выравнивания размер программы изменяется скачкообразно.
--------------------
If you want to get to the top, you have to start at the bottom
Моя после компиляции без всяких особых натроек компилятора весит 3104 байта
А чем компилировали? Поделитесь секретом
BPC Старый добрый BPC. Это собственно и есть компилятор для соревнований. Всё в досбоксе собирается.
Добавлено через 3 мин. Счёт идёт на байты. Вообще задание полностью так звучит - Нужно написать две программы спиральной матрицы для размерность от 2 до 9. Одну на ассемблере, другую на паскале и в суме они должны быть меньше 3000 байт, и тот чья прога меньше остальных, тот и получает самоэкз. В программе на паскале использовать asm end. Запрещено.
Понятно, Ассемблер всё объясняет. А то задача выглядит как злобный троллинг препода.
Я бы начал думать как сэкономить на WriteLn. Теоретически, у вас два вызова с разным набором параметров. На Си можно было бы сделать подобие printf("..формат..", Элемент_Массива, i==n?"\n":" "); хотя само вычисление может оказаться большим.
Понятно, Ассемблер всё объясняет. А то задача выглядит как злобный троллинг препода.
Я бы начал думать как сэкономить на WriteLn. Теоретически, у вас два вызова с разным набором параметров. На Си можно было бы сделать подобие printf("..формат..", Элемент_Массива, i==n?"\n":" "); хотя само вычисление может оказаться большим.
В том то и дело. Он говорил, что можно использовать в паскале прерывания(безэховый ввод в частности), но нельзя ассемблерные вставки. Да и даже с учётом, что вторая прога на ассемблере, рекорд на паскале всё равно остаётся 1200 байт. Побить я его конечно не стремлюсь(да и вряд ли возможно), но как вообще в принципе можно приблизиться хотя бы 1500-1800 байт на паскале? Пытался использовать модуль dos с его Intr и MsDos, но программа становится больше, что меня не устраивает. Пока, косо смотрю в сторону interrupt-процедур, но толковой документации я не нашёл и я вообще не знаю, могут ли они дать мне уменьшение в размерах?(там вроде как регистры можно использовать, но использует ли их реально компилятор на выходе я не знаю).
В общем. Немного модифицировал и обнаружил, что теперь моя прога с вводом и выводов весит 2700 с хвостиком, с оптимизацией, а при закоменченных read и write весит 1700 c чем-то. Это то что мне нужно. Я смогу тогда на оставшиейся из 3000 байты потратить на программу на ассемблере, но всё же встаёт вопрос. Чем можно заменить маловесным ввод и вывод, чтобы это были не ассемблерные вставки?..
Как ни странно - я смог ужать программу ещё сильнее... ну точнее её экзешник на выходе. со всеми оптимизациями компилятора выходит 2080 байт. Но всё ещё нужно преодолеть порог в 2000 байт. Есть идеи, глядя на этот новый код?
program spiral; uses dos; var m: array [1..9, 1..9] of word; n: word; i: word; j: word; c: word; l: word; s: integer; t: word; p: ^word; r: registers; begin with r do begin ah := 8; msdos®; n := r.al - 48; ah := 2; end; l := n; t := n; s := 1; i := 1; p := @j; repeat p^ := p^ + s; c := c + 1; if c = t then begin if p = @j then begin p := @i; l := l - 1; end else begin p := @j; s := -s; end; t := c + l; end; m[i,j] := c; until l = 0; for i:=1 to n do begin for j:=1 to n do with r do begin dl := m[i,j] div 10 + 48; msdos®; dl := m[i,j] mod 10 + 48; msdos®; dl := 32; msdos®; end; with r do begin dl := 13; msdos®; dl := 10; msdos®; end; end; end.
Пораскинув мозгами, смог ужать итоговый екзешник до 1952 байт, но дальше чего-то не двигается. Может я чего-то в этом коде просто в упор не вижу, как оптимизировать? Любое удаление if или mod с div приводит к существенном ощутимому уменьшению. Есть какие-нибудь идеи?
uses dos; var m: array [1..81] of word; s: integer; r: registers; f: boolean; begin with r do begin ah := 7; msdos®; di := al - 48; ah := 2; bx := di; es := di; s := 1; repeat cx := cx + 1; si := si + s; if cx = es then begin if abs(s) = 1 then begin s := di; bx := bx - 1; end else begin s := 1; f := not f; end; if f then s := -s; es := cx + bx; end; m[si] := cx; until bx = 0; repeat bx := bx + 1; dl := m[bx] div 10 + 48; msdos®; dl := m[bx] mod 10 + 48; msdos®; dl := 32; msdos®; if bx mod di = 0 then begin dl := 10; msdos®; end; until bx = cx; end; end.
Я изучив exe-шник - обнаружил длиннющую строку с информацией о borland pascal, права, копирайт и т.д. Она же в принципе не нужна, но при этом я не могу её безболезненно напрямую удалить. Есть какой-то способ от неё избавиться?
Последние вести с полей. Уменьшил прогу до 1936 байт путём замены в выводе условия.
{$S-} uses dos; var m: array [1..81] of word; s: integer; r: registers; f: boolean; begin with r do begin ah := 7; msdos®; di := al - 48; ah := 2; bx := di; es := di; s := 1; repeat cx := cx + 1; si := si + s; if cx = es then begin if abs(s) = 1 then begin s := di; bx := bx - 1; end else begin s := 1; f := not f; end; if f then s := -s; es := cx + bx; end; m[si] := cx; until bx = 0; repeat bx := bx + 1; dl := m[bx] div 10 + 48; msdos®; dl := m[bx] mod 10 + 48; msdos®; if bx mod di = 0 then dl := 10 else dl := 32; msdos®; until bx = cx; end; end.
Пытался использовать модуль dos с его Intr и MsDos, но программа становится больше, что меня не устраивает. Пока, косо смотрю в сторону interrupt-процедур, но толковой документации я не нашёл и я вообще не знаю, могут ли они дать мне уменьшение в размерах?(там вроде как регистры можно использовать, но использует ли их реально компилятор на выходе я не знаю).
Turbo Pascal позволяет написать свою interrupt-процедуру, но не определить указатель на неё. Когда я пытаюсь написать
… Turbo Pascal ругается на отсутствие = после interrupt. Похоже, у указателей на процедуры вообще не может быть директив.
Ситуация всё же не безнадёжная. Мне удалось вызвать прерывание 16#21# (AH => 16#09#). Вызов прерываний как программных, так и аппаратных, похож на далёкий вызов, но в стек помещается также и регистр флагов. Инструкция iret, которой заканчиваются обработчики прерываний, в отличие от retf, также и возвращает состояние этого регистра. Если в Турбо Паскале указатели на процедуры могут быть только обычными, мне пришла в голову идея объявить тип указателя на прерывание как принимающий один аргумент. И чтоб передавать потом в этот аргумент типичное состояние флагов, которое я вывел на экран ассемблерной процедурой, не попадающей в конечный результат.
Далее, вот конкретно подвызов AH => 16#09# принимает адрес строки в DS:DX. Соответственно, надо как-то подстроить, чтоб там оказались нужные значения. Почти надёжный способ с AX и DX — это устроить возврат LongInt. LongInt возвращается в DX:AX, старшее слово — в DX, младшее — в AX. На DS я повлиять не могу, он спроецирован на общий для всей программы сегмент данных. Так что нужно, чтоб буфер был там. То есть, это обязательно глобальная переменная.
Итак, мне нужна функция, которая сконструирует DX:AX, вернув подходящее значение. Это значение будет сразу же «выброшено», но функция-то об этом не знает. Возвращать лучше бы DWord, но в Turbo Pascal такого типа нет, а есть только знаковый LongInt. Это плохо. Вдруг старший бит DX будет выставлен? Значит, я сначала получаю значение DX как есть (тип Word), потом привожу к Integer, что в Турбо Паскале часто работает как Unchecked_Conversion в языке Ада или reinterpret_cast в C++. Потом надо это значение сдвинуть на 16 бит в верхнее слово, но сначала ещё раз привести тип, на этот раз — к LongInt. А после этого при помощи «or $0900» инициализировать будущий AH.
Я использовал GetIntVec из модуля Dos. Вы можете переделать на прямой доступ к таблице прерываний, но осторожно. Между функцией, которая конструирует DX:AX, и вызовом прерывания по возможности не должно быть никаких вычислений, которые могли бы уничтожить AX. А доступ по прямому адресу чреват чем-то таким. Так что надо сохранить этот адрес заранее поближе. С глобальными переменными, как я вижу, работает хорошо.
--------------------
If you want to get to the top, you have to start at the bottom
Решил попробовать компилятор Turbo Pascal 5.5 В командной строке набираю TPC SPIRAL.PAS и на выходе получается фаил размером 1696 байт. Всё бы ничего, но это фаил не работает. Он запускается и может либо вывести матрицу буквами, либо ничего не вывести и зависнуть, либо из-за этой программы dosbox вылетает. Качал несколько разных версий компилятора и все выдают одно и тоже. С чем это может быть связано? Какие параметры стоит прописать, чтобы программа нормально скомпилировалась?