Lazarus

Announcements => Third party => Topic started by: avk on February 04, 2019, 06:18:43 am

Title: Yet another generics collection
Post by: avk on February 04, 2019, 06:18:43 am
As a result of experiments with FPC generics:
https://github.com/avk959/LGenerics (https://github.com/avk959/LGenerics)
Tested on Windows and Linux.
Title: Re: Yet another generics collection
Post by: Alextp on February 04, 2019, 07:22:41 am
Collection of generic algorithms and data structures entirely written in/for FPC and Lazarus. Started as a self-education project, it now seems quite comfortable and fast. In order to use it (FPC 3.1.1 and higher and Lazarus 1.9.0 and higher):

-    open and compile package LGenerics/packages/LGenerics.lpk.
-    add LGenerics package to project dependencies.

Implemented primitives:

-    stack(unit LGStack)
-    queue(unit LGQueue)
-    deque(unit LGDeque)
-    vector(unit LGVector)
-    vector of bits(unit LGVector)
 -   priority queue based on binary heap(unit LGPriorityQueue)
 -   priority queue with key update and melding based on pairing heap(unit LGPriorityQueue)
 -   sorted list(unit LGList)
 -   hashed list - array based list with the ability to fast search by key(unit LGList)
 -   hashset(unit LGHashSet)
 -   sorted set(unit LGTreeSet)
 -   hash multiset(unit LGHashMultiSet)
 -   sorted multiset(unit LGTreeMultiSet)
 -   hashmap(unit LGHashMap)
 -   sorted map(unit LGTreeMap)
 -   hash multimap(unit LGMultiMap)
 -   tree multimap(unit LGMultiMap)
 -   list miltimap(unit LGMultiMap)
 -   bijective map(unit LGBiMap)
 -   sparse 2D table(unit LGTable2D)
 -   disjoint set(unit LGHashSet)
 -   sparse labeled undirected graph(unit LGSimpleGraph)
 -   sparse labeled directed graph(unit LGSimpleDigraph)
Title: Re: Yet another generics collection
Post by: Blaazen on February 04, 2019, 09:15:25 am
Nice. Don't forget to add link to wiki: http://wiki.lazarus.freepascal.org/Components_and_Code_examples (http://wiki.lazarus.freepascal.org/Components_and_Code_examples)
Title: Re: Yet another generics collection
Post by: heejit on February 04, 2019, 10:31:17 am
If possible add into OPM  and a wiki with examples
Title: Re: Yet another generics collection
Post by: Thaddy on February 04, 2019, 10:43:56 am
@avg
It has a big issue: I assume for speed there is an over-use of {$H-} which not everybody likes, because it limits its applicability.
Compliments, with the restriction that it is nice code, but with niche application because of its reliance on short strings.
I am not even sure the many $H+ and $H- switches over the units are always correct.... or that every string  in $H- mode has the guaranteed correct size..
I would not accept that in production code.

Don't let that discourage you, but document the limitation. O:-)
Title: Re: Yet another generics collection
Post by: marcov on February 04, 2019, 10:47:58 am
Sortedlist uses single array. That is a scaling risk when you get into the 100k range.
Title: Re: Yet another generics collection
Post by: Thaddy on February 04, 2019, 10:52:33 am
Sortedlist uses single array. That is a scaling risk when you get into the 100k range.
Yes. Should be heap allocated. The range can be even earlier depending on stack. Use a pointer type.
(but again at the cost of speed)
Title: Re: Yet another generics collection
Post by: marcov on February 04, 2019, 11:12:01 am
Sortedlist uses single array. That is a scaling risk when you get into the 100k range.
Yes. Should be heap allocated. The range can be even earlier depending on stack. Use a pointer type.
(but again at the cost of speed)

A dynamic array is already heap allocated. I was referring to the slowdown ordered insertion of items into a single array (average O(n) operation).

The thread about the benchmark that PascalDragon refers had some info on it. I added lightcontainers to that benchmark, but it was post added and is not on by default. This simply does (dynamic) array of (dynamic) array.

Note also that the benchmark only are about lookup, array based ordered lists are of course slower than hashes than lookup, but usually more conservative with memory, allow in-order iteration and allow to find the items close to a certain item. Still the benchmark is quite nice.

p.s. oops, PascalDragon mentioned in a related but different thread here (https://forum.lazarus.freepascal.org/index.php/topic,44048.0/topicseen.html)
Title: Re: Yet another generics collection
Post by: avk on February 04, 2019, 11:42:07 am
Nice...
Thank you.
Sortedlist uses single array. That is a scaling risk when you get into the 100k range.
Yes of course.
@Thaddy, could you clarify your point:
It has a big issue: I assume for speed there is an over-use of {$H-} which not everybody likes, because it limits its applicability.
Title: Re: Yet another generics collection
Post by: Leledumbo on February 04, 2019, 12:24:37 pm
@Thaddy, could you clarify your point:
It has a big issue: I assume for speed there is an over-use of {$H-} which not everybody likes, because it limits its applicability.
I believe what he meant was: shortstrings are stack allocated, has much simpler structure and requires no manager, therefore it has speed advantage over ansistrings and other string types that doesn't have the 255 8-bit character limitation. This might be a good show in benchmark, but in reality, people might require more than 255 characters. The silent truncation behavior of most (or all?) of its related function doesn't help for sure.
Title: Re: Yet another generics collection
Post by: Thaddy on February 04, 2019, 01:00:19 pm
@Thaddy, could you clarify your point:
See Leledumbo's answer who beat me to it  ;D.
But there are more effects that can cause trouble along the way:
It is better to protect the string changes with $push and $pop too, because currently some versions of FPC (e.g. 3.0.4) keep the string changes in units over unit boundaries (which is a reported bug, it should adhere to the program settings if another unit does not define a string type)
That's why things like:
Code: Pascal  [Select][+][-]
  1. interface
  2. {$MODE OBJFPC}{$H+}    // <----- OK
  3. {$INLINE ON}{$WARN 6058 off : }
  4. {$MODESWITCH NESTEDPROCVARS}
  5. {$MODESWITCH ADVANCEDRECORDS}
  6.  
  7. interface
  8.  
  9. uses
  10.  
  11.   SysUtils,
  12.   LGUtils,
  13.   {%H-}LGHelpers,    /// < ---- this can cause a lot of trouble afterwards.....
  14.   LGAbstractContainer,
  15.   LGHashTable,
  16.   LGStrConst;

Can bring the user into trouble.
And once the bug is fixed it won't work outside a unit
You should:
- Set the string type on a per unit basis or not at all.
- At least restore the string type.

As it stands it is a shortcut that works by accident and not by language specification and documentation.
Title: Re: Yet another generics collection
Post by: Thaddy on February 04, 2019, 01:08:48 pm
@Avk
Oh, I see: you write {%H-} and not {$H-}...
In that case, that's a Lazarus IDE macro and not an FPC define?
That's also not a good idea in a library...
Title: Re: Yet another generics collection
Post by: avk on February 04, 2019, 01:16:42 pm
Yes, that's a Lazarus IDE directive.
Why is this not a good idea in the library?
Title: Re: Yet another generics collection
Post by: Thaddy on February 04, 2019, 02:04:21 pm
The library should be transparent.
Your library does not rely on visual code.
E.g: I do not usually use the Lazarus ide but Geany.
You won't find any Lazarus macro's in any FPC library code.
That's also the reason I misinterpreted it at first glance.
Title: Re: Yet another generics collection
Post by: marcov on February 04, 2019, 02:22:31 pm
The library should be transparent.

Your library does not rely on visual code.

E.g: I do not usually use the Lazarus ide but Geany.

So? What is the problem there? How do the lazarus macros make that impossible

Quote
You won't find any Lazarus macro's in any FPC library code.
That's also the reason I misinterpreted it at first glance.

Incorrect. See e.g. packages/src/avl_tree
Title: Re: Yet another generics collection
Post by: avk on February 04, 2019, 02:24:40 pm
@Thaddy, thank you, I have to think about it.
The fact is that FPC generates a lot of unnecessary hints among which you can not see the important.
Title: Re: Yet another generics collection
Post by: Thaddy on February 04, 2019, 05:14:21 pm
I wrote a wiki article on how to handle that properly. http://wiki.freepascal.org/Turn_warnings_and_hints_on_or_off
Maybe that helps
Title: Re: Yet another generics collection
Post by: Akira1364 on February 04, 2019, 09:04:26 pm
Cool library! Whole lot of "something wasn't inlined" hints though. Just in case you aren't aware, that is almost always caused by a function being marked inline but being called by another function with an implementation that comes later in the file than it. It just won't ever work in that case.
Title: Re: Yet another generics collection
Post by: valdir.marcos on February 05, 2019, 02:11:34 am
Collection of generic algorithms and data structures entirely written in/for FPC and Lazarus. Started as a self-education project, it now seems quite comfortable and fast. In order to use it (FPC 3.1.1 and higher and Lazarus 1.9.0 and higher):

Also the types in Generics.Collections support records without any operator overload.
One advantage of the FGL ones: they are small, so they're more suitable for embedded projects where memory size might be an issue.
And for those that are interested: here (http://www.benibela.de/fpc-map-benchmark_en.html) we have a performance comparison of various FPC containers (no, not by me).
Just curious.

If there are already official Generics implementations for Objfpc syntax since version 2.2. and Delphi compatible syntax since version 2.6.0.
http://wiki.freepascal.org/Generics

Why are there still so many alternative implementations for Generics?

Shouldn't all this effort be redirected to evolve official Generics implementation?
Title: Re: Yet another generics collection
Post by: Akira1364 on February 05, 2019, 03:40:00 am
Shouldn't all this effort be redirected to evolve official Generics implementation?

I think a more important thing to look at first would be to start actively encouraging people to use generics overall in new code, and stop pointing them at things like Contnrs as though they're still "the best you'll get." They're not. Typecasting void pointers back and forth is dumb when it can be avoided.

There's a reason nobody uses non-generic TList or anything from Contnrs when working with new Delphi versions. I don't get why FPC is so different in this regard when it has all the same functionality (better functionality in some ways) available.
Title: Re: Yet another generics collection
Post by: Blaazen on February 05, 2019, 02:48:30 pm
@ Akira1364

Something similar asked Graeme on ML a few years ago. For example, I still use TCollection and TCollectionItem for visual components because they work well and have built-in design-time editors. Otherwise I use FGL (at most TFPGObjectList)  for reasons you pointed.
One of reasons may be that CodeTools still does not fully support generics, i.e. when you hit Ctrl+Space you don't get proper choice.
Title: Re: Yet another generics collection
Post by: Akira1364 on February 05, 2019, 03:10:34 pm
For example, I still use TCollection and TCollectionItem for visual components because they work well and have built-in design-time editors.

One of reasons may be that CodeTools still does not fully support generics, i.e. when you hit Ctrl+Space you don't get proper choice.

TCollection and TCollectionItem are a bit different I'd say due to the specific "persistent" RTTI-based functionality they provide. There's definitely good reasons to use those, since no relevant generic equivalent currently exists.

For the CodeTools stuff, it's true that the support for generics still isn't perfect. I don't think I'd ever write my code specifically to workaround IDE issues, though.
Title: Re: Yet another generics collection
Post by: avk on February 06, 2019, 12:01:06 pm
Whole lot of "something wasn't inlined" hints though.
I cleaned the inlines a bit, so the compiler noise about this should be smaller.
Title: Re: Yet another generics collection
Post by: marcov on February 06, 2019, 05:25:02 pm
Why are there still so many alternative implementations for Generics?

The Delphi compatible generics library is not yet delivered in a release.
Title: Re: Yet another generics collection
Post by: avk on February 07, 2019, 08:29:55 am
The Delphi compatible generics library is not yet delivered in a release.
Just in case, LGenerics is incompatible with Delphi.
Title: Re: Yet another generics collection
Post by: avk on February 23, 2019, 11:13:33 am
recent changes in LGenerics:
 - added implementation of concurrent fine-grained hashmap(first attempt)
 - added some thread pool implementations
 - improved implementation of futures
Title: Re: Yet another generics collection
Post by: Thaddy on February 23, 2019, 11:29:09 am
I like the thread pool features. Will test.
Title: Re: Yet another generics collection
Post by: avk on February 24, 2019, 08:36:51 am
... Will test.
Thank you, it would be highly interesting to know if it works on the arm device.
Title: Re: Yet another generics collection
Post by: avk on December 22, 2019, 05:23:25 am
Hi everyone,
a separate branch "stable_0_52"(I hope) has been created for the current version of the LGenerics package and it seems to be compatible with fpc 3.2.

It has been added since the last announcement
new primitives:
 - some variants of "smart pointers"
 - dynarray with COW semantics
 - 128-bit integers
 - general rooted tree
 - red-black tree
 - some variants of the treap
 - static segment tree
 - helpers for getting an extended IEnumerable interface
   for any entity that provides an enumerator

algorithms on graphs:
 - minimum vertex cover
 - chordality testing
 - dominators in flowgraps
 - FMR planarity testing algorithm

Merry Christmas and happy coding! 
Title: Re: Yet another generics collection
Post by: julkas on December 22, 2019, 11:35:00 am
@avk Great +5.
1. Plans for random algorithms on graph (Karger, ...) ?
2. Delphi compatibility?
Add docs.

Thanks.
Title: Re: Yet another generics collection
Post by: avk on December 30, 2019, 07:30:02 am
@julkas, thank you.

Especially with regard to randomized algorithms, I have not yet thought, now there is a desire to expand the set of supported types of graphs. But if you are interested in finding the minimum cut, the library has a deterministic algorithm.
As for Delphi compatibility: if Delphi will support helper inheritance and record management operators, why not? :)

The library is still in its infancy, a lot has to be changed, so as long as I don't see the point in writing documentation, it will have to be rewritten. So far, I've been trying to comment on classes and methods in detail.
Title: Re: Yet another generics collection
Post by: avk on January 05, 2020, 07:37:50 am
Happy 2020!

I added a translation of Orson Peters' PDQSort algorithm.
Title: Re: Yet another generics collection
Post by: avk on January 31, 2020, 12:13:18 pm
Slightly improved sorting algorithms performance.
Below are results of some comparison benchmarks, first plot is about pascal sortings:
A negative value indicates that the algorithm failed the test(exhibits quadratic behavior).
win7-64bit, fpc-3.3.1-r44056, Delphi 10.3 CE;

The second one shows comparison with c++ sortings on a virtual Linux machine(gcc 7.3.0).
Title: Re: Yet another generics collection
Post by: julkas on January 31, 2020, 06:15:34 pm
@avk your attachments are invisible for guests.
Title: Re: Yet another generics collection
Post by: Thaddy on January 31, 2020, 06:29:51 pm
@avk your attachments are invisible for guests.
That is normal.
Title: Re: Yet another generics collection
Post by: avk on February 01, 2020, 07:01:36 am
@avk your attachments are invisible for guests.
Doesn’t it depend on the forum settings?
Title: Re: Yet another generics collection
Post by: julkas on February 01, 2020, 03:43:47 pm
Slightly improved sorting algorithms performance.
Below are results of some comparison benchmarks, first plot is about pascal sortings:
  • Delphi denotes Delphi.Generics.Collections.TList<Integer>.Sort
  • Fgl  - fgl.TFpgList<Integer>.Sort
  • GCol - rtl-generics.Generics.Collections.TList<Integer>.Sort
  • Fcl  - fcl-stl.TOrderedArrayUtils.Sort(TVector<Integer>)
  • Lg   - LGenerics.TGVectorHelper.Sort(TGVector<Integer>)
A negative value indicates that the algorithm failed the test(exhibits quadratic behavior).
win7-64bit, fpc-3.3.1-r44056, Delphi 10.3 CE;

The second one shows comparison with c++ sortings on a virtual Linux machine(gcc 7.3.0).
Can you give more info about your benchmark env (VM, CPU, RAM, optimization switches, C++ source code)?
What about 10**7, 10**8?
Title: Re: Yet another generics collection
Post by: Thaddy on February 01, 2020, 04:22:55 pm
Doesn’t it depend on the forum settings?
Yes. Being able to view (or upload) is dependent on forum membership.
Title: Re: Yet another generics collection
Post by: Thaddy on February 01, 2020, 04:25:40 pm
What about 10**7, 10**8?
What about 10**555 ?
That's a silly question.  I do not think C++ can even handle that with standard libraries....We are talking quadratic expansion here.
Given the code and sufficient memory and time 10**7 should be no problem.
Title: Re: Yet another generics collection
Post by: avk on February 01, 2020, 05:28:59 pm
Can you give more info about your benchmark env (VM, CPU, RAM, optimization switches, C++ source code)?
Oh sure. This is Ubuntu MATE 18.04 with 2 GB RAM on VirtualBox 5.2.26. The host system and processor are listed above.
Attachment contains sources and a small Readme. If you want, you can add 10^7 and more there. 
Title: Re: Yet another generics collection
Post by: avk on February 16, 2020, 12:38:03 pm
The performance of the containers seems to have improved slightly.
Below are some results of "quick and dirty" comparison benchmark for some hashmaps(string keys) from Pascal' hashmap zoo.
Participants(with default settings):
The benchmark was compiled with FPC 3.3.1 r44056(x86_64-win64) and runs on win7.
Title: Re: Yet another generics collection
Post by: avk on May 05, 2020, 04:17:10 pm
Added support for sets of arbitrary size (well, at least up to High(Cardinal) div 33).
Quick and dirty comparison of performance with the built-in set looks like this:
Code: Text  [Select][+][-]
  1. built-in set - size:              32
  2. generic set  - size:              32
  3. built-in set - include:           670 ms
  4. generic set  - include:           410 ms
  5. built-in set - contains:          520 ms
  6. generic set  - contains:          200 ms
  7. built-in set - intersection:      300 ms
  8. generic set  - intersection:      20 ms
  9. built-in set - iteration(sparse): 720 ms
  10. generic set  - iteration(sparse): 130 ms
  11. built-in set - iteration(dense):  670 ms
  12. generic set  - iteration(dense):  660 ms  
  13.  
Title: Re: Yet another generics collection
Post by: Thaddy on May 05, 2020, 07:58:41 pm
Nice! I abandon my efforts... for the huge sets. I am using your library more and more.
Compliments! This is not "Yet another" but also firmly founded in theory, which I especcially like. And you have a really clean coding style, which I also like very much. Therefor the code is quite self-documenting.
Title: Re: Yet another generics collection
Post by: fcu on May 06, 2020, 12:13:53 am
3mb of code wow !! , my projects never exceed 100kb   
i liked this library very much , also fpc generic.collection becomes microscopic compared with this giant and great library
really thanks for making this public
keep up the good work   
Title: Re: Yet another generics collection
Post by: sash on August 10, 2020, 01:43:18 pm
Hello.

Is it possible to use it without installing as a package?
Because otherwise, it's hard to maintain in automated builds.
Title: Re: Yet another generics collection
Post by: avk on August 10, 2020, 02:48:10 pm
There shouldn't seem to be any problems, but to be honest, I haven't tried.
Title: Re: Yet another generics collection
Post by: sash on August 10, 2020, 03:48:38 pm
There shouldn't seem to be any problems, but to be honest, I haven't tried.

Thanks for reply.

I figured out, it works, but only if I add
  (in addition to LGenerics/lgenerics/ in Other unit files(-Fu))
  LGenerics/lgenerics/include to Include files(-Fi),
otherwise compiler cannot find {$I EnumsH.inc}.

I'd suggest improvement in form of replacing such includes as {$i include/xyz.inc}, so -Fi LGenerics/lgenerics/include will not be necessary (as actually being a part of *.pas units).

Another one, how do you construct graphs, can I use builtin hashing helpers for this?
Code: Pascal  [Select][+][-]
  1. uses
  2.    LGSimpleGraph, LGHelpers;
  3. type
  4.   TMyGraph = specialize TGSimpleGraph<TMyVertexClass, TMyEdgeClass, TWhat?>;
  5.  

Thanks again.
Title: Re: Yet another generics collection
Post by: avk on August 10, 2020, 04:48:06 pm
Thanks for the suggestion.

To use the built-in helper for a class, it is enough to declare the graph as
Code: Pascal  [Select][+][-]
  1. uses
  2.    LGSimpleGraph, LGHelpers;
  3. type
  4.   TMyGraph = specialize TGSimpleGraph<TMyVertexClass, TMyEdgeClass, TMyVertexClass>;
  5.  

Note that the built-in helper uses the TObject.Equals and TObject.GetHashCode methods under the hood.
Title: Re: Yet another generics collection
Post by: Alextp on August 10, 2020, 05:13:06 pm
Added wiki page
https://wiki.freepascal.org/LGenerics
Title: Re: Yet another generics collection
Post by: avk on August 10, 2020, 07:43:36 pm
Thank you very much, that's very kind.
Title: Re: Yet another generics collection
Post by: sash on August 24, 2020, 09:05:45 pm
Again about graphs.
Is there a suggested way of (un)serialization?

Title: Re: Yet another generics collection
Post by: avk on August 25, 2020, 03:33:27 am
Only the simplest SaveToStream/LoadFromStream.
Title: Re: Yet another generics collection
Post by: mr-highball on August 25, 2020, 04:15:03 am
Saw your library back when it was first posted and have to say, you've got some good stuff in here. Just wanted to say it's been starred and to keep up the good work 👍👍
Title: Re: Yet another generics collection
Post by: avk on August 25, 2020, 11:50:54 am
Thank you very much.
Title: Re: Yet another generics collection
Post by: sash on August 26, 2020, 02:41:11 pm
Only the simplest SaveToStream/LoadFromStream.

Well, for Vetices there are Items, but I can't figure out how can I exactly iterate through Edges as linear list.
Can you provide an example?
Title: Re: Yet another generics collection
Post by: avk on August 26, 2020, 04:38:03 pm
It seems I misunderstood your question?

There is the Edges method, which returns enumerable, which enumerates all edges of the graph.
On an undirected graph each edge will meet twice, which may be inconvenient.
Therefore the undirected graph also has the DistinctEdges method.

This code
Code: Pascal  [Select][+][-]
  1. program print_edges;
  2. {$mode delphi}
  3. uses
  4.   SysUtils, LGUtils, LGSimpleGraph;
  5.  
  6. type
  7.   TRef = TGAutoRef<TStrChart>;
  8.  
  9. var
  10.   Ref: TRef;
  11.   g: TStrChart;
  12.   s: string;
  13.   e: TStrChart.TEdge;
  14. begin
  15.   g := Ref;
  16.   g.AddEdge('one', 'two');
  17.   g.AddEdge('one', 'three');
  18.   g.AddEdge('two', 'four');
  19.   g.AddEdge('two', 'five');
  20.   g.AddEdge('three', 'six');
  21.   g.AddEdge('three', 'seven');
  22.   g.AddEdge('six', 'eight');
  23.   g.AddEdge('seven', 'eight');
  24.   g.AddEdge('eight', 'one');
  25. { or
  26.   g.AddEdges(
  27.     ['one', 'two', 'one', 'three', 'two', 'four', 'two', 'five', 'three', 'six',
  28.      'three', 'seven', 'six', 'eight', 'seven', 'eight', 'eight', 'one']); }
  29.  
  30.   WriteLn('Vertices:');
  31.   for s in g.Vertices do
  32.     WriteLn(s);
  33.  
  34.   WriteLn;
  35.  
  36.   WriteLn('Edges:');
  37.   for e in g.DistinctEdges do
  38.     WriteLn(g[e.Source], ' -- ', g[e.Destination]);
  39. end.
  40.  
will print
Code: Text  [Select][+][-]
  1. Vertices:
  2. one
  3. two
  4. three
  5. four
  6. five
  7. six
  8. seven
  9. eight
  10.  
  11. Edges:
  12. one -- two
  13. one -- three
  14. one -- eight
  15. two -- four
  16. two -- five
  17. three -- six
  18. three -- seven
  19. six -- eight
  20. seven -- eight
  21.  
Title: Re: Yet another generics collection
Post by: sash on August 26, 2020, 06:31:53 pm
Yes, my case is undirected graphs (with my own TVertex and TEdge classes), and I need to save/load whole dataset to text/xml (both structure and objects).
Also I need to visualize it in form of "circles connected by lines", so I guess DistinctEdges is what I need.

Currently, I'm using another graph library (C-code linked to my Pascal project), but found your one, and evaluating it. It's very complex, not yet get used to it.

Also, does DistinctEdges return cached value, or does it recalculate list on the fly (from adjacency matrix?)?
Title: Re: Yet another generics collection
Post by: avk on August 26, 2020, 07:42:46 pm
Also, does DistinctEdges return cached value, or does it recalculate list on the fly (from adjacency matrix?)?
The iterator simply traverses the vertex adjacency lists.

BTW, there is a way(rather primitive) to draw a graph.
This code will save the graph from the previous example in Graphviz' dot format:
Code: Pascal  [Select][+][-]
  1. program save2dot;
  2. {$mode delphi}
  3. uses
  4.   SysUtils, LGUtils, LGSimpleGraph;
  5. var
  6.   Ref: TGAutoRef<TStrChart>;
  7.   g: TStrChart;
  8.   DotWriter: TGAutoRef<TStrChartDotWriter>;
  9. begin
  10.   g := Ref;
  11.   g.Title := 'Chart';
  12.   g.AddEdges(['one', 'two', 'one', 'three', 'two', 'four', 'two', 'five', 'three', 'six',
  13.               'three', 'seven', 'six', 'eight', 'seven', 'eight', 'eight', 'one']);
  14.  
  15.   with DotWriter.Instance do
  16.     begin
  17.       ShowTitle := True;
  18.       SizeX := 4;
  19.       SizeY := 4;
  20.       SaveToFile(g, 'Chart.dot')
  21.     end;
  22. end.
  23.  
If you feed the resulting file to Graphviz, you will get a picture similar to the one in the attachment.
Title: Re: Yet another generics collection
Post by: sash on August 26, 2020, 11:34:17 pm
Well, I know about Graphviz, but I must use canvas to draw and edit graph layout...

And what about memory management?
Should I take care about freeing my custom vertex and edge class instances?
Title: Re: Yet another generics collection
Post by: avk on August 27, 2020, 06:55:18 am
If instances of vertices and edges are not stored anywhere except the graph, then certainly yes.
Provided that you do not remove the vertices and edges of the graph while manipulating with it, this can be done in the destructor. Otherwise, you also need to override the protected methods DoRemoveVertex and DoRemoveEdge
Title: Re: Yet another generics collection
Post by: sash 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() ?
Title: Re: Yet another generics collection
Post by: avk 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.  
Title: Re: Yet another generics collection
Post by: avk 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.  
Title: Re: Yet another generics collection
Post by: avk on August 28, 2020, 04:41:32 pm
@sash, eventually I added TGSimpleObjGraph. It would be interesting to know your opinion.
Title: Re: Yet another generics collection
Post by: sash 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;
?

Title: Re: Yet another generics collection
Post by: avk 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).
Title: Re: Yet another generics collection
Post by: sash 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?
Title: Re: Yet another generics collection
Post by: avk on August 30, 2020, 05:53:38 pm
Yeah, exactly.
Title: Re: Yet another generics collection
Post by: avk on October 19, 2020, 10:45:33 am
Added a radix sort algorithm, so I ran the sorting benchmark again.
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.
Title: Re: Yet another generics collection
Post by: avk on December 30, 2020, 06:57:56 am
Added implementation of the JSON parser/generator.
It seems it passes all tests from JSONTestSuite (https://github.com/nst/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!
Title: Re: Yet another generics collection
Post by: lainz 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.
Title: Re: Yet another generics collection
Post by: avk 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.  
Title: Re: Yet another generics collection
Post by: lainz on January 05, 2021, 01:14:01 pm
Thanks!  :)
Title: Re: Yet another generics collection
Post by: avk on January 05, 2021, 01:56:34 pm
You are welcome.
Title: Re: Yet another generics collection
Post by: lainz 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!
Title: Re: Yet another generics collection
Post by: avk on January 05, 2021, 05:25:13 pm
It's a good question anyway. I do my best to avoid adding nodes directly, as this is error-prone. However, double parsing isn't a very attractive solution either.
I just hastily added a new ArrayAppend method, maybe that's what you need?
Title: Re: Yet another generics collection
Post by: lainz on January 05, 2021, 09:12:42 pm
Yes that works.

Anyways I get a slower time this time with the change. But I'm not measuring it well, so I can't say, I'm measuring a whole process that depends on internet, so speed can vary and is not only by the json library, but the server speed, internet speed and other things.
Title: Re: Yet another generics collection
Post by: avk on January 18, 2021, 03:10:59 pm
Added pull-style JSON stream reader.

It provides, at the user's choice

As for performance, query
Code: Pascal  [Select][+][-]
  1.   Reader.FindPath('/features/100001')
  2.  
on this (https://github.com/zemirco/sf-city-lots-json/blob/master/citylots.json) JSON(~190MB) takes about 0.7 s. on my machine.
Title: Re: Yet another generics collection
Post by: avk on February 22, 2021, 06:59:47 am
Added implementation of two string matching algorithms (unit lgStrHelpers), both are inheritors of the Boyer-Moore algorithm with minor improvements or simplifications.
The TBmSearch entity implements a Boyer-Moore incarnation called Fast-Search, and TBmhrSearch implements the Boyer-Moore-Horspool-Raita algorithm(sometimes just Raita). TBmSearchCI is a case-insensitive version of TBmSearch.

A simple comparative benchmark on various inputs; BuildinBM denotes FindMatchesBoyerMooreCaseSensitive from StrUtils.

Random string(200000000 bytes) over a five-character alphabet, search for 10 patterns(running time in ms, lower is better).
Code: Text  [Select][+][-]
  1.  pattern len       TBmSearch    TBmhrSearch  BuildinBM
  2.      5               3157          3500        4017
  3.     10               2235          2487        2814
  4.     20               2078          2687        2627
  5.     50               1455          2078        1812
  6.    100               1437          2502        1767
  7.    200               1375          2422        1749
  8.  

Natural language text(English, "The Forsyte Saga", 2079763 bytes), search for 1000 patterns(running time in ms, lower is better).
Code: Text  [Select][+][-]
  1.  pattern len       TBmSearch    TBmhrSearch  BuildinBM
  2.      5               1969          2266        2799
  3.     10               1125          1297        1593
  4.     20                704           811         984
  5.     50                470           516         609
  6.    100                376           405         468
  7.    200                312           327         374
  8.  

Search for a single pattern in a list(200000 items) of moderate-length strings(5000-15000 bytes)(running time in ms, lower is better).
Code: Text  [Select][+][-]
  1.  pattern len       TBmSearch    TBmhrSearch  BuildinBM
  2.      5               2653          3311        3343
  3.     10               1016          1171        1530
  4.     20                842           875        1169
  5.     50                358           375         558
  6.    100                374           419         672
  7.    200                296           314         640
  8.  

Case insensitive search, Pascal sources(83996301 bytes), search for 25 patterns, BuildinBM_CI here denotes FindMatchesBoyerMooreCaseInSensitive(running time in ms, lower is better).
Code: Text  [Select][+][-]
  1.  pattern len       TBmSearchCI    BuildinBM_CI
  2.      5               2565            3250
  3.     10               1488            1744
  4.     20                889            1042
  5.     50                618             709
  6.    100                444             517
  7.    200                390             442
  8.  
Title: Re: Yet another generics collection
Post by: 440bx on February 22, 2021, 07:36:35 am
The TBmSearch entity implements a Boyer-Moore incarnation called Fast-Search, and TBmhrSearch implements the Boyer-Moore-Horspool-Raita algorithm(sometimes just Raita). TBmSearchCI is a case-insensitive version of TBmSearch.
Nicely done!.
Title: Re: Yet another generics collection
Post by: avk on February 22, 2021, 07:52:21 am
Thank you.
Title: Re: Yet another generics collection
Post by: OkobaPatino on February 22, 2021, 02:05:57 pm
Well done avk.
TinyPortal © 2005-2018