IPB
ЛогинПароль:

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> Оптимальный алгоритм спиральной матрицы
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 15
Пол: Мужской
Реальное имя: Кирилл Мамонов
Компонентный Паскаль: Сторонник
Free Pascal: Сторонник
Turbo Pascal: Установлен

Репутация: -  0  +


Здравствуйте! Есть задача - написать оптимизированную по размеру исполняемого файла без ассемблерных вставок(можно использовать прерывания) программу для заполнения матрицы по спирали для случаев от 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.

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Большевик–концептуал
**

Группа: Пользователи
Сообщений: 133
Пол: Мужской
Реальное имя: Иван Левашев
Jabber: octagram@jabber.ru
Skype: i.levashew
QQ: 3152538431
WeChat
Ада: Сторонник
Embarcadero Delphi: Сторонник
Free Pascal: Разработчик
Turbo Pascal: Установлен

Репутация: -  0  +


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

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


--------------------
If you want to get to the top, you have to start at the bottom
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3





Группа: Пользователи
Сообщений: 8
Пол: Мужской

Репутация: -  0  +


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

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

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

Матрица по спирали - попробуйте, сравните.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Новичок
*

Группа: Пользователи
Сообщений: 15
Пол: Мужской
Реальное имя: Кирилл Мамонов
Компонентный Паскаль: Сторонник
Free Pascal: Сторонник
Turbo Pascal: Установлен

Репутация: -  0  +


Цитата(Халявов @ 21.12.2017 22:32) *

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

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

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

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


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

Задано в КубГУ, ну как задано... За самую маленькую в группе самоэкз получить можно)
Рекорд за всё время говорят где-то к 1200 байт приблизился.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

Группа: Пользователи
Сообщений: 15
Пол: Мужской
Реальное имя: Кирилл Мамонов
Компонентный Паскаль: Сторонник
Free Pascal: Сторонник
Turbo Pascal: Установлен

Репутация: -  0  +


Как думаете? Вообще реально написать такую программу с вводом и выводом без ассемблерных вставок чтоб она была хотя бы меньше 1500 байт?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6





Группа: Пользователи
Сообщений: 8
Пол: Мужской

Репутация: -  0  +


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

Сообщение отредактировано: Халявов -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Новичок
*

Группа: Пользователи
Сообщений: 15
Пол: Мужской
Реальное имя: Кирилл Мамонов
Компонентный Паскаль: Сторонник
Free Pascal: Сторонник
Turbo Pascal: Установлен

Репутация: -  0  +


Цитата(Халявов @ 24.12.2017 1:42) *

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


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


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





Группа: Пользователи
Сообщений: 8
Пол: Мужской

Репутация: -  0  +


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

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


Новичок
*

Группа: Пользователи
Сообщений: 15
Пол: Мужской
Реальное имя: Кирилл Мамонов
Компонентный Паскаль: Сторонник
Free Pascal: Сторонник
Turbo Pascal: Установлен

Репутация: -  0  +


Цитата(Халявов @ 24.12.2017 2:15) *

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

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

В том то и дело. Он говорил, что можно использовать в паскале прерывания(безэховый ввод в частности), но нельзя ассемблерные вставки. Да и даже с учётом, что вторая прога на ассемблере, рекорд на паскале всё равно остаётся 1200 байт. Побить я его конечно не стремлюсь(да и вряд ли возможно), но как вообще в принципе можно приблизиться хотя бы 1500-1800 байт на паскале? Пытался использовать модуль dos с его Intr и MsDos, но программа становится больше, что меня не устраивает. Пока, косо смотрю в сторону interrupt-процедур, но толковой документации я не нашёл и я вообще не знаю, могут ли они дать мне уменьшение в размерах?(там вроде как регистры можно использовать, но использует ли их реально компилятор на выходе я не знаю).
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Новичок
*

Группа: Пользователи
Сообщений: 15
Пол: Мужской
Реальное имя: Кирилл Мамонов
Компонентный Паскаль: Сторонник
Free Pascal: Сторонник
Turbo Pascal: Установлен

Репутация: -  0  +


В общем. Немного модифицировал и обнаружил, что теперь моя прога с вводом и выводов весит 2700 с хвостиком, с оптимизацией, а при закоменченных read и write весит 1700 c чем-то. Это то что мне нужно. Я смогу тогда на оставшиейся из 3000 байты потратить на программу на ассемблере, но всё же встаёт вопрос. Чем можно заменить маловесным ввод и вывод, чтобы это были не ассемблерные вставки?..
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Новичок
*

Группа: Пользователи
Сообщений: 15
Пол: Мужской
Реальное имя: Кирилл Мамонов
Компонентный Паскаль: Сторонник
Free Pascal: Сторонник
Turbo Pascal: Установлен

Репутация: -  0  +


Как ни странно - я смог ужать программу ещё сильнее... ну точнее её экзешник на выходе. со всеми оптимизациями компилятора выходит 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.

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Новичок
*

Группа: Пользователи
Сообщений: 15
Пол: Мужской
Реальное имя: Кирилл Мамонов
Компонентный Паскаль: Сторонник
Free Pascal: Сторонник
Turbo Pascal: Установлен

Репутация: -  0  +


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

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Новичок
*

Группа: Пользователи
Сообщений: 15
Пол: Мужской
Реальное имя: Кирилл Мамонов
Компонентный Паскаль: Сторонник
Free Pascal: Сторонник
Turbo Pascal: Установлен

Репутация: -  0  +


Я изучив exe-шник - обнаружил длиннющую строку с информацией о borland pascal, права, копирайт и т.д. Она же в принципе не нужна, но при этом я не могу её безболезненно напрямую удалить. Есть какой-то способ от неё избавиться?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Новичок
*

Группа: Пользователи
Сообщений: 15
Пол: Мужской
Реальное имя: Кирилл Мамонов
Компонентный Паскаль: Сторонник
Free Pascal: Сторонник
Turbo Pascal: Установлен

Репутация: -  0  +


Последние вести с полей. Уменьшил прогу до 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.

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Знаток
****

Группа: Пользователи
Сообщений: 466
Пол: Мужской
Реальное имя: Федосеев Павел

Репутация: -  9  +


Можно ещё чуток, если заменить
1. bx := bx + 1; на inc(bx)
2. si := si + s; на inc(si, s)
И то же самое для dec(bx).
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Новичок
*

Группа: Пользователи
Сообщений: 15
Пол: Мужской
Реальное имя: Кирилл Мамонов
Компонентный Паскаль: Сторонник
Free Pascal: Сторонник
Turbo Pascal: Установлен

Репутация: -  0  +


Цитата(Федосеев Павел @ 26.12.2017 20:24) *

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

Просто огромное спасибо! Это реально помогло)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Большевик–концептуал
**

Группа: Пользователи
Сообщений: 133
Пол: Мужской
Реальное имя: Иван Левашев
Jabber: octagram@jabber.ru
Skype: i.levashew
QQ: 3152538431
WeChat
Ада: Сторонник
Embarcadero Delphi: Сторонник
Free Pascal: Разработчик
Turbo Pascal: Установлен

Репутация: -  0  +


Цитата(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. А доступ по прямому адресу чреват чем-то таким. Так что надо сохранить этот адрес заранее поближе. С глобальными переменными, как я вижу, работает хорошо.


--------------------
If you want to get to the top, you have to start at the bottom
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Новичок
*

Группа: Пользователи
Сообщений: 15
Пол: Мужской
Реальное имя: Кирилл Мамонов
Компонентный Паскаль: Сторонник
Free Pascal: Сторонник
Turbo Pascal: Установлен

Репутация: -  0  +


Решил попробовать компилятор Turbo Pascal 5.5 В командной строке набираю TPC SPIRAL.PAS и на выходе получается фаил размером 1696 байт. Всё бы ничего, но это фаил не работает. Он запускается и может либо вывести матрицу буквами, либо ничего не вывести и зависнуть, либо из-за этой программы dosbox вылетает. Качал несколько разных версий компилятора и все выдают одно и тоже. С чем это может быть связано? Какие параметры стоит прописать, чтобы программа нормально скомпилировалась?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19





Группа: Пользователи
Сообщений: 8
Пол: Мужской

Репутация: -  0  +


Цитата(Akusov @ 28.12.2017 11:55) *
Turbo Pascal 5.5 В командной строке набираю TPC SPIRAL.PAS
Может как-то перепутали модули разных версий Uses Dos.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Новичок
*

Группа: Пользователи
Сообщений: 15
Пол: Мужской
Реальное имя: Кирилл Мамонов
Компонентный Паскаль: Сторонник
Free Pascal: Сторонник
Turbo Pascal: Установлен

Репутация: -  0  +


Цитата(Халявов @ 28.12.2017 8:05) *

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

Исключено. Офф.Версия.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 




- Текстовая версия 19.01.2018 18:20
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"