Как можно улучшить эффективность и качество ПП? Опции

[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 - 29.01.2009 14:35

[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]

Если мы список заменим на массив, как это поможет избавиться от повторяющихся чисел???

Сообщение отредактировано: 1147 - 31.01.2009 6:16

[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]

Огромное спасибо volvo, этого разумеется хватит!

[1147]

Последний вопрос у меня, но не столько по самой программе, сколько по функции Gettime. Никак не получается измерить время выполнения программы. Соответствующие темы на форуме читал (http://forum.pascalnet.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 - 1.02.2009 14:06

[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 - 1.02.2009 14:47

[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. Но тогда получается что в результате оптимизированная программа вполне возможно будет работать дольше первоначальной . Если с помощью gettime проверку сделать нельзя, то в данном случае, я так понимаю, вообще не получится произвести точного сравнения времени выполнения программ?

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

Добавлено через 10 мин.
и еще.. в ассемблере например время выполнения программы всегда одинаковое. последний раз у меня было 47ms. и это значение не менялось. как это объясняется?