![]() |
![]() ![]() |
![]() |
Bokul |
![]()
Сообщение
#1
|
![]() Гуру ![]() ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 1 117 Пол: Мужской Реальное имя: Богдан Репутация: ![]() ![]() ![]() |
Реализовал объект многоугольник, который имеет неопределенное количество вершин. Но скорость работы с ним критическая, поэтому надо как можно сильнее его оптимизировать.
Вот, что он из себя представляет:
unit Polygone;
interface
uses UnitTVector,ListOfVertex,objects;
TPPolygone=^TPolygone;
TPolygone=object
List:TVertexList;//Кольцевой список
constructor init;//инициализируем поля
procedure AddVertex(x,y:integer);//добавляем вершину, x,y - ее координаты
procedure Increase(Const vector:TVector);//Увеличиваем координаты всех вершины на вектор vector, описание - ниже
procedure Decrease(Const vector:TVector);//Уменьшаем координаты всех вершины на вектор vector, описание - ниже
procedure ForEach(proc:ToDO);//Проделываем процедуру типа ToDO с каждой вершиной
function ContainsPoint(point:TPoint):boolean;//входит ли точка point в объект
function IsInside(OtherPolyg:TPolygone):boolean;//входит ли объект в OtherPolyg
function ContainsOtherPolyg(OtherPolyg:TPolygone):boolean;// входит ли OtherPolyg в объект
destructor done;//Удаляем все поля
end;
Кольцевой список
unit ListOfVertex;
interface
uses objects;
type
ToDo=procedure(point:TPoint);//тип процедуры, вызываемой с ForEach
TPVertexItem=^TVertexItem;//элемент списка
TVertexItem=record
vertex:TPoint;//информационная часть - координаты вершины
next:TPVertexItem;
end;
TPVertexList=^TVertexList;
TVertexList=object
Last:TPVertexItem;
constructor init;//инициализируем поля
procedure AddElement(data:TPoint);//добавляем новый элемент
function DeleteElement(p:TPVertexItem):boolean;//удаляем элемент
procedure ForEach(proc:ToDo);//Проделываем процедуру типа ToDO с каждым элементом
destructor done;//удаляемся
end;
Модуль для работы с векторами
unit UnitTVector;
interface
Type
TVector=record
X,Y:integer;
end;
Operator + (Const v1,v2:TVector) R:TVector; //складываем два вектора
Operator - (Const v1,v2:TVector) R:TVector;//отнимаем от первого вектора второй
Operator * (Const k:double; v:TVector) R:TVector;//перемножаем вектор на коэффициент k
Operator * (Const v:TVector; k:double) R:TVector;//тоже самое, только другой порядок
Operator / (Const v:TVector; k:double) R:TVector;//делим вектор на коэффициент
Программа для проверки минимальной работоспособности
uses crt,ListOfVertex,objects, UnitTVector, Polygone;
procedure Show(p:TPoint);
begin
writeln('X = ',p.x,' Y = ',p.y);
end;
var obj1,obj2:TPPolygone;
p1:TPoint;
mem:longint;
vector:TVector;
begin
clrscr;
mem:=GetHeapStatus.TotalFree;
vector.x:=4;
vector.y:=8;
p1.x:=40;
p1.y:=50;
new(obj2,init);
with obj2^ do
begin
AddVertex(30,10);
AddVertex(30,20);
AddVertex(50,20);
AddVertex(50,10);
end;
new(obj1,init);
with obj1^ do
begin
AddVertex(10,10);
AddVertex(40,60);
AddVertex(1000,10);
writeln('First');
ForEach(show);
writeln;
writeln('Point x=',p1.x,' y=',p1.y);
if ContainsPoint(p1) then writeln('First contains Point')
else writeln('First does not contain Point');
writeln;
Writeln('After decrease: ');
writeln('Vector: x=',vector.x,' y=',vector.y);
decrease(vector);
ForEach(show);
writeln;
writeln('Second');
obj2^.ForEach(show);
if ContainsOtherPolyg(obj2^) then writeln('First contains second object')
else writeln('First does not contain second object');
if IsInside(obj2^) then writeln('Second is inside first object')
else writeln('Second is not inside first object');
end;
dispose(obj1,done);
dispose(obj2,done);
writeln;
writeln('Difference: ',mem-GetHeapStatus.TotalFree);
readln;
end.
Три модуля вмести: ![]() PS в принципе код прозрачен, но если что-то не понятно - спрашивайте. ![]() -------------------- Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее. |
volvo |
![]()
Сообщение
#2
|
Гость ![]() |
Хм... Чего тут пока оптимизировать - непонятно... Я бы сделал версию со статистикой (причем, используя директивы {$IFDEF}, хорошая статистика она никогда не помешает, но надо, чтоб ее можно было отключать быстро, а не переписывать из-за этого пол-программы), сколько раз какая функция/метод вызывается (если пойти чуть дальше - сколько времени в среднем выполняется каждый метод), и запустил бы эту версию, скажем, для нескольких сотен ( может, тысяч, все зависит от того, сколько времени ты согласен ждать ответа программы
![]() И вот когда программа тебе сообщит, что один метод вызывается 100 раз, а другой - 500000, ты будешь точно знать, на какой из них надо обращать внимание, а на какой - не очень... P.S. Цитата(Console) ... First contains second object Second is not inside first object Difference: -32768 ![]() Кстати, почему бы Increase/Decrease тоже не реализовать через ForEach? |
Bokul |
![]()
Сообщение
#3
|
![]() Гуру ![]() ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 1 117 Пол: Мужской Реальное имя: Богдан Репутация: ![]() ![]() ![]() |
Цитата Я бы сделал версию со статистикой (причем, используя директивы {$IFDEF}, хорошая статистика она никогда не помешает, но надо, чтоб ее можно было отключать быстро, а не переписывать из-за этого пол-программы) Да, правильно - так и надо, сделаем... Цитата (если пойти чуть дальше - сколько времени в среднем выполняется каждый метод) Как в Fpc засекать время? Цитата Кстати, почему бы Increase/Decrease тоже не реализовать через ForEach? Вообще то сначала они у меня были в виде перегруженных операторов (+-), но никак не получалось заставить их правильно работать - один из аргументов менял свое значение в независимости от того, как я его передавал в подпрограмму (оно и правильно, ведь если мы даже скопируем ссылку, данные расположенные по ее адресу останутся на месте). А почему без ForEach - для этого процедуре надо передавать еще один параметр - вектор, но ForEach работает только с таким типом ToDo=procedure(point:TPoint);
PS volvo, где у тебя произошла такая утечка? ![]() -------------------- Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее. |
volvo |
![]()
Сообщение
#4
|
Гость ![]() |
Цитата где у тебя произошла такая утечка? ![]() У меня? Я запустил только твою программу, буква в букву, как ты ее привел, так что утечка - у тебя... Цитата Как в Fpc засекать время? uses windows;
var T: dword;
...
T := gettickcount();
// ...
writeln('time = ', gettickcount() - T);
Я думаю, этого будет достаточно, если сделать огромное количество вычислений... Можно, конечно, и поточнее время замерять, но с этим, я думаю, не стОит заморачиваться...Цитата А почему без ForEach - для этого процедуре надо передавать еще один параметр - вектор, но ForEach работает только с таким типом Ну, во-первых, перегрузку функций еще никто не отменял, ты не в TP, а в ObjectPascal-е, кстати, можно было бы и перегрузить, если, конечно, такие функции будут вызываться достаточно часто... А во-вторых,Цитата Вообще то сначала они у меня были в виде перегруженных операторов (+-), но никак не получалось заставить их правильно работать - показывай, как перегружал, у меня после добавления перегрузки operator + (const p: TPoint; const v: TVector) R: TPoint;
operator - (const p: TPoint; const v: TVector) R: TPoint;
в модуль UnitTVector вот такой код:procedure TPolygone.Decrease(Const Vector:TVector);
var p, the_last:TPVertexItem;
begin
the_last:=List.last^.next;
p := the_last;
repeat
p^.vertex -= vector; // Как тебе такая запись ?
p:=p^.next;
until p = the_last;
end;
отрабатывает без проблем... Кстати, это тебе хинт, как немного оптимизировать программу, вместо того, чтоб каждый раз брать List^.Last^.next, берешь его один раз, и сравниваешь с текущим значением P ![]() |
Bokul |
![]()
Сообщение
#5
|
![]() Гуру ![]() ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 1 117 Пол: Мужской Реальное имя: Богдан Репутация: ![]() ![]() ![]() |
Цитата У меня? Я запустил только твою программу, буква в букву, как ты ее привел, так что утечка - у тебя... ![]() Цитата показывай, как перегружал, у меня после добавления перегрузки Я не совсем то, что ты перегружал (в модуле Polygone они закомментированные):
operator + (Polygone:TPolygone; Const Vector:TVector) R:TPolygone;
operator - (Polygone:TPolygone; Vector:TVector) R:TPolygone;
Так Polygone менял свои значения вмести с R ![]() Цитата Как тебе такая запись ? ![]() ![]() Цитата Кстати, это тебе хинт, как немного оптимизировать программу, вместо того, чтоб каждый раз брать List^.Last^.next, берешь его один раз, и сравниваешь с текущим значением P Спасибо! Только это скорее first чем last, это же связанный список и Last^.next указывает на первый элемент. ![]() -------------------- Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее. |
Bokul |
![]()
Сообщение
#6
|
![]() Гуру ![]() ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 1 117 Пол: Мужской Реальное имя: Богдан Репутация: ![]() ![]() ![]() |
Цитата И программу проверки мою??? Я имею ввиду при каких данных происходит такая утечка.. Есть вопросы по статистике: 1 При подключении модуля windows к модулю Polygone, наверное, проходит совмещения типов и компилятор начинает сердится на строку
procedure TPolygone.AddVertex(x,y:integer);
var point:TPoint;
begin
point.x:=x;
point.y:=y;
List.AddElement(point);//polygone.pas(132,27) Error: Incompatible type for arg no. 1: Got "POINT", expected "TPoint"
2 Статистику надо собирать по каждой подпрограмме запускаемой во всех модулях? -------------------- Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее. |
volvo |
![]()
Сообщение
#7
|
Гость ![]() |
Цитата Я имею ввиду при каких данных происходит такая утечка.. При твоих... Copy+Paste из твоего первого сообщения + Build + Run = (результат ты видел) ![]() Цитата При подключении модуля windows к модулю Polygone, наверное, проходит совмещения типов и компилятор начинает сердится на строку Берем бубен, 3 раза обходим вокруг компа, не забывая пропеть какую-нибудь песню, напоминающую песнь чукчи в тундре (не забудь, именно ТРИ раза!!!), потом снова садимся за компьютер, меняем местами названия модулей:unit Polygone;
interface
uses windows, objects, UnitTVector,ListOfVertex; // <--- Вот так...
и смотрим, что будет... ![]() Цитата Статистику надо собирать по каждой подпрограмме запускаемой во всех модулях? Я бы собирал статистику по каждому методу в программе... Для всех объектов - при вызове метода увеличить счетчик, и все... Потом пригодится... Распечатаешь все счетчики - сразу увидишь, что НАДО оптимизировать, а что НЕТ...Если то же самое сделаешь со временем - будет еще лучше, возможно метод-то вызывается 10 раз, но пожирает при этом 80% времени - его и будем ускорять... |
Bokul |
![]()
Сообщение
#8
|
![]() Гуру ![]() ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 1 117 Пол: Мужской Реальное имя: Богдан Репутация: ![]() ![]() ![]() |
Цитата При твоих... Copy+Paste из твоего первого сообщения + Build + Run = (результат ты видел) Точно, почему я сам это не увидел ![]() ![]() -------------------- Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее. |
Bokul |
![]()
Сообщение
#9
|
![]() Гуру ![]() ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 1 117 Пол: Мужской Реальное имя: Богдан Репутация: ![]() ![]() ![]() |
Попытался добавить статистику, но как-то не сильно она хочет работать - надо суровую руку профи приложить..
![]() Что я сделал: Добавил в объект ТPolygone поле Stat типа TAboutPol для хранения интересующей нас информации о каждом методе
TData=record
time,n:longint;
end;
TAboutPol=record
init,AddVertex,Increase,Decrease,ForEach,
ContainsPoint,IsInside,ContainsOtherPolyg,done:TData;
Так как я не могу проверить в программе утечек (из-за проблемы, описанной в теме "Шаровая" оперативка ), то и все мои попытки избавление от них остались тщетными (а может их прсто нет? ![]() ![]() Статистика тоже хромает по непонятным для меня причинам: ![]() первый столбик (nomber) отвечает за количество вызовов каждого метода, но они должны быть разные - ведь метод ContainsPoint запускается каждый раз при выполнении ContainsOtherPolyg или IsInside. ![]() ![]() ![]() ![]() Присоединяю архив с добавленной статистикой для Polygone, модулем ListOfVertex, избавленным от нескольких багов и программу вывода статистики ![]() -------------------- Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее. |
volvo |
![]()
Сообщение
#10
|
Гость ![]() |
Цитата Попытался добавить статистику, но как-то не сильно она хочет работать Чего-то ты переусложнил по-моему работу со статистикой... Смотри, как это же делал бы я:1. Пишем очень простой модуль: unit stat;
interface
type
tstatindex = (
siInit, siAddVertex, siIncrease, siDecrease,
siForEach, siContainsPoint, siContainsOtherPolyg,
siInside, siDone);
tstatrec = record
time: dword;
counter: dword;
end;
var
stat_array: array[tstatindex] of tstatrec;
// Назначение следующих 2-х переменных поймешь позже...
curr_stat: tstatindex;
curr_T: dword;
procedure print_stat;
implementation
const
title: array[tstatindex] of string = (
'Init',
'siAddVertex',
'siIncrease',
'siDecrease',
'siForEach',
'siContainsPoint',
'siContainsOtherPolyg',
'siInside',
'siDone'
);
procedure print_stat;
var i: tstatindex;
begin
writeln('methods calling:');
for i := low(tstatindex) to high(tstatindex) do
with stat_array[ i ] do begin
write(title[ i ] + ': ', 'count:: ', counter:6,
' time:: ', time:6);
if counter = 0 then writeln(' zero division')
else writeln(' average:: ', (time / counter): 10 :5);
end;
end;
end.
Как видишь - ничего особенного, просто выделяем место для хранения статистики, и процедура для их печати2. Пишем 2 очень маленьких файлика: before.inc begin
inc(stat_array[curr_stat].counter);
curr_T := gettickcount();
end;
и after.inc begin
inc(stat_array[curr_stat].time, gettickcount() - curr_T);
end;
3. Зачем? А вот зачем: теперь вместо конструкции вида: procedure TPolygone.ForEach(proc:ToDO);
{$ifdef StatisticPolygone}var t:dword; {$endif}
begin
{$ifdef StatisticPolygone}
t:=gettickcount();
{$endif}
list.foreach(proc);
{$ifdef StatisticPolygone}
inc(Stat.ForEach.time,gettickcount-t);
inc(Stat.ForEach.n);
{$endif}
end;
достаточно написатьprocedure TPolygone.ForEach(proc:ToDO);
begin
curr_stat := siForEach;
{$i before.inc}
list.foreach(proc);
{$i after.inc}
end;
(понятно назначение тех двух переменных - я ввел их просто чтобы не описывать вот эти вои локальные переменные, и сэкономить этим на объеме текста)... А проверять {$ifdef StatisticPolygone} можно и внутри файлов before.inc/after.incПеределал твою программу, добавив в нее свой модуль статистики - вот что получилось: Цитата(Console) ForEach: Number: 10000 Time: 15 Time for each: 0.001500 По-моему, больше похоже на правду... А насчет Difference я тебе уже сказал в другой теме, куда смотреть...Increase: Number: 10000 Time: 0 Time for each: 0.000000 Decrease: Number: 10000 Time: 15 Time for each: 0.001500 ContainsPoint: Number: 10000 Time: 47 Time for each: 0.004700 ContainsOtherPolyg: Number: 10000 Time: 0 Time for each: 0.000000 IsInside: Number: 10000 Time: 0 Time for each: 0.000000 methods calling: Init: count:: 10000 time:: 0 average:: 0.00000 siAddVertex: count:: 1000000 time:: 250 average:: 0.00025 siIncrease: count:: 10000 time:: 0 average:: 0.00000 siDecrease: count:: 10000 time:: 15 average:: 0.00150 siForEach: count:: 10000 time:: 15 average:: 0.00150 siContainsPoint: count:: 30000 time:: 47 average:: 0.00157 siContainsOtherPolyg: count:: 10000 time:: 0 average:: 0.00000 siInside: count:: 20000 time:: 0 average:: 0.00000 siDone: count:: 0 time:: 0 zero division Difference: -79872 |
Bokul |
![]() ![]()
Сообщение
#11
|
![]() Гуру ![]() ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 1 117 Пол: Мужской Реальное имя: Богдан Репутация: ![]() ![]() ![]() |
Цитата Смотри, как это же делал бы я: Красиво ![]() Цитата А насчет Difference я тебе уже сказал в другой теме, куда смотреть... Нашел утечку ![]() ![]() Вместо dispose(mas[i]);
надо dispose(mas[i],done);
Вот, какие данные получил я : ![]() Отчет heaprtc Цитата Heap dump by heaptrc unit 10100000 memory blocks allocated : 121200000/161600000 10100000 memory blocks freed : 121200000/161600000 0 unfreed memory blocks : 0 True heap size : 98304 (80 used in System startup) True free heap : 98224 Наверно ничего и не надо оптимизировать - ведь для нас критическими являются такие рабочие лошадки как ContainsPoint, ContainsOtherPolyg, Inside, а не AddVertex и Done, пожирающие почти все время, которые используются только при инициализации и в конце. -------------------- Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее. |
![]() ![]() |
![]() |
Текстовая версия | 29.07.2025 21:10 |