Форум «Всё о Паскале» _ Free Pascal, Pascal ABC и другие _ Многоугольник
Автор: Bokul 26.12.2006 13:32
Реализовал объект многоугольник, который имеет неопределенное количество вершин. Но скорость работы с ним критическая, поэтому надо как можно сильнее его оптимизировать. Вот, что он из себя представляет:
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.
Три модуля вмести:Polygone.rar ( 13.71 килобайт )
Кол-во скачиваний: 603
PS в принципе код прозрачен, но если что-то не понятно - спрашивайте.
Автор: volvo 26.12.2006 13:59
Хм... Чего тут пока оптимизировать - непонятно... Я бы сделал версию со статистикой (причем, используя директивы {$IFDEF}, хорошая статистика она никогда не помешает, но надо, чтоб ее можно было отключать быстро, а не переписывать из-за этого пол-программы), сколько раз какая функция/метод вызывается (если пойти чуть дальше - сколько времени в среднем выполняется каждый метод), и запустил бы эту версию, скажем, для нескольких сотен ( может, тысяч, все зависит от того, сколько времени ты согласен ждать ответа программы ) полигонов, каждый из которых состоит из десятков/сотен вершин...
И вот когда программа тебе сообщит, что один метод вызывается 100 раз, а другой - 500000, ты будешь точно знать, на какой из них надо обращать внимание, а на какой - не очень...
P.S.
Цитата(Console)
... First contains second object Second is not inside first object
Difference: -32768
Кстати, почему бы Increase/Decrease тоже не реализовать через ForEach?
Автор: Bokul 26.12.2006 23:32
Цитата
Я бы сделал версию со статистикой (причем, используя директивы {$IFDEF}, хорошая статистика она никогда не помешает, но надо, чтоб ее можно было отключать быстро, а не переписывать из-за этого пол-программы)
Да, правильно - так и надо, сделаем...
Цитата
(если пойти чуть дальше - сколько времени в среднем выполняется каждый метод)
Как в Fpc засекать время?
Цитата
Кстати, почему бы Increase/Decrease тоже не реализовать через ForEach?
Вообще то сначала они у меня были в виде перегруженных операторов (+-), но никак не получалось заставить их правильно работать - один из аргументов менял свое значение в независимости от того, как я его передавал в подпрограмму (оно и правильно, ведь если мы даже скопируем ссылку, данные расположенные по ее адресу останутся на месте). А почему без ForEach - для этого процедуре надо передавать еще один параметр - вектор, но ForEach работает только с таким типом
ToDo=procedure(point:TPoint);
PS volvo, где у тебя произошла такая утечка?
Автор: volvo 27.12.2006 0:05
Цитата
где у тебя произошла такая утечка?
У меня? Я запустил только твою программу, буква в букву, как ты ее привел, так что утечка - у тебя...
Цитата
Как в Fpc засекать время?
uses windows; var T: dword; ... T := gettickcount(); // ... writeln('time = ', gettickcount() - T);
Я думаю, этого будет достаточно, если сделать огромное количество вычислений... Можно, конечно, и поточнее время замерять, но с этим, я думаю, не стОит заморачиваться...
Цитата
А почему без ForEach - для этого процедуре надо передавать еще один параметр - вектор, но ForEach работает только с таким типом
Ну, во-первых, перегрузку функций еще никто не отменял, ты не в TP, а в ObjectPascal-е, кстати, можно было бы и перегрузить, если, конечно, такие функции будут вызываться достаточно часто... А во-вторых,
Цитата
Вообще то сначала они у меня были в виде перегруженных операторов (+-), но никак не получалось заставить их правильно работать
- показывай, как перегружал, у меня после добавления перегрузки
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 27.12.2006 0:22
Цитата
У меня? Я запустил только твою программу, буква в букву, как ты ее привел, так что утечка - у тебя...
И программу проверки мою???
Цитата
показывай, как перегружал, у меня после добавления перегрузки
Я не совсем то, что ты перегружал (в модуле Polygone они закомментированные):
Кстати, это тебе хинт, как немного оптимизировать программу, вместо того, чтоб каждый раз брать List^.Last^.next, берешь его один раз, и сравниваешь с текущим значением P
Спасибо! Только это скорее first чем last, это же связанный список и Last^.next указывает на первый элемент.
Автор: Bokul 27.12.2006 1:28
Цитата
И программу проверки мою???
Я имею ввиду при каких данных происходит такая утечка..
Есть вопросы по статистике: 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 27.12.2006 1:41
Цитата
Я имею ввиду при каких данных происходит такая утечка..
При твоих... Copy+Paste из твоего первого сообщения + Build + Run = (результат ты видел)
Цитата
При подключении модуля windows к модулю Polygone, наверное, проходит совмещения типов и компилятор начинает сердится на строку
Берем бубен, 3 раза обходим вокруг компа, не забывая пропеть какую-нибудь песню, напоминающую песнь чукчи в тундре (не забудь, именно ТРИ раза!!!), потом снова садимся за компьютер, меняем местами названия модулей:
unit Polygone; interface uses windows, objects, UnitTVector,ListOfVertex; // <--- Вот так...
и смотрим, что будет...
Цитата
Статистику надо собирать по каждой подпрограмме запускаемой во всех модулях?
Я бы собирал статистику по каждому методу в программе... Для всех объектов - при вызове метода увеличить счетчик, и все... Потом пригодится... Распечатаешь все счетчики - сразу увидишь, что НАДО оптимизировать, а что НЕТ...
Если то же самое сделаешь со временем - будет еще лучше, возможно метод-то вызывается 10 раз, но пожирает при этом 80% времени - его и будем ускорять...
Автор: Bokul 27.12.2006 2:18
Цитата
При твоих... Copy+Paste из твоего первого сообщения + Build + Run = (результат ты видел)
Точно, почему я сам это не увидел Самое удивительное это что размер свободной области увеличивается
Автор: Bokul 27.12.2006 11:50
Попытался добавить статистику, но как-то не сильно она хочет работать - надо суровую руку профи приложить.. Что я сделал: Добавил в объект ТPolygone поле Stat типа TAboutPol для хранения интересующей нас информации о каждом методе
Так как я не могу проверить в программе утечек (из-за проблемы, описанной в теме http://forum.pascal.net.ru/index.php?showtopic=14937 ), то и все мои попытки избавление от них остались тщетными (а может их прсто нет? ), хотя при отладке модуля ListOfVertex ошибок, вроде, не возникало (отладка проделывалась также в Bp). Прога для тестирования - 4.rar ( 441 байт )
Кол-во скачиваний: 614
Статистика тоже хромает по непонятным для меня причинам: первый столбик (nomber) отвечает за количество вызовов каждого метода, но они должны быть разные - ведь метод ContainsPoint запускается каждый раз при выполнении ContainsOtherPolyg или IsInside. . Что еще интересно - я вижу (в Watches) как меняется переменная Stat.ContainsPoint.n при отладке, но получаю совсем другие результаты при выполнении!!! Искал ошибку целый день - безрезультатно .
Присоединяю архив с добавленной статистикой для Polygone, модулем ListOfVertex, избавленным от нескольких багов и программу вывода статистики Polygone.rar ( 16.08 килобайт )
Кол-во скачиваний: 570
Автор: volvo 29.12.2006 17:01
Цитата
Попытался добавить статистику, но как-то не сильно она хочет работать
Чего-то ты переусложнил по-моему работу со статистикой... Смотри, как это же делал бы я: 1. Пишем очень простой модуль:
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); 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 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
По-моему, больше похоже на правду... А насчет Difference я тебе уже сказал в другой теме, куда смотреть...
Автор: Bokul 30.12.2006 0:56
Цитата
Смотри, как это же делал бы я:
Красиво Единственный вопрос - как называется тип типа tstatindex?
Цитата
А насчет 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, пожирающие почти все время, которые используются только при инициализации и в конце.