{ TKeurmeesterList }
program pgmSearchLists;
{$mode objfpc}{$H+}
uses
Classes,
SysUtils,
fgl, uRdtsc,
StrUtils,
DateUtils,
AVL_Tree;
type
TKeurmeester = class
id: Integer;
naam: String;
end;
{ TKeurmeesterList }
TKeurmeesterList = class(specialize TFPGObjectList<TKeurmeester>)
type
TIDMap = specialize TFPGMap<Integer, Integer>;
private
fIDMap: TIDMap;
fAVLTree: TAvlTree;
fAVLWorkObj: TKeurmeester;
public
constructor Create;
destructor Destroy; override;
function Add(aItem: TKeurmeester): Integer;
procedure Delete(aIndex: Integer);
function LocateKeurmeester(id: Integer): Boolean;
function LocateKeurmeesterIn(id: Integer): Boolean;
function LocateKeurmeesterMap(id: Integer): Boolean;
function LocateKeurmeesterAVL(id: Integer): Boolean;
function AvlTreeCompare(Tree: TAVLTree; Data1, Data2: Pointer): integer;
procedure BeginUpdate;
procedure EndUpdate;
end;
{ TKeurmeesterList }
constructor TKeurmeesterList.Create;
begin
inherited Create;
fIDMap := TIDMap.Create;
fIDMap.Duplicates := dupIgnore;
fIDMap.Sorted := True;
fAVLTree:= TAVLTree.CreateObjectCompare(@AvlTreeCompare);
fAVLWorkObj:=TKeurmeester.Create;
end;
destructor TKeurmeesterList.Destroy;
begin
fIDMap.Free;
fAVLTree.Free;
fAVLWorkObj.Free;
inherited Destroy;
end;
function TKeurmeesterList.Add(aItem: TKeurmeester): Integer;
begin
Result := inherited Add(aItem);
fIDMap.Add(aItem.id, Result);
fAVLTree.Add(aItem);
end;
procedure TKeurmeesterList.Delete(aIndex: Integer);
var
idx: Integer;
lNode: TAVLTreeNode;
begin
idx := fIDMap.IndexOf(Items[aIndex].id);
if idx >= 0 then
fIDMap.Delete(idx);
if idx >= 0 then begin
lNode := fAVLTree.Find(Items[idx]);
if assigned(lNode) then
fAVLTree.Delete(lNode);
end;
inherited Delete(aIndex);
end;
function TKeurmeesterList.LocateKeurmeester(id: Integer): Boolean;
var
i: Integer;
begin
Result := False;
for i := 0 to Count - 1 do
begin
if Items[i].id = id then
begin
Result := True;
break;
end;
end;
end;
function TKeurmeesterList.LocateKeurmeesterIn(id: Integer): Boolean;
var
ki: TKeurmeester;
begin
Result := False;
for ki in Self do
begin
if ki.id = id then
begin
Result := True;
break;
end;
end;
end;
function TKeurmeesterList.LocateKeurmeesterMap(id: Integer): Boolean;
begin
Result := fIDMap.IndexOf(id) >= 0;
end;
function TKeurmeesterList.LocateKeurmeesterAVL(id: Integer): Boolean;
begin
fAVLWorkObj.id:=id;
Result := Assigned(fAVLTree.Find(fAVLWorkObj));
end;
function TKeurmeesterList.AvlTreeCompare(Tree: TAVLTree; Data1, Data2: Pointer
): integer;
var
lData1: TKeurmeester absolute Data1;
lData2: TKeurmeester absolute Data2;
begin
Result := lData1.id-lData2.id;
end;
procedure TKeurmeesterList.BeginUpdate;
begin
fIDMap.Sorted := False;
end;
procedure TKeurmeesterList.EndUpdate;
begin
fIDMap.Sort;
fIDMap.Sorted := True;
end;
const
cNCount = 100000; // Number of items
cRndCount = 512; // List if random items to search (mul of 2 for easy masking
var
lTFAr: array[Boolean] of integer; // True false count
procedure ClearTFAr;
begin
lTFAr[False] := 0;
lTFAr[True] := 0;
end;
var
kl: TKeurmeesterList;
ki: TKeurmeester;
i, j, n, v, vl: Integer;
// valarr: Array [1..4] of Integer = (5378, 478315, 999998, 9999999);
valarr: Array [0..cRndCount-1] of Integer;
lIx: Integer;
dt: TDateTime;
lStart: Qword;
begin
n := cNCount;
dt := Now;
//create list with data
kl := TKeurmeesterList.Create;
kl.BeginUpdate;
for i := 0 to n - 1 do
begin
ki := TKeurmeester.Create;
ki.id := i;
ki.naam := 'Item ' + IntToStr(i);
kl.Add(ki);
end;
kl.EndUpdate;
WriteLn('prepare data: ', MillisecondsBetween(Now, dt));
// Generate random values in valarr (~half below limit and half above }
for i:= Low(valarr) to High(valarr) do
valarr[i] := Random(n*3) div 2;
for j := 1 to 4 do
begin
v := (j * cNCount) div 4;
WriteLn('==========================');
WriteLn('Check random IDs for nbitems = ', v);
WriteLn('--------------------------');
//"for in" test
ClearTFAr;
lStart := CPUTickStamp;
dt := Now;
for i := 0 to v do begin
lIx := i and (cRndCount - 1);
inc(lTFAr[kl.LocateKeurmeesterIn(valarr[lIx])]);
end;
WriteLn('"for in" loop time in ms: ', MillisecondsBetween(Now, dt),
'; ', RdtscElapsed(lStart, CPUTickStamp),
Format('; result: True:%d False:%d', [lTFAr[True], lTFAr[False]]));
//"for to do" test
ClearTFAr;
lStart := CPUTickStamp;
dt := Now;
for i := 0 to v do begin
lIx := i and (cRndCount - 1);
inc(lTFAr[kl.LocateKeurmeester(valarr[lIx])]);
end;
WriteLn('"for to do" loop time in ms: ', MillisecondsBetween(Now, dt),
'; ', RdtscElapsed(lStart, CPUTickStamp),
Format('; result: True:%d False:%d', [lTFAr[True], lTFAr[False]]));
//map test
ClearTFAr;
lStart := CPUTickStamp;
dt := Now;
for i := 0 to v do begin
lIx := i and (cRndCount - 1);
inc(lTFAr[kl.LocateKeurmeesterMap(valarr[lIx])]);
end;
WriteLn('map time in ms: ', MillisecondsBetween(Now, dt),
'; ', RdtscElapsed(lStart, CPUTickStamp),
Format('; result: True:%d False:%d', [lTFAr[True], lTFAr[False]]));
//AVLTree test
ClearTFAr;
lStart := CPUTickStamp;
dt := Now;
for i := 0 to v do begin
lIx := i and (cRndCount - 1);
Inc(lTFAr[kl.LocateKeurmeesterAVL(valarr[lIx])]);
end;
WriteLn('AVL time in ms: ', MillisecondsBetween(Now, dt),
'; ', RdtscElapsed(lStart, CPUTickStamp),
Format('; result: True:%d False:%d', [lTFAr[True], lTFAr[False]]));
end;
kl.Free;
ReadLn;
end.
Recent
