Помощь - Поиск - Пользователи - Календарь
Полная версия: Оптимальный алгоритм спиральной матрицы
Форум «Всё о Паскале» > Современный Паскаль и другие языки > Free Pascal, Pascal ABC и другие
Akusov
Здравствуйте! Есть задача - написать оптимизированную по размеру исполняемого файла без ассемблерных вставок(можно использовать прерывания) программу для заполнения матрицы по спирали для случаев от 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.

OCTAGRAM
Какая-то довольно специфическая оптимизация. На фоне рантайма размер кода изчезающе мал, мне кажется.

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

Цитата
написать оптимизированную по размеру исполняемого файла

-и сколько получилось?

Матрица по спирали - попробуйте, сравните.
Akusov
Цитата(Халявов @ 21.12.2017 22:32) *

Интересно, в каком вузе дают подобные программы? Ну в смысле, что явно академическая задача и "давайте её оптимизировать".

Цитата
написать оптимизированную по размеру исполняемого файла

-и сколько получилось?

Матрица по спирали - попробуйте, сравните.


Моя после компиляции без всяких особых натроек компилятора весит 3104 байта
Вами, приведённая 3776 байт

Задано в КубГУ, ну как задано... За самую маленькую в группе самоэкз получить можно)
Рекорд за всё время говорят где-то к 1200 байт приблизился.
Akusov
Как думаете? Вообще реально написать такую программу с вводом и выводом без ассемблерных вставок чтоб она была хотя бы меньше 1500 байт?
Халявов
Цитата(Akusov @ 24.12.2017 2:13) *
Моя после компиляции без всяких особых натроек компилятора весит 3104 байта
А чем компилировали? Поделитесь секретом smile.gif
Akusov
Цитата(Халявов @ 24.12.2017 1:42) *

Цитата(Akusov @ 24.12.2017 2:13) *
Моя после компиляции без всяких особых натроек компилятора весит 3104 байта
А чем компилировали? Поделитесь секретом smile.gif


BPC Старый добрый BPC. Это собственно и есть компилятор для соревнований. Всё в досбоксе собирается.


Добавлено через 3 мин.
Счёт идёт на байты. Вообще задание полностью так звучит - Нужно написать две программы спиральной матрицы для размерность от 2 до 9. Одну на ассемблере, другую на паскале и в суме они должны быть меньше 3000 байт, и тот чья прога меньше остальных, тот и получает самоэкз. В программе на паскале использовать asm end. Запрещено.
Халявов
Понятно, Ассемблер всё объясняет. А то задача выглядит как злобный троллинг препода.

Я бы начал думать как сэкономить на WriteLn. Теоретически, у вас два вызова с разным набором параметров.
На Си можно было бы сделать подобие
printf("..формат..", Элемент_Массива, i==n?"\n":" ");
хотя само вычисление может оказаться большим.
Akusov
Цитата(Халявов @ 24.12.2017 2:15) *

Понятно, Ассемблер всё объясняет. А то задача выглядит как злобный троллинг препода.

Я бы начал думать как сэкономить на WriteLn. Теоретически, у вас два вызова с разным набором параметров.
На Си можно было бы сделать подобие
printf("..формат..", Элемент_Массива, i==n?"\n":" ");
хотя само вычисление может оказаться большим.

В том то и дело. Он говорил, что можно использовать в паскале прерывания(безэховый ввод в частности), но нельзя ассемблерные вставки. Да и даже с учётом, что вторая прога на ассемблере, рекорд на паскале всё равно остаётся 1200 байт. Побить я его конечно не стремлюсь(да и вряд ли возможно), но как вообще в принципе можно приблизиться хотя бы 1500-1800 байт на паскале? Пытался использовать модуль dos с его Intr и MsDos, но программа становится больше, что меня не устраивает. Пока, косо смотрю в сторону interrupt-процедур, но толковой документации я не нашёл и я вообще не знаю, могут ли они дать мне уменьшение в размерах?(там вроде как регистры можно использовать, но использует ли их реально компилятор на выходе я не знаю).
Akusov
В общем. Немного модифицировал и обнаружил, что теперь моя прога с вводом и выводов весит 2700 с хвостиком, с оптимизацией, а при закоменченных read и write весит 1700 c чем-то. Это то что мне нужно. Я смогу тогда на оставшиейся из 3000 байты потратить на программу на ассемблере, но всё же встаёт вопрос. Чем можно заменить маловесным ввод и вывод, чтобы это были не ассемблерные вставки?..
Akusov
Как ни странно - я смог ужать программу ещё сильнее... ну точнее её экзешник на выходе. со всеми оптимизациями компилятора выходит 2080 байт. Но всё ещё нужно преодолеть порог в 2000 байт. Есть идеи, глядя на этот новый код? smile.gif
 
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.

Akusov
Пораскинув мозгами, смог ужать итоговый екзешник до 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.

Akusov
Я изучив exe-шник - обнаружил длиннющую строку с информацией о borland pascal, права, копирайт и т.д. Она же в принципе не нужна, но при этом я не могу её безболезненно напрямую удалить. Есть какой-то способ от неё избавиться?
Akusov
Последние вести с полей. Уменьшил прогу до 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.

Федосеев Павел
Можно ещё чуток, если заменить
1. bx := bx + 1; на inc(bx)
2. si := si + s; на inc(si, s)
И то же самое для dec(bx).
Akusov
Цитата(Федосеев Павел @ 26.12.2017 20:24) *

Можно ещё чуток, если заменить
1. bx := bx + 1; на inc(bx)
2. si := si + s; на inc(si, s)
И то же самое для dec(bx).

Просто огромное спасибо! Это реально помогло)
OCTAGRAM
Цитата(Akusov @ 24.12.2017 6:32) *
Пытался использовать модуль dos с его Intr и MsDos, но программа становится больше, что меня не устраивает. Пока, косо смотрю в сторону interrupt-процедур, но толковой документации я не нашёл и я вообще не знаю, могут ли они дать мне уменьшение в размерах?(там вроде как регистры можно использовать, но использует ли их реально компилятор на выходе я не знаю).


Turbo Pascal позволяет написать свою interrupt-процедуру, но не определить указатель на неё. Когда я пытаюсь написать

type THandler = procedure(AX, BX, CX, DX, SI, DI, DS, ES, BP: Word); 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. А доступ по прямому адресу чреват чем-то таким. Так что надо сохранить этот адрес заранее поближе. С глобальными переменными, как я вижу, работает хорошо.
Akusov
Решил попробовать компилятор Turbo Pascal 5.5 В командной строке набираю TPC SPIRAL.PAS и на выходе получается фаил размером 1696 байт. Всё бы ничего, но это фаил не работает. Он запускается и может либо вывести матрицу буквами, либо ничего не вывести и зависнуть, либо из-за этой программы dosbox вылетает. Качал несколько разных версий компилятора и все выдают одно и тоже. С чем это может быть связано? Какие параметры стоит прописать, чтобы программа нормально скомпилировалась?
Халявов
Цитата(Akusov @ 28.12.2017 11:55) *
Turbo Pascal 5.5 В командной строке набираю TPC SPIRAL.PAS
Может как-то перепутали модули разных версий Uses Dos.
Akusov
Цитата(Халявов @ 28.12.2017 8:05) *

Цитата(Akusov @ 28.12.2017 11:55) *
Turbo Pascal 5.5 В командной строке набираю TPC SPIRAL.PAS
Может как-то перепутали модули разных версий Uses Dos.

Исключено. Офф.Версия.
OCTAGRAM
Можно ещё попробовать директивами отключить эмуляцию сопроцессора и все проверки, включая I/O. Каждая из них может потенциально по графу зависимостей подтягивать куски библиотеки времени исполнения. Хотя, насколько я помню, в System.pas и Crt.pas большая часть была написана в отдельных файлах на ассемблере и подключена как OBJ. А OBJ, если уж тащится, то тащится целиком.

Буфер, если печатать моим способом, должен быть поменьше, string[15], чтоб только хватило напечатать число, потом пробел или перенос строки.

Вынесение m в локальные переменные процедуры вообще влияет на размер хоть как-то?
Akusov
Цитата(OCTAGRAM @ 28.12.2017 14:04) *

Можно ещё попробовать директивами отключить эмуляцию сопроцессора и все проверки, включая I/O. Каждая из них может потенциально по графу зависимостей подтягивать куски библиотеки времени исполнения. Хотя, насколько я помню, в System.pas и Crt.pas большая часть была написана в отдельных файлах на ассемблере и подключена как OBJ. А OBJ, если уж тащится, то тащится целиком.

Буфер, если печатать моим способом, должен быть поменьше, string[15], чтоб только хватило напечатать число, потом пробел или перенос строки.

Вынесение m в локальные переменные процедуры вообще влияет на размер хоть как-то?


Я с помощью TPC всё же смог получить 1696 байтов, но занесение всей проги в процедуру погоды не делает. Точнее наоборот. программ увеличивается.
Akusov
Уже 1680. Нашёл просто дичайшую неоптимизированность и заменил её.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.