TList и динамические массивы

← →
mimas (2004-12-10 23:06) [0]

Работаю с построчным выводом полигона на канву. Нужно много и быстро просчитывать координаты и возвращать их из функции. Вот думаю в чем лучше их хранить: в списке TList или заталкивать в динамический массив. Варианты только такие, т.к. результирующие массивы координат нужно вернуть из функции.
Что посоветуете?

← →
Palladin © (2004-12-11 01:32) [1]

если работаешь с record то быстрей динмассивы, но в этом случае лишаешься удобств, которые можно вполне реализовать самому создав свой TList...

← →
Dema-X © (2004-12-11 06:54) [2]

быстрее статические массивы,так как Tlist и есть динамический массив,все тормоза начинаюся на создании ячейки динамического массива,поэтому если позаботится об этом заранее то по скорости будет примерно одинаково,если нужна скорость то можеш непосредсвенно со стеком или кучей через асм работать

← →
Digitman © (2004-12-11 12:45) [3]

> Dema-X © (11.12.04 06:54) [2]

> непосредсвенно со стеком или
> кучей через асм работать

что так жидко ?
ты еще посоветуй работать прямо в машкодах)

> mimas (10.12.04 23:06)
> в чем лучше их хранить: в списке TList или заталкивать
> в динамический массив

храни в чем угодно, великой разницы нет.

все преимущество дин.массивов сводится к тому, что время их жизни, скажем так, равно "времени жизни кода", их декларирующего ... т.е. во многих большинстве случаев не надо явно заботиться об освобождении ресурсов, занятых такими массивами .. здесь прослеживается прямая аналогия с типом [Ansi]String (длинными строками), работа компилятора с данными этого типа по сути мало отличается от работы с дин.массивами - компилятор точно так же вставляет в результ.код неявные операции по распределению/перераспределению/освобождению памяти, в зависимости от области видимости/использования стр.переменных.

списочно-ориентированные объекты на базе TList в ран-тайм требуют явных операций по их созданию/уничтожению, этим они, возможно, и не столь удобны в сравнении с дин.массивами, но зато они выигрывают в сквозной производительности операций с памятью за счет того что не оперируют (в отличии от дин.массивов) никакими заголовками

← →
Anatoly Podgoretsky © (2004-12-11 12:57) [4]

TList то же динамический массив, но не данных, а указателей на данные, поэтому при одинаковых условиях он медленнее.

← →
Digitman © (2004-12-11 13:07) [5]

> Anatoly Podgoretsky

Анатолий, согласись что в случае хранения в массиве кардиналов (или совместимых с кардиналом типов данных) указатель легко приводится к этому типу, и никаких "замедлений" нет и быть не может ..

тем паче что речь идет о "координатах" , которые (в первом предположении) хранятся в списке в виде ц/ч значений ..

← →
jack128 © (2004-12-11 13:11) [6]

Anatoly Podgoretsky © (11.12.04 12:57) [4]
TList то же динамический массив, но не данных, а указателей на данные, поэтому при одинаковых условиях он медленнее

Что такое "при одинаковых условиях"??? Если SizeOf(Record) > SizeOf(Pointer), то очевидно вставка и удаление будет быстрее с листом, доступ к элементу наверное помедленнее(лишнее разименовование)

← →
Digitman © (2004-12-11 13:17) [7]

ответ в ЛЮБОМ случае дает CPU-window
о чем мы здесь ?

← →
Anatoly Podgoretsky © (2004-12-11 13:21) [8]

jack128 © (11.12.04 13:11) [6]
Почему это быстрее, и то и другое динамический массив, то есть действую по тем же алгоритмам TList будет помедленне, не забыть также про создание субъекта и передаче его указателя в TList.
Вот динамический массив указателей будет практически одинаков по времени.
Ситуация такая
Pointer -> Pointer -> Data Pointer -> Data

← →
Digitman © (2004-12-11 13:26) [9]

> Anatoly Podgoretsky

а последующий доступ ? к эл-там того же TList или того же дин.массива ?

дин.массив, как помнится, всякий раз обращается к заголовку .. и там - куча инструкций, ощутимо больше, чем инструкций при обращении к тому же i-му эл-ту массива под управлением TList .. убеди в обратном ?

← →
Anatoly Podgoretsky © (2004-12-11 13:38) [10]

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

TList -> Method -> DynArray и операции с ним DynArray и операции с ним

← →
Digitman © (2004-12-11 13:41) [11]

> при этом добавляется и выполнение методов

выливается же это в вызов тех же стат. п/программ : call offset чего-то

← →
TUser © (2004-12-11 13:41) [12]

Еще надо сказать, что многое зависит от того, каким образом меняется размер дин. массива. Если, например,
for i:=0 to <много> do begin
SetLength(MyArray,length(MyArray)+1);
{do somthing that can affect in the memory rearrengment}
end;
то ясно, что TList быстрее - он память блоками по 64 начнет выделять с некоторого момента. Может так статься, что еще быстрее написание чего-то на него очень похожего, что выделяет блоки еще большего размера.
Также скажу, что мысли о скорости подобных операций должны нас волновать, только если таких операций очень много. Если несколько десятков в минуту и меньше - то все это совершенно не важно, т.к. пользователь разницы все равно не заметит.

← →
Anatoly Podgoretsky © (2004-12-11 14:27) [13]

Речь шла про одинаковые условия, так и надо одинаково откусывать память, а еше лучше сразу если это возможно.

← →
Verg © (2004-12-11 15:10) [14]

TList гибче, я считаю. Особенно имя ввиду его клоны - TObjectList, например. Легко хранить разношерстные объекты.

В принципе динамический массив - это быстрый доступ (как к отдельному элементу, так и к группе) и крайне медленное изменение состава.
Связный список ему полная противоположность минус высокая фрагментация кучи.
Бинарное дерево может поспорить и с тем и с другим, если есть индексирование.
Можно комбинировать - данные хранить в массиве, а их сортировку делать по принципу бинарного дерева, т.е. исключив физическое премещение данных при удалении, вставке. Свободные ячейки массива зачислять в связанный список, а не удалять их физически. Их же и использовать при добавлении новых элементов. В то же время снабдить их "временем жизни", что поможет реализовать "сборщик мусора".

Надо выбирать каждый раз по задаче, а не раз и навсегда.

← →
Digitman © (2004-12-11 15:27) [15]

> Verg © (11.12.04 15:10) [14]

> выбирать каждый раз по задаче

от уж точно.
согласен на все сто.
а для сего нужно ЧЕТКО (хотя бы для самого себя) сформулировать конечную задачу.
по-русски еще говорят - получить/реализовать ТЗ.
без ТЗ все это - баловство.

Я бы сказал Микро-ТЗ. На конкретную, поставленную реализацию некой функциональности.
Вот тут мне "подопечный" принес показать как он понял задачу об "N-таймеров". Я ее посмотрел, применил, еще раз посмотрел.. ну короче даже не знаю "пять ставить, или пять с минусом"? :)))

unit TimerManag; interface uses Windows, Classes, SyncObjs; type PTimerObject = ^TTimerObject; TTimerProc = procedure(var Sender : PTimerObject) of object; TTimerObject = record StartTick : DWORD; Interval : DWORD; OneShort : boolean; Proc : TTimerProc; Sync : boolean; Fired : boolean; case Rip : boolean of false: ( Data : pointer;); true : ( NextRip : PTimerObject;); end; type TTimerManager = class(TThread) private FRipRoot : PTimerObject; FTimerList : TList; FCs : TCriticalSection; NeedSort : boolean; FSyncEvent : TEvent; FProcTmr : PTimerObject; FRipCount : integer; FFiredCount : integer; function ProcessTimers : DWORD; procedure DoFunc; procedure Sort(BasT : DWORD); function GetCount: integer; protected destructor Destroy; override; procedure Execute; override; public constructor Create; procedure CreateTimer(var Result : PTimerObject; AInterval : DWORD; AOneShort : boolean; AData : pointer; AProc : TTimerProc; ASync : boolean = false); procedure KillTimer( var Tmr : PTimerObject; Destroy : boolean = true ); procedure Done; procedure Dump( Lst : TStrings ); property Count : integer read GetCount; property RipCount : integer read FRipCount; property FiredCount : integer read FFiredCount; end; implementation uses SysUtils; constructor TTimerManager.Create; begin inherited Create(true); FreeOnTerminate := false; FCs := TCriticalSection.Create; FTimerList := TList.Create; FSyncEvent := TEvent.Create(nil, true, false, ""); resume; end; function TTimerManager.GetCount; begin FCs.Enter; try Result := FTimerList.Count; finally FCs.Leave; end; end; destructor TTimerManager.Destroy; var Tmr : PTimerObject; begin While FTimerList.Count > 0 do begin Tmr := PTimerObject(FTimerList[0]); FTimerList.Delete(0); Dispose(Tmr); end; FTimerList.Free; FSyncEvent.Free; FCs.Free; inherited; end; procedure TTimerManager.Done; begin FCs.Enter; try Terminate; FSyncEvent.SetEvent(); finally FCs.Leave; WaitFor; Free; end; end; function Fired(Tc : DWORD; Tmr : PTimerObject): boolean; begin Result := Tc - Tmr^.StartTick >= Tmr^.Interval; end; var T : DWORD; function TCompare( Item1, Item2 : pointer) : integer; var Tmr1, Tmr2 : PTimerObject; D1, D2 : DWORD; F1, F2 : boolean; begin Tmr1 := Item1; Tmr2 := Item2; F1 := Tmr1^.Rip or Tmr1^.Fired; F2 := Tmr2^.Rip or Tmr2^.Fired; if F1 or F2 then begin if F1 = F2 then Result := 0 else begin if F1 then Result := 1 else Result := -1; end; exit; end; F1 := Fired(T, Tmr1); F2 := Fired(T, Tmr2); if F1 and F2 then Result := 0 else if F1 then result := -1 else if F2 then result := 1 else begin D1 := Tmr1^.StartTick + Tmr1^.Interval - T; D2 := Tmr2^.StartTick + Tmr2^.Interval - T; if D1= D2 then result := 0 else result := ord(D1 > D2 )*2 - 1; end; end; procedure TTimerManager.Sort(BasT : DWORD); begin T := BasT; if NeedSort then begin FTimerList.Sort(TCompare); NeedSort := false; end; end; procedure TTimerManager.DoFunc; begin FProcTmr^.Proc( FProcTmr ); end; function TTimerManager.ProcessTimers : DWORD; label l1; var I : integer; begin FCs.Enter; try FSyncEvent.ResetEvent(); Result := 0; if Terminated then exit; Sort( GetTickCount() ); L1:; I := 0; while I < FTimerList.Count do begin FProcTmr := PTimerObject(FTimerList[I]); if not (FProcTmr^.Rip or FProcTmr^.Fired) then begin if Fired(GetTickCount(), FProcTmr) then begin NeedSort := true; if Assigned(FProcTmr^.Proc) then begin if FProcTmr^.Sync then begin FCs.Leave; Synchronize(DoFunc); FCs.Enter; if Terminated then exit; end else DoFunc; end; if FProcTmr <> nil then begin if FProcTmr^.OneShort then KillTimer( FProcTmr, false ) else FProcTmr^.StartTick := GetTickCount(); end; end else break; end; Inc(I); end; Sort( GetTickCount() ); if FtimerList.Count > 0 then begin FProctmr := PTimerObject(FTimerList[0]); if not (FProctmr^.Rip or FProctmr^.Fired) then begin if Fired(T, FProcTmr) then begin Sleep(1); goto l1; end; Result := FProcTmr^.StartTick + FProcTmr^.Interval - T; if Result = INFINITE then result := INFINITE - 1; end else Result := INFINITE; end else Result := INFINITE; finally FCs.Leave; end; end; procedure TTimerManager.KillTimer( var Tmr : PTimerObject; Destroy : boolean = true ); var I, J : integer; begin FCs.Enter; try if Terminated then exit; if Tmr = nil then exit; I := FTimerList.IndexOf( Tmr ); if I < 0 then begin Dispose( Tmr ); Tmr := nil; end else begin if Destroy then begin if not Tmr^.Rip then begin Tmr^.Rip := true; NeedSort := true; Tmr^.NextRip := FRipRoot; FRipRoot := Tmr; Inc( FRipCount ); end; Tmr:= nil; end else begin if not Tmr^.Fired then Inc( FFiredCount ); Tmr^.Fired := true; end; NeedSort := true; {FSyncEvent.SetEvent;} end; finally FCs.Leave; end; end;

procedure TTimerManager.Execute; begin while not Terminated do FSyncEvent.WaitFor( ProcessTimers ); end; procedure TTimerManager.CreateTimer( var Result : PTimerObject; AInterval : DWORD; AOneShort : boolean; AData : pointer; AProc : TTimerProc; ASync : boolean = false); begin FCs.Enter; try if Terminated then exit; if (Result = nil) or (FTimerList.IndexOf(Result) < 0) or (Result^.Rip) then begin if FRipRoot = nil then begin new(Result); Result^.Fired := False; FTimerList.Add( Result ); end else begin Result := FRipRoot; FRipRoot := FRipRoot^.NextRip; Dec( FRipCount ); end; end; if Result^.Fired then Dec( FFiredCount ); Result^.NextRip := nil; Result^.StartTick:= GetTickCount(); Result^.Interval := AInterval; Result^.OneShort := AOneShort; Result^.Proc := AProc; Result^.Data := AData; Result^.Sync := ASync; Result^.Rip := False; Result^.Fired := False; NeedSort := true; FSyncEvent.SetEvent; finally FCs.Leave; end; end; procedure TTimerManager.Dump( Lst : TStrings ); var I : integer; S : string; Tmr : PTimerObject; T : DWORD; begin FCs.Enter; try Lst.Add("Count="+IntToStr(Count)+" Fired="+IntToStr(FiredCount)+" Riped="+IntToStr(RipCount)); for I:=0 to FTimerList.Count -1 do begin T := GetTickCount(); Tmr := PTimerobject(FTimerList[I]); S:= IntToStr(I)+#9; S:=S + IntToStr( Tmr^.Interval ) + #9; if T - Tmr^.StartTick >= Tmr^.Interval then S := S+ "expired" else S :=S + IntToStr(Tmr^.StartTick + Tmr^.Interval - T); S := S; if Tmr^.Rip then S:= S+#9"RIP"; if Tmr^.Fired then S:= S+#9"FIRED"; Lst.Add( S ); end; finally FCs.Leave; end; end; end.

Verg © (11.12.04 16:21) [17]

А чего ОНО делает ? А то, если честно, не понятно. Выпрямители там, тумбы разные... (с)

С уважением,

Таймеры там, таймеры. Элементраные отсчетчики времени... Много, сколь угодно много. Время каждый считает - либо приодически, либо одноразово. Каждый может быть остановлен в любое на выбор заказчика время. Управляемо не должно заисеть от наличия цикла выборки сообщений у заказчика. Максимально кросс. TTimer (settimer) - запрещен по условию. Допускается пногопоточность. Требование - минимум потоков (лучше вообще без привязки к конкретной "тематике" ОС, единственное - она точно многозадачна) при максимуме разрешающей способности (минимум накладных расходов по быстродействию самого "движка"). Минимум расхода памяти, при всех вышеперечисленных условиях.

В данном случае, решение применить TList (Sort) и tStrings в Dump-е в расчет не берутся, как легко реализуемые на любой платформе, на любом языке.

Кстати, вот одно к "минусу"
if Result = INFINITE then
result := INFINITE - 1;

Кто ему дал право отнимать какие-то чиселки из INFINITE?

Как сделать? - Я бы назначил любое число >= 1 просто

дин. массивы быстрее при доступе к элементам, т.к. не труебуется вызов метода get. В случае добавления - быстрее tlist. Той же скорости можно добиться и в dynarrays, если самому реализовать подход из TList с count и capacity.

TList и динамические массивы - что быстрее? Найти похожие ветки