Помощь - Поиск - Пользователи - Календарь
Полная версия: Как можно улучшить эффективность и качество ПП?
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
1147
Такое задание по курсу технологии программирования:
дан текст программы (Pascal). Программа создает динамический список неповторяющихся целых чисел в диапазоне от -50 до 50, обеспечивает прямой и обратный вывод элементов списка, должна посчитать сумму 1+n, 2+n-1,...i+n-1+1,...n/2+n/2+1
Необходимо улучшить эффективность и качество данной программы, что увеличит скорость ее выполнения, устранит возможные недостатки и возможно улучшит другие характеристики...
Если кто заметит в ней какие-либо недостатки или фрагменты которые можно улучшить (например операцию умножения заменить на смещение и т.д.), огромная просьба пояснить мне в чем заключается улучшение, как его реализовать и какой фрагмент кода можно преобразовать, возможно есть чтото лишнее в коде...

{построение динамического списка }
Program din;
uses crt;
type tpo=^tn; tn=record x:real; p1,p2:tpo; end;
var s,b:tpo; f,k:pointer;
i,n,x,dd:integer; z:real;

begin
clrscr; n:=6; dd:=9;
{создание списка }
new(s); randomize; z:=random(100)-50; s^.x:=z; f:=s; s^.p2:=nil;
for i:=1 to n-1 do begin new(b); z:=random(100)-50; b^.x:=z;
s^.p1:=b; b^.p2:=s; s:=b; end;
s^.p1:=nil; k:=s;

textcolor(13);
Write(' прямой вывод: ');
s:=f; x:=18;
while s<>nil do
begin gotoxy(x,wherey); write(s^.x:1:1); s:=s^.p1; x:=x+dd;
end;
writeln;
x:=20;
for i:=1 to N do begin gotoxy(x,wherey); write('+'); x:=x+dd;
end;
writeln;

Write('обратный ввод: ');
b:=k; x:=18;
while b<>nil do
begin gotoxy(x,wherey); write(b^.x:1:1); b:=b^.p2; x:=x+dd;
end;
x:=wherex;
writeln; textcolor(11);
for i:=1 to x do begin gotoxy(i,wherey); write('_'); end;
writeln;
writeln;
Write(' результат: ');
s:=f; b:=k; x:=18;
while s<>nil do
begin z:=s^.x+ b^.x; gotoxy(x,wherey); write(z:1:1);
s:=s^.p1; b:=b^.p2; x:=x+dd; end;
readkey;
end.
;
end.


Тегами пользоваться не забывай
volvo
Цитата
Программа создает динамический список неповторяющихся целых чисел в диапазоне от -50 до 50
Во-первых, в твоем коде я не увидел проверку на повторяемость. Можно показать пальцем, где именно ты гарантируешь, что какое-то число не будет использовано дважды? Вот я запустил твою программу 3 раза, и на третий раз:
 прямой вывод:   -2.0     35.0     45.0     -39.0    -22.0    45.0
+ + + + + +
обратный ввод: 45.0 -22.0 -39.0 45.0 35.0 -2.0
___________________________________________________________________

результат: 43.0 13.0 6.0 6.0 13.0 43.0
Видишь число 45?

Второе: целые числа - это Integer, а не Real, зачем тебе лишние 4 байта в каждом элементе списка?

P.S.
Перенесено в "Задачи", поскольку это уже конкретная реализация, а не общий вопрос.
1147
Получается что программа содержит эти 2 недочета, а в остальном все нормально, да?
Как можно организовать проверку на повторяемость? Засчет этого увеличится время выполнения программы, а задача наоборот минимизировать его. Может быть возможно внести изменения в создание списка чтобы он гарантированно не выдал повторения? Хотя с randomize это наверно неизбежно будет происходить
volvo
Цитата
Засчет этого увеличится время выполнения программы
Для начале надо создать корректно (а не кое-как) работающую программу, а уж потом ее оптимизировать. Твоя программа поставленным в задании условиям не удовлетворяет. Значит, надо сделать так, чтоб удовлетворяла. Это может привести (и приведет) к увеличению времени выполнения, но смотри...

Ведь я могу заменить в твоей реализации список на массив, это будет вообще очень быстро работать. Однако, это ж тебя не устроит, правда? Ведь в задании сказано
Цитата
Программа создает динамический список неповторяющихся целых чисел в диапазоне от -50 до 50
, ты скажешь. Но вместе с тем, в задании сказано:
Цитата
Программа создает динамический список неповторяющихся целых чисел в диапазоне от -50 до 50
. Так что выбора нет, исправляй...

Креме всего прочего, у тебя число 50 ни при каких условиях не сгенерируется. Только -50 .. 49, там в Random надо добавить 1...

Добавлено через 4 мин.
Плюс к этому, смешно оптимизировать программу, которая использует такие медленные вещи, как GotoXY, да еще в таком виде, как у тебя, только для того, чтобы перемещаться по горизонтали... Пользуйся форматным выводом чисел чуть-чуть по другому, можно будет вообще убрать все gotoxy...
1147
Большое спасибо за полезные советы Volvo, с остальным я попробую справиться
1147
Если мы список заменим на массив, как это поможет избавиться от повторяющихся чисел???
volvo
Если мы список заменим на массив - это поможет значительно ускорить программу. Даже при добавлении проверки на повторяющиеся числа выигрыш в скорости останется. Но это - не по заданию.

Пока избавься от GotoXY, они у тебя пожирают значительное время.
1147
type подойдет для того чтобы избавиться от gotoxy? Каким образом можно организовать проверку на повторение? И что произойдет в случае обнаружения повторяющихся цифр?

Добавлено через 2 мин.
наверное новая генерация чисел до тех пор пока не будет совпадений?
volvo
Цитата
Каким образом можно организовать проверку на повторение?
Смотри внимательно, что изменилось в программе:
Program  din;
uses crt;
type
tpo = ^tn;
tn = record
x: shortint;
p1, p2: tpo;
end;

const
width = 15;
field = 8;

var s,b,f,k:tpo;
i,n,x:integer; z:byte;
used: set of byte;

begin
clrscr;
n:=6;

randomize;
new(s); z:=random(101); inclide(used, z);
s^.x := z - 50; f:=s; s^.p2:=nil;
for i:=1 to n-1 do begin
new(b);
repeat z:=random(101); until not (z in used);
b^.x:=z - 50; s^.p1:=b; b^.p2:=s; s:=b;
end;
s^.p1:=nil; k:=s;

textcolor(13);
write('прямой вывод: ':width);
s:=f;
while s<>nil do begin
write(s^.x:field); s:=s^.p1;
end;
writeln;

write('':width);
for i:=1 to N do write('+':field);
writeln;

Write('обратный ввод: ':width);
b:=k; x := width;
while b<>nil do begin
write(b^.x:field); b:=b^.p2;
inc(x, field);
end;
writeln;

textcolor(11);
for i:=1 to x do write('_');
writeln; writeln;

Write('результат: ':width);
s:=f; b:=k;
while s<>nil do begin
write((s^.x+ b^.x):field);
s:=s^.p1; b:=b^.p2;
end;
readkey;
end.
Можно еще убрать вызова textcolor, записывая атрибуты напрямую в переменную textattr, вызов функции - тоже время. Но оно тут не в цикле, поэтому можно пренебречь.

Можно суммировать только первую половину элементов списка, вторая записывается в обратном порядке, если зарезервировать еще один массив 1 .. n div 2, то можно сэкономить кое-что на последнем цикле, до n/2 записывая полученные суммы в массив, после n/2 - печатая уже готовые суммы в обратном порядке...

Хватит?
1147
good.gif Огромное спасибо volvo, этого разумеется хватит!
1147
Последний вопрос у меня, но не столько по самой программе, сколько по функции Gettime. Никак не получается измерить время выполнения программы. Соответствующие темы на форуме читал (http://forum.pascal.net.ru/index.php?showtopic=8585&st=0&p=58499&#entry58499), но применить не получается.. Исчерпал все возможные варианты (как видно все, кроме правильного), но время выполнения получить так и не удалось..
volvo
Твоя программа выполняется слишком быстро, чтобы засечь время выполнения способом с GetTime, и даже способом с чтением из MemL[$0040:$006C]...

У меня получилось замерить скорость выполнения твоей программы вот этим способом:
Использование счетчика тактов процессора (RDTSC)
1147
{$N+}

procedure ReadTSC(Var counter : Comp); far; external;
{$L tsc.obj}

Var a1, a2, a3 : Comp;
begin
ReadTSC(a1);
Writeln('Working : )');
ReadTSC(a2);
Writeln(a1:20:0, ', ', a2:20:0, ', ', (a2-a1):20:0)
end.


получилось следующим образом: процедура, дальше идет текст основной программы. Но программа не запускается.
Как вызвать эту процедуру и где?
volvo
Нет-нет... У тебя здесь - основная программа. Процедура - внешняя, здесь только ее прототип... То есть, ты должен заменить Writeln на свой код:

{$N+}
procedure ReadTSC(Var counter : Comp); far; external;
{$L tsc.obj}
Var a1, a2: Comp;

{
Тут - твои описания типов/переменных/констант
}

begin
ReadTSC(a1);
{
Тут - текст твоей программы, все что между begin и end...
}
ReadTSC(a2);
Writeln(a1:20:0, ', ', a2:20:0, ', ', (a2-a1):20:0)
end.
1147
Получается таким образом

{$N+}
procedure ReadTSC(Var counter : Comp); far; external;
{$L tsc.obj}
Var a1, a2: Comp;
Program din;
uses crt;
type tpo=^tn; tn=record x:real; p1,p2:tpo; end;
begin
.
.
.
.
end


но мне кажется что эту часть

Program din;
uses crt;
type
tpo = ^tn;
tn = record
x: shortint;
p1, p2: tpo;
end;
я не в том месте ставлю. изза этого ошибка..

Добавлено через 16 мин.
error 36: begin expected
1147
Так, ну с этим вопросом я разобрался, вот только текст у меня теперь весь сбивается при запуске...

Добавлено через 4 мин.
и еще... в каких единицах у нас получается время?
volvo
Цитата
только текст у меня теперь весь сбивается при запуске...
Значит, что-то сделал не так... У меня ничего не сбилось... Не с чего там сбиваться, программа выглядит точно так же, как и прежде, ПЕРЕД выводом твоих результатов ничего, кроме вызова одной-единственной функции, не происходит -> даже теоретически ничего не должно меняться.

Цитата
в каких единицах у нас получается время?
На сайте ж написано: в тактах процессора.
1147
а почему значение времени выполнения программы каждый раз разное? Я 9 раз запустил программу, и каждый раз получал новый результат:
1446088
1193822
1281238
1196104
1179864
1251810
1390536
1161384
1216572

Добавлено через 7 мин.
и зачем нам нужно a3?
volvo
Потому что такты - вещь
1) очень чувствительная;
2) крайне ненадежная, поскольку у тебя не Real-Time ОС, а Windows, да? Многозадачная ОС, понимаешь ли. Как планировщик решит, так приложение и будет выполняться... Кстати, это касается и других способов замера времени тоже.

Добавлено через 46 сек.
A3 не нужно, опечатка, чуть позже исправлю...
1147
да, у меня windows. Но тогда получается что в результате оптимизированная программа вполне возможно будет работать дольше первоначальной smile.gif . Если с помощью gettime проверку сделать нельзя, то в данном случае, я так понимаю, вообще не получится произвести точного сравнения времени выполнения программ?

Добавлено через 1 мин.
или можно воспользоваться средним арифметическим значением...

Добавлено через 10 мин.
и еще.. в ассемблере например время выполнения программы всегда одинаковое. последний раз у меня было 47ms. и это значение не менялось. как это объясняется?
volvo
Делай среднее арифметическое. Способ с GetTime, кстати, тоже не дает точного времени выполнения... Попробуй напиши какую-нибудь длительно выполняющуюся программу (секунд на 5-6), засеки время ее работы с GetTime, а потом сделай то же самое, параллельно запустив какой-нибудь процесс с высоким приоритетом... Как ты думаешь, что будет? Время выполнения через GetTime совпадет? Вряд ли...

Добавлено через 8 мин.
Цитата
в ассемблере например время выполнения программы всегда одинаковое. последний раз у меня было 47ms. и это значение не менялось. как это объясняется?
47ms и 1 млн. тактов - это немного разные вещи, тебе не кажется? Сделай более точный замер времени ассемблерной программой, получишь тоже плавающие результаты... Начнем с того, что тактовая частота процессора сама по себе может изменяться... Но это уже тема для другого раздела, никак не для "Задач"
1147
Еще раз хочу поблагодарить тебя volvo, твоя помощь мне серьезно облегчила задачу, помогла понять что к чему
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.