Recent

Author Topic: Yet another generics collection  (Read 20082 times)

sash

  • Sr. Member
  • ****
  • Posts: 366
Re: Yet another generics collection
« Reply #60 on: August 27, 2020, 05:17:45 pm »
Provided that you do not remove the vertices and edges of the graph while manipulating with it, this can be done in the destructor.
Well ... I do remove elements... so I wrote
Code: Pascal  [Select][+][-]
  1. function TMyGraph.DoRemoveEdge(aSrc, aDst : SizeInt) : Boolean;
  2. var
  3.   edg : TMyGraphEdge;
  4. begin
  5.   Result := false;
  6.   if GetEdgeDataI(aSrc, aDst, edg) then begin
  7.     Result := inherited DoRemoveEdge(aSrc, aDst);
  8.     if Result then
  9.       edg.Free;
  10.   end;
  11. end;
  12.  
Is it ok? Will it work on MyGraph.Clear() ?
« Last Edit: August 27, 2020, 05:27:56 pm by sash »
Lazarus 2.0.10 FPC 3.2.0 x86_64-linux-gtk2 @ Ubuntu 20.04 XFCE

avk

  • Sr. Member
  • ****
  • Posts: 415
    • my self-education project
Re: Yet another generics collection
« Reply #61 on: August 27, 2020, 06:02:44 pm »
OMG, I completely forgot about Clear.
It also needs to be overridden.

Provided that you do not remove the vertices and edges of the graph while manipulating with it, this can be done in the destructor.
Well ... I do remove elements... so I wrote
Code: Pascal  [Select][+][-]
  1. function TMyGraph.DoRemoveEdge(aSrc, aDst : SizeInt) : Boolean;
  2. var
  3.   edg : TMyGraphEdge;
  4. begin
  5.   Result := false;
  6.   if GetEdgeDataI(aSrc, aDst, edg) then begin
  7.     Result := inherited DoRemoveEdge(aSrc, aDst);
  8.     if Result then
  9.       edg.Free;
  10.   end;
  11. end;
  12.  

I would prefer like this:
Code: Pascal  [Select][+][-]
  1. function TMyGraph.DoRemoveEdge(aSrc, aDst : SizeInt) : Boolean;
  2. var
  3.   edg : TMyGraphEdge;
  4. begin
  5.   if GetEdgeDataI(aSrc, aDst, edg) and (inherited DoRemoveEdge(aSrc, aDst)) then begin
  6.     edg.Free;
  7.     exit(True);
  8.   end;
  9.   Result := False;  
  10. end;
  11.  

avk

  • Sr. Member
  • ****
  • Posts: 415
    • my self-education project
Re: Yet another generics collection
« Reply #62 on: August 27, 2020, 07:08:46 pm »
Perhaps something like this:
Code: Pascal  [Select][+][-]
  1. ...
  2. type
  3.  
  4.   TMyVertex = class
  5.   end;
  6.  
  7.   TMyEdge = class
  8.   end;
  9.  
  10.   TMyGraph = class(specialize TGSimpleGraph<TMyVertex, TMyEdge, TMyVertex>)
  11.   protected
  12.     procedure DoRemoveVertex(aIndex: SizeInt); override;
  13.     function  DoRemoveEdge(aSrc, aDst: SizeInt): Boolean; override;
  14.   public
  15.     destructor Destroy; override;
  16.     procedure Clear; override;
  17.   end;
  18.  
  19. implementation
  20. {$B-}{$COPERATORS ON}{$POINTERMATH ON}
  21. ...
  22. { TMyGraph }
  23.  
  24. procedure TMyGraph.DoRemoveVertex(aIndex: SizeInt);
  25. var
  26.   p: PAdjItem;
  27. begin
  28.   for p in AdjLists[aIndex]^ do
  29.     p^.Data.Free;
  30.   Items[aIndex].Free;
  31.   inherited DoRemoveVertex(aIndex);
  32. end;
  33.  
  34. function TMyGraph.DoRemoveEdge(aSrc, aDst: SizeInt): Boolean;
  35. var
  36.   e: TMyEdge;
  37. begin
  38.   if GetEdgeDataI(aSrc, aDst, e) and (inherited DoRemoveEdge(aSrc, aDst)) then
  39.     begin
  40.       e.Free;
  41.       exit(True);
  42.     end;
  43.     Result := False;
  44. end;
  45.  
  46. destructor TMyGraph.Destroy;
  47. begin
  48.   Clear;
  49.   inherited;
  50. end;
  51.  
  52. procedure TMyGraph.Clear;
  53. var
  54.   e: TEdge;
  55.   I: SizeInt;
  56. begin
  57.   for e in DistinctEdges do
  58.     e.Data.Free;
  59.   for I := 0 to Pred(VertexCount) do
  60.     Items[I].Free;
  61.   inherited;
  62. end;
  63.  

avk

  • Sr. Member
  • ****
  • Posts: 415
    • my self-education project
Re: Yet another generics collection
« Reply #63 on: August 28, 2020, 04:41:32 pm »
@sash, eventually I added TGSimpleObjGraph. It would be interesting to know your opinion.

sash

  • Sr. Member
  • ****
  • Posts: 366
Re: Yet another generics collection
« Reply #64 on: August 29, 2020, 01:33:38 pm »
@sash, eventually I added TGSimpleObjGraph. It would be interesting to know your opinion.

Thank you very much.
Updated to TGSimpleObjGraph.

Much more convenient. Seems like It works as it should. I didn't test allocations yet, but certainly will.
I'm glad you implemented OwnsXXX properties, don't know about edges, but my use-case assumes some vertices belongs to multiple graphs, so it's very handy.

Again (some more questions :))
- what happens with orphaned edges (when both connected vertices deleted)?
- can I replace an existing instance of vertex like
Code: Pascal  [Select][+][-]
  1. graph.Items[i].Free;
  2. graph.Items[i] := TAnotherVertex.Create;
?

Lazarus 2.0.10 FPC 3.2.0 x86_64-linux-gtk2 @ Ubuntu 20.04 XFCE

avk

  • Sr. Member
  • ****
  • Posts: 415
    • my self-education project
Re: Yet another generics collection
« Reply #65 on: August 30, 2020, 01:07:00 pm »
- what happens with orphaned edges (when both connected vertices deleted)?
- can I replace an existing instance of vertex like

1. Removal of any vertex of the graph implies the removal of all incident edges.
2. It would be safer like this:
Code: Pascal  [Select][+][-]
  1.   OldValue := graph.Items[i];
  2.   graph.Items[i] := TAnotherVertex.Create;
  3.   OldValue.Free;
  4.  
But the latest revision of the library will do this automatically(provided that the graph owns the vertices).

sash

  • Sr. Member
  • ****
  • Posts: 366
Re: Yet another generics collection
« Reply #66 on: August 30, 2020, 05:19:19 pm »
But the latest revision of the library will do this automatically(provided that the graph owns the vertices).
Do what? Free old contained object on assignment of new one?
Lazarus 2.0.10 FPC 3.2.0 x86_64-linux-gtk2 @ Ubuntu 20.04 XFCE

avk

  • Sr. Member
  • ****
  • Posts: 415
    • my self-education project
Re: Yet another generics collection
« Reply #67 on: August 30, 2020, 05:53:38 pm »
Yeah, exactly.

avk

  • Sr. Member
  • ****
  • Posts: 415
    • my self-education project
Re: Yet another generics collection
« Reply #68 on: October 19, 2020, 10:45:33 am »
Added a radix sort algorithm, so I ran the sorting benchmark again.
  • Rtl/SortBase denotes SortBase.QuickSort_ItemList_Context
  • Rtl-Generics - Generics.Collections.TArrayHelper.Sort
  • Fcl-Stl - gArrayUtils.TOrderingArrayUtils.Sort
  • PasPDQSort - TPDQSorter.Sort - Akira1364's Pascal translation of PDQSort from https://github.com/Akira13641/PasPDQSort
  • LG/QuickSort - TGOrdinalArrayHelper.QuickSort
  • LG/IntroSort - TGOrdinalArrayHelper.IntroSort
  • LG/DualPivotQuickSort - TGOrdinalArrayHelper.DualPivotQuickSort
  • LG/PDQSort - TGOrdinalArrayHelper.PDQSort
  • LG/MergeSort - TGComparableArrayHelper.MergeSort
  • LG/TimSort - TGComparableTimSort.Sort
  • LG/Sort - TGOrdinalArrayHelper(mostly uses radix sort)
A negative value indicates that the algorithm failed the test(exhibits quadratic behavior).
The benchmark was compiled with FPC 3.3.1-r46955 and ran on a win7-64bit machine.

avk

  • Sr. Member
  • ****
  • Posts: 415
    • my self-education project
Re: Yet another generics collection
« Reply #69 on: December 30, 2020, 06:57:56 am »
Added implementation of the JSON parser/generator.
It seems it passes all tests from JSONTestSuite.

As for performance, below are the results of a (quick and dirty) benchmark involving Delphi.JSON framework, JsonTools and FpJson.
The benchmark tries to measure the parsing performance(in Kb/s), sources can be found in the "LGenerics/example/json/parse_bench" folder.
It was compiled with FPC-3.3.1-r47862-win64 (-O3), Delphi code was compiled with Delphi 10.3.3 CE (win64, release).

Happy New Year!

OwlOfTime

  • Hero Member
  • *****
  • Posts: 3827
Re: Yet another generics collection
« Reply #70 on: January 04, 2021, 11:25:43 pm »
Wow, I need to try that Json, looks promising and in the graph faster than Json Tools.

I have some questions, because that caused me some headaches. This two bugs are present in your Json library?

https://github.com/sysrpl/JsonTools/issues/12

https://github.com/sysrpl/JsonTools/issues/11

Thanks, if that works, maybe we switch (again) of JSON Library.
« Last Edit: January 05, 2021, 12:11:36 am by lainz »
Just Why?

avk

  • Sr. Member
  • ****
  • Posts: 415
    • my self-education project
Re: Yet another generics collection
« Reply #71 on: January 05, 2021, 09:10:28 am »
Thank you.
Well my locale also uses a comma as the decimal separator.
At least this code
Code: Pascal  [Select][+][-]
  1. ...
  2. var
  3.   o: TJsonNode;
  4. begin
  5.   o := TJsonNode.NewJson('{"test": "one \"\"two\"\" three", "float value": 0.52875}');
  6.   Memo1.Append(o['test']);
  7.   Memo1.Append(Double(o['float value']).ToString);
  8.   Memo1.Append(o.FormatJson);
  9.   o.Free;
  10. end;
  11.  
prints
Code: Text  [Select][+][-]
  1. one ""two"" three
  2. 0,52875
  3. {
  4.     "test": "one \"\"two\"\" three",
  5.     "float value": 0.52875
  6. }
  7.  

OwlOfTime

  • Hero Member
  • *****
  • Posts: 3827
Re: Yet another generics collection
« Reply #72 on: January 05, 2021, 01:14:01 pm »
Thanks!  :)
Just Why?

avk

  • Sr. Member
  • ****
  • Posts: 415
    • my self-education project
Re: Yet another generics collection
« Reply #73 on: January 05, 2021, 01:56:34 pm »
You are welcome.

OwlOfTime

  • Hero Member
  • *****
  • Posts: 3827
Re: Yet another generics collection
« Reply #74 on: January 05, 2021, 02:09:34 pm »
Hi I have some questions on the LGJson usage

Code: Pascal  [Select][+][-]
  1. for j:=0 to tempData.Count-1 do
  2.            begin
  3.              // copy
  4.              tempObj := arr.AsArray.AddNode(jvkObject);
  5.              tempObj.AsJson := tempData.Items[j].AsJson;
  6.            end;
  7.            if not bPaginar then
  8.             b := False;
  9.            FreeAndNil(tempData);

tempData, tempObj and arr are al TJsonNode.

What I'm doing is making a copy of tempData into arr.

Basically I get an array from internet (tempData) and must join all the objects I get into (arr). I get several times tempData, and I free that in each iteration. (FreeAndNil(tempData)).

That way of copying the object is fine? Or there is a better way?

Edit: Anyways it works, and in our application works almost the same that JsonTools, I get the same time syncing the same data.

Edit2: Our bottleneck is in another castle!
« Last Edit: January 05, 2021, 04:28:05 pm by lainz »
Just Why?

 

TinyPortal © 2005-2018