Hi,

I am in need of a component/clas that can hold a 2 dimensional "table" of strings.
The dimensions are unknown at designtime: I read the data from a HTML table. The HTML reader provides events that give me the data of each cell, and that tell me whenever a row is started or closed.

The class should be able to:
- access individual "cellls" (read/write)
- add or insert a row (with an without data (TStrings and Array of String must be supprted as the datatype)). Note: adding a row must be possible when the dimensions of the table are yet unknown.
- upon adding a row, it should be able to extend the dimensions of the table
- the strings itself may contain LineEndings

Not needed right now, but nice to have:
- add or insert a column (with an without data)
- upon adding a column, it should be able to extend the dimensions of the table
- delete a row or column

I have no need for saving the table to disk in any way. The program that uses this class should not need external libraries, since I cannot install those on the target computer I need my program on.

I botched up some class that can do this (good enough for my purposes, but it's not nice code), but I was wondering if there already is some component that is more suitable (and well tested) for this. Using some sort of in memory dataset comes to mind, but I never use databases in my programs at all, so I'm a complete novice on that topic.

Suggestions are welcome.

Bart

fpspreadsheet? It even has a html reader, but might be an overkill though. Internally it uses a TAVLTree for storing the cells. This tree is extremely fast. Maybe you can build your class around it.

Or the TVirtualGrid from grids.pas which is used internally by TCustomGrid and its descendants?

why not use the TstringGrid component?

2016-12-29 19:02 GMT+01:00 Werner Pamler via Lazarus <

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.lazarus-ide.org/pipermail/lazarus/attachments/20170102/560d925f/attachment.html>

guy barbier wrote

why not use the TstringGrid component?

Because I do not want it to depend on LCL (which I forgot to mention).

Bart

I am in need of a component/clas that can hold a 2 dimensional "table" of strings.

It has taken me a ridiculously long time to discover bufdataset, but right now I'm re-writing whole chunks of code to use these. Advantage for me: Filtering/Locate/Sort. For debug purposes, if you want to see the contents of the array, just plonk a DBGrid and point the bufdataset to that.

Our wiki overcomplicates the control - it probably assumes you already know the basics.

: Good simple start point code...
http://forum.lazarus-ide.org/index.php?topic=31698.0

: Advanced topics, but only if needed...
http://wiki.freepascal.org/How_to_write_in-memory_database_applications_in_Lazarus/FPC

Cheers

Mike
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.lazarus-ide.org/pipermail/lazarus/attachments/20170103/e84737c5/attachment.html>

Bart wrote

I am in need of a component/clas that can hold a 2 dimensional "table" of strings.

Go back to the basics.... Simply use an array. ;-)

Regards,
Graeme

Graeme Geldenhuys wrote

Simply use an array. ;-)

A two dimensional dynamic array.

If he wants "add" and "delete" etc functions, he can easily embed same in a class, plus using a two dimensional array default property for comfort.

-Michael

Michael Schnell wrote

A two dimensional dynamic array. If he wants "add" and "delete" etc functions, he can easily embed same in a class, plus using a two dimensional array default property for comfort.

Yes, that's what I ended up with.
I constructed a TStringTable class that does all I need (and more):
- insert, add, delete rows/cols
- autogrow colcount (with insertrow)
- exchange rows/cols
- get/set rows/cols
- property Cells[ACol, ARow]: string (read/write)

It can be found here:
http://svn.code.sf.net/p/flyingsheep/code/trunk/MijnLib/stringtable.pp

Implementation can probably be faster (I use dumb for loops to move things around, where maybe I could have used move(), but failed and gave up).

It does not scale very well (due to numerous setlength() calls), but filling a 1000x1000 TStringTable just cost me 76 ms. A 5000x5000 table however cost me 1248 ms.

B.t.w. for testing purposes I tried to set up a 10000x10000 array of array of string, but the program died on me without a sign of a single exception.

Bart

Just implemented sorting.

Bart

Bart wrote

Just implemented sorting.

Nice !
(Even if I don't see a straight forward understanding of two dimensional sorting).

BTW.:

Looking at the code I could imagine that auto-growing when using the Cell property to write an element might be appropriate.

Read/Write form/to a file might be sensible. Here AFAIK, the fpc's TStringList does not yet feature setting the encoding, which Delphi does.

-Michael

Hi Bart,

just having a look at the declaration, haven't skimmed through code yet,

do you also plan to add a TStringGrid-like interface for cols and rows

http://lazarus-ccr.sourceforge.net/docs/lcl/grids/tcustomstringgrid.cols.html ?

(i understand that not all TStrings does, will make sense in table row/col context... like we wouldn't want to let StringTable.Rows[rowindex].Strings[colindex].Delete to delete the entire column, or shift the data to close the gap...)

I wonder why nobody thought of this kind of (non-visual) TStringGrid before ? :)

I guess the TStringGrid has become very visually-centered and it's not possible to split the visual from non-visual there any more without serious work ;)

Kind Regards

el es

Lukasz Sokol wrote

just having a look at the declaration, haven't skimmed through code yet, do you also plan to add a TStringGrid-like interface for cols and rows

No, I wanted to keep it as simple as possible.

Bart

Michael Schnell wrote

Looking at the code I could imagine that auto-growing when using the Cell property to write an element might be appropriate.

I thought bout that, but rejected it.

Read/Write form/to a file might be sensible. Here AFAIK, the fpc's TStringList does not yet feature setting the encoding, which Delphi does.

And then we get the problem of the format of the file. We had similar discussion about TStringGrid (which supports .csv files), I think with BigChimp (Reinier).
Any choice you make here is arbitrary.

Options:
- class helper
- a system like TBufDataSet uses: implement SaveToStream and ReadFromStream that require a reader/write class
- make a new unit that implements reader/writer procedures (StringTableExportToCSV(const Fn: String; ST: TStringTable) etc.

My current usecase does not require use it for string the contenst of a HTML table (copied from clipboard) and extract data from that.

(Starts ranting)

All this because the manufacturor of the pogram refuses to implement a simple function: give me a list of current medication in a simple plain text format.

While the program (a web application) can show on the screen stuf like:

metoprolol mga 100 mg 1 maal daags 1 tablet (oraal) clopidogrel 75 mg 1 maal daags 1 tablet (oraal)

It is impossible to copy and paste this in any other program without much editing.
E.gif you copy/paste 10 lines like this in MS Word (or Notepad for that matter), you end up with a document of 80 pages (!!!!!), mostly whitespace (LineEndings, space, non-breaking-space) and the text gets cluttered with opening and closing brackets and bullets.

The web program also can show this information as a HTML table, but again copy/pasting this ruins your Word document.

So that's where my program comes in.
It can deal with the table and with the other (plain text) format, and it santizes the input.
It will change
"metoprolol mga 100 mg 1 maal daags 1 tablet (oraal)" into
"metoprolol mga 100 mg 1 dd 1"

It will also deal with the fact that MS Word has decided to treat LineEndings as New Paragraph.

And all this is necessary so that I can copy/paste current medication into letter of referral or letter of discharge (instead of manually typing it, with the risk of potentially devestating typo's.. And each and every update of the webprogram they change something about the layout or separators they use, and I have to update my program again.

Mind you FF is able to copy the table in plaintext format using Tabs as a separator, which would be easy, but IE (which is the only browser available to me on the system) cannot do so.

Obviously my boss does not care, he does not have to use this program, only the doctors (12 of them) have.
And needless to say that the ICT department has forbidden me to use this program, because "it is not a commercial progra, and therefore there is no offical support for it, and unsupported programs cannot be installed on our system".
(Note: the ICT guys all use Chrome as their browser, because "IE sucks") Fortunately my program is standalone (try that with VB or VC), so I just put it somewhere on a share, and so far they have not noticed.

Bart

OK I understand, you don't want to depend on TStrings ?

Which actually, gives me a bit of an idea...

-L.

Lukasz Sokol wrote

OK I understand, you don't want to depend on TStrings ?

That makes no sense to me, some methods take a TStrings as parameter... Maybe you meant TStringGrid instead?

I did not want my code to depend on LCL.
(It does depend on LazUtils though, but that can be stripped out easily for anyone who cares).

Bart

If you get into some tricky web browser issues you can also visit the DOM with internet explorer embedded browser control.. (or firefox embedded or chromium embedded). Then you can copy whatever html table you want into whatever format you want... just visit the table via the dom, or visit any of the html web page components and deal with it.

But if fast html parser does the job... it's simpler.

Bart wrote

That makes no sense to me,

Instead of a two dimensional array of strings you could have use a single dimensional array of StringLists (a less symmetrical way, of course).

-Michael

Yeah basically access every row or col as a TStrings type (for easy .Delimited or .CommaText yield)

-L.

Michael Schnell wrote

Instead of a two dimensional array of strings you could have use a single dimensional array of StringLists (a less symmetrical way, of course).

That was my frist try (see:
http://svn.code.sf.net/p/flyingsheep/code/trunk/FarmedTools/tableemulator.pp), but then you run into troubles when a string contains a LineEnding...

Bart

Michael Schnell wrote

> Just implemented sorting. Nice ! (Even if I don't see a straight forward understanding of two dimensional sorting).

Imagine you wat the rows that have the largest values (this depends on the context) at the top, or likewise columns at the left?

Sorting individual rows/cols o.t.o.h. makes no sense to me.

Anyhow: implementing sorting was just an excercise to see if it would work.

Bart

Isn't there a way to change LineEnding to something like a dummy that never gets read...

Or maybe I am confusing Delimiter for CSV values

Should line ending be modifiable to anything someone wants?

Lars wrote

Isn't there a way to change LineEnding to something like a dummy that never gets read...

Yes, just see the code I mentioned.
I did not like it.
I even contemplated string each string base64 encoded (guaranteed to have no line-endings) inside the TstringList.

I think my current implementation is cleaner.
As long as you do not plan on having a table > 1000x1000 it behaves quite nicely IMO.

Bart

Bart wrote

I think my current implementation is cleaner. As long as you do not plan on having a table > 1000x1000 it behaves quite nicely IMO.

Right now i think, there is a shortage of standard non-visual classes that can handle first 2 degrees of separation of data into sections in a file - by section delimiter or by line-endings; Tables in other words.

The only component that can handle entire file of comma- or otherwise- delimited data is a TStringGrid. But it is visual, and quite a lot of overkill for some cases - then everybody who reads a comma-separated (or even space-separated variable-length (variable decimal places?) sub-strings ends up not using a TStringList, but inventing iterating over sub-strings with a temporary TStringList every time... (who says you never want to use LCL Classes unit in a console program, really ?)

While if the TStringTable was to expose every row (or col) in the table as another TStringList, as requested, interfacing with that (even loading directly into and from a TStringGrid when needed for display) would be so much easier.

For such usage, it is rather assumed that NO substring can contain EOL of any kind, EOL is assumed to be meaning end of a string here. Not unlike TStringList assuming EOL to mean end of a string.

YMMV but I hope some of this makes sense ;)

Bart

-L.

Bart wrote

filling a 1000x1000 TStringTable just cost me 76 ms. A 5000x5000 table however cost me 1248 ms.

Amazing. I tried the AVLTree used by fpspreadsheet and it needs 0.37 sec for 1000x1000 and 10.3 sec for 5000x5000.

Seems as expected:
Using 25 million entries instead of 1 million entries makes a factor of 25 for the needed time.

Lukasz Sokol wrote

For such usage, it is rather assumed that NO substring can contain EOL of any kind,

For the intende purpose of TStringTable, this is certainly NOT the case.

EOL is assumed to be meaning end of a string here. Not unlike TStringList assuming EOL to mean end of a string.

That makes no sense to

Werner Pamler wrote

Amazing. I tried the AVLTree used by fpspreadsheet and it needs 0.37 sec for 1000x1000 and 10.3 sec for 5000x5000.

My tests were all "in memory", no disk access whatsoever.

Bart

Mine as well.

I would be tempted to implement such a table in fpspreadsheet, but its problem is that it occupies memory for empty cells while the AVLTree stores only existing cells (at the expense of the cell record which contains row and column indexes).

Werner Pamler wrote

I would be tempted to implement such a table in fpspreadsheet, but its problem is that it occupies memory for empty cells

An empty cell occupies only a nil pointer.

Mind you that when you do not know the dimensions of the table AND you have to increase ColCount several times whilst filling the table, then I suspect things will slow down significantly, because each increase of ColCount requires RowCount times a SetLength on each row (which means re-allocating the entire row).

I think dealing with spreadsheets needs a component that scales well. I got an EOutOfMemory on a 10000x5000 table (for which I also had all strings in memory a second time though).

Bart

An empty cell occupies only a nil pointer.

It may sum up, though, if the table is large and sparsely populated.

Ah - that's the explanation: you did your test with a predimensioned table? Mine started with an empty table, and with every new cell the tree sorts the new cell to the correct location and rebalances itself. It would be interesting to compare with your table in the same way.

I think dealing with spreadsheets needs a component that scales well. I got an EOutOfMemory on a 10000x5000 table (for which I also had all strings in memory a second time though).

I don't think so, usually spreadsheets are much smaller (or people are abusing spreadsheets as a poor-man's database). Max column count of LibreOffice, BTW, is 1024.

Werner Pamler wrote

Ah - that's the explanation: you did your test with a predimensioned table? Mine started with an empty table, and with every new cell the tree sorts the new cell to the correct location and rebalances itself. It would be interesting to compare with your table in the same way.

I fill my table per row, that is I collect 1 row of data at the time (adding it to a tmp variable) then add the row to the table. Adding cell by cell would be even more inefficient (at least in the beginning), but at some point you won't need to increase rowcount anymore. But the GetCell/SetCell is not the most efficient way of adding data.

My test scenario is:

I create an array of array of string (Z) and fill that with strings in the form of 'ColX:RowY'.
I then iterate the Z and do AddRow(Z[i]), this adds a row and copies the data from Z[i], using a simple for loop (maybe can be made more efficient).
So there are only 2 operations, copying is probably faster then inserting into a Tree.

The good point about this is that creating a row also initializes it's values, since a row is an array of string and SetLength sets all values to nil/0.

Note: the creating and populating of Z takes up the most time (up to 10 seconds).

Bart

I understand that :) and I respect that.

Sorry should have reiterated EOL is an end of a SUBstring... :)

Bart

-L.

I know you guys are talking about non-gui structures, but just for comparison I included fpGUI's StringGrid results, which uses a custom internal storage mechanism.

Creating (setting column count and row count) and populating (every cell has a value written to it) a 5,000 x 5,000 grid takes 1.815 seconds on my system.

The same test with a 1,000 x 1,000 takes 0.118 seconds.

The same test with 10,000 x 5,000 takes 4.514 seconds.

Not to shabby for a GUI component. ;-)

Now if any developers implements an application that actually displays that amount of data to the end-user without filtering, I'll be first in line to knock them over the head. :-P

Regards,
Graeme

Graeme Geldenhuys wrote

Now if any developers implements an application that actually displays that amount of data to the end-user without filtering, I'll be first in line to knock them over the head. :-P

I think this is easy with VirtualTreeView as it only display what fits on the window. Of course, you will not see all the millions of entries at the same time but putting it into a VirtualTree will allow you to scroll through them without delay. I use a VirtualTree for millions of entries and it works fine.

You only need to make sure that displaying one entry does not require to go through all other entries (i.e. by calculating something that involves all entries).

Jürgen Hestermann wrote

Of course, you will not see all the millions of entries at the same time but putting it into a VirtualTree will allow you to scroll through them without delay.

fpGUI's StringGrid doesn't have any delay on scrolling or jumping to the extreme limits of the data. The all appear instantly.

My point was that NO application should display so much data to a end-user, as it is simply too much. A end-user always knows what they are looking for, more or less, (otherwise they wouldn't be in that screen). So present them with some filtering options first. Basic UI design principles... but this is another topic to discuss elsewhere.

Regards,
Graeme

If the author if the AVLTree is reading this: Is there a way to add a group of nodes to the tree which are already ordered such that they will be adjacent? The normal "Add" method assumes that the node can be anywhere, and the tree has to find the correct location for the new node. I guess that such a "batch mode" could speed up loading the AVLTree.

Werner Pamler wrote

I would be tempted to implement such a table in fpspreadsheet, but its problem is that it occupies memory for empty cells while the AVLTree stores only existing cells (at the expense of the cell record which contains row and column indexes).

What about a two dimensional array of integers pointing to a one dimensional array of strings, and doing some garbage collection cells are set to empty strings ? (Maybe even identical strings can be managed...)

-Michael

Michael Schnell wrote

On 09.01.2017 23:28, Werner Pamler via Lazarus wrote: What about a two dimensional array of integers pointing to a one dimensional array of strings, and doing some garbage collection cells are set to empty strings ? (Maybe even identical strings can be managed...)

What's the difference between a 2 dimensional array of intergers and a 2 dimensional array of pointers (assuming that integers use the same space as a pointers)? Even worse, you would need additional dereferencing and also an additional integer for each string.

Graeme Geldenhuys wrote

My point was that NO application should display so much data to a end-user, as it is simply too much.

I disagree.
I have written an (XTree-like) file manager that can log all directories and files into memory. Then there is a function to display all of them in a flat list. This could be up to millions if you log a large server share. But you can then display a sorted flat list where you find i.e. the newest (or largest) files on top and the oldest (or smallest) files at the end. Of course, you will seldom step through all of them from top to bottom. But you may jump to top (or bottom) and scroll a bit up or down. Or you can jump to a certain entry (by name search or something else) and then scroll around this entry.
I can even permanently tag some of these so found entries at top or bottom or in between and then reduce the list to just these tagged files with one keystroke. I can also apply some more sophisticated functions like attribute change, delete, rename, etc. where I would not like to be resticted on the number of files in any way. IMO these are very common use cases and should be made available to the user.

I hate all these limited (mostly web) applications that split such large lists into pages where I have to choose a new page first just to move down a bit. A rediculous restriction.

A end-user always knows what they are looking for, more or less, (otherwise they wouldn't be in that screen).

I disagree again!
In most cases I (and I think most users) only have a vague imagination of what I am looking for. I first need an overview to make further decisions (for example about a filter).

So present them with some filtering options first. Basic UI design principles... but this is another topic to discuss elsewhere.

Filtering: Yes. But it's not always the first step! Very often I first need an overview to decide which filters I want to use. To stay with my file manager example:
I can set a filter to show all files with the current date (today). But then I will miss all files that have a date in the future (from which very many exists on many machines).
When I have an overall list sorted by date I will see them immeditaly on top. Also, when files are misspelled (or not spelled the way you expect them) then they may strike you when shown in an overall list but not when you already filtered by the text you expected.

Werner Pamler wrote

If the author if the AVLTree is reading this: Is there a way to add a group of nodes to the tree which are already ordered such that they will be adjacent?

I think that may not be possible. Your data may be ordered already, but that does not guerantee that there is not already data inside the tree that must be ordered "inside" the group you add?

Bart

Jürgen Hestermann wrote

I can also apply some more sophisticated functions like attribute change, delete, rename, etc. where I would not like to be resticted on the number of files in any way.

You don't need to see those items to apply those attributes. Specify some file criteria, specify the attribute changes and apply. The result can be a count of affected files. And if your application is well designed, you can undo that action too.

I hate all these limited (mostly web) applications that split such large lists into pages where I have to choose a new page first just to move down a bit. A rediculous restriction.

Indeed, and that is not what I was suggesting.

"vague" means you more or less know what you are looking for. My point exactly.

NO end-user simply goes into an application screen and randomly browses 50 million data records (which will take years scanning visually), and then only comes up with an idea of what they want to do with that information. Instead they will go into a screen with the intend to find a subset of data - say all electricity suppliers for a region in a town. If they didn't have such an intent (no matter how big or small), they would not be using the application or be in that screen to start with.

Filtering: Yes. But it's not always the first step!

So pulling in 50+ million records into a data grid over a internet connection (or worse, a dial-up connection) simply for the sake of it, then only filtering down the data.... all seems very inefficient.

Put another way, lets populate a dropdown combobox with 50 million items and set the item display limit to 15 items. So if you open that, and move the scrollbar with the mouse only 1 pixel, you'll probably scroll the items by 100,000. Absolute pointless behaviour and design.

I cannot see a single use case where that will be a good idea. If you have the time, read the book "About Face 3: The Essentials of Interaction Design". You might learn something.

Regards,
Graeme

I think that may not be possible. Your data may be ordered already, but that does not guerantee that there is not already data inside the tree that must be ordered "inside" the group you add?

I am thinking of loading a spreadsheet from file. Initially the sheet (= tree) is empty. The cells in the standard spreadsheet files are arranged by rows, starting at the top; and within each row, the cells are ordered from left to right. So, the reader catches the cells in the correct order (the tree sorts the cells exactly in the same way). A standard "Add" of the tree calls "FindInsertPos" which seeks for the correct position of the new cell. But every time this search starts from the root which is unnecessary from my pov because the new cell should be at the end. There is no "Append" or "AddtoEnd" method.

Maybe I should remember the node of the previously added cell, and when the next cell is to be added I should attach it as a right child of this node.

Unfortunately I am not very experienced with this kind of trees. For example: Is it necessary to rebalance the AVLtree immediately after each insertion, or can I wait until all nodes exist? There is a "BalanceAfterInsert" method with the new node as a parameter - this indicates that balancing should occur immediately after insert. But this method is private and thus cannot be called from a derived tree implementing an "AddToEnd" method.

Yes.
There are two versions of this AVL trees: The FPC unit avltree and the LazUtils unit avglvltree. It is the same tree, but with different names to avoid conflicts. New features go to the lazutils version and are later merged to the FPC version.

I added a function "AddAscendingSequence" to TAvgLvlTree for adding a sequence. Here is an example:

var
  LastNode, Successor: TAvgLvlTreeNode; i: integer;
begin
  LastNode:=nil;
  Successor:=nil;
  for i:=1 to 1000000 do
    LastNode:=Tree.AddAscendingSequence(TItem.Create(i),LastNode,Successor);
end;

In this example the number of compares are reduced from about 20 millions to 1 million. The time depends on your compare function. Usually compare functions are pretty quick, so in a simple example adding a sequence might be only twice as fast.

Mattias

Graeme Geldenhuys wrote

> I can also apply some more sophisticated functions like attribute change, delete, rename, etc. > where I would not like to be resticted on the number of files in any way. You don't need to see those items to apply those attributes.

I prefer to see the items before I change them instead of blindly relying on a filter. A filter may include items I did not want to (filters can get complex). I need the abillity to have at least a quick glance over the list before I do the changes.

> Filtering: Yes. But it's not always the first step! So pulling in 50+ million records into a data grid over a internet connection (or worse, a dial-up connection) simply for the sake of it, then only filtering down the data.... all seems very inefficient.

Why pulling records over an internet connection?
In this case the list needs to be hold on the server and the client just loads the next page if you scroll.
But as said: There are use cases where you may want to start with a filter and there are others where it is not.
Just let the user decide and do not force him to do it one way only.

Put another way, lets populate a dropdown combobox with 50 million items and set the item display limit to 15 items. So if you open that, and move the scrollbar with the mouse only 1 pixel, you'll probably scroll the items by 100,000. Absolute pointless behaviour and design.

I don't understand your example.
When a subset of 15 items is displayed and you scroll down then only the next subset (again 15 items) needs to be displayed. Where is the problem?
And when the slider is too sensitive for the large list then don't use it! Instead provide other ways to jump to specific entries. If I have a file list sorted by date I may jump to a specific date and then have the abilitiy to scroll around this date with the cursor keys or page up/down keys. Where is the problem?

I cannot see a single use case where that will be a good idea.

I mentioned the case of the file manager.
Just look at Xtree/Ztree.
The concept exists since decades and I am missing it in many other applications.

If you have the time, read the book "About Face 3: The Essentials of Interaction Design". You might learn something.

These books are just opinions of other people.
Nice to reed to get some ideas but they will never have the overall solution for all user interfaces.

BTW: In the end there is not much difference between filtering and showing a flat list. You will never see all entries side by side in one window. In both cases a subset is displayed.

When showing all entries you only see the first n records that fit on the window. After scrolling down, the next n records are shown. When jumping somewhere, still only n records need to be retrieved and shown. I don't see the problem with this.
It's just like applying a new filter with each scroll event.

When using a filter as the first step you get a list of all matching entries. But this list can get large too. You do not know before. Then you end up with the same problem:
A large list of entries that needs to be displayed to the user.

Yes, the optimization only works if you insert a sequence between two nodes. The new AddAscendingSequence checks that.

Mattias

An AddHighest can be added. Note that from a theoretical pov it still costs O(log n).

Maybe I should remember the node of the previously added cell, and when the next cell is to be added I should attach it as a right child of this node.

That's what AddAscendingSequence does.

Unfortunately I am not very experienced with this kind of trees. For example: Is it necessary to rebalance the AVLtree immediately after each insertion,

Yes, because the Balance factors are only valid for at most one error.

Well, theoretically you can create an optimized method that creates a fresh tree from a sorted list in O(n).

In TAvgLvlTree the BalanceAfterInsert is protected. I will send a new version to FPC.

Mattias

There are two versions of this AVL trees: The FPC unit avltree and the LazUtils unit avglvltree. It is the same tree, but with different names to avoid conflicts.

Does this mean: I can directly replace the TAVLTree by the TAvgLvlTree and the TAVLTreeNode by the TAvgLvlTreeNode to use the LazUtils tree and everything works as before? No other changes?

Yes.

Mattias

I am attaching my "benchmark" program. The stringtable implemented here is a quick copy & paste from fpspreadsheet code with minor modifications. Setting the define "AVL_TREE" in the project options activates the fpc AVLTree behind the table, while undefining it uses the LazUtils tree.

When running the test you'll see that the LazUtils tree is almost a factor 2 slower than the fpc tree. (0.6 sec vs 0.36 sec for populating a 1000x1000 table, 16 sec vs 9.8 sec for a 5000x5000 table). Any idea why the Lazarus tree is slower although the tree code should be the same, Mattias?

You'll see also that the new optimized AddAscendingSquence speeds things up considerably (4.6 sec vs 16 sec for 5000x5000). Since it calls the normal Add if the new node does not fit at its assumed position I suppose that nothing speaks against using this method as a general replacement of Add in fpspreadsheet.

Werner
-------------- next part --------------
A non-text attachment was scrubbed...
Name: StringTable_TREE.zip
Type: application/x-zip-compressed
Size: 6523 bytes
Desc: not available
URL: <http://lists.lazarus-ide.org/pipermail/lazarus/attachments/20170111/79e2732f/attachment.bin>

The FPC sources are compiled with -O2 and without any checks. And TAvgLvlTree had a further call when comparing. I inlined that now. Please test by compiling lazutils with -O2.
In my tests TAvgLvlTree is a bit faster than the old TAVLTree.

You'll see also that the new optimized AddAscendingSquence speeds things up considerably (4.6 sec vs 16 sec for 5000x5000).

Why should someone consider an unrealistic test?

Since it calls the normal Add if the new node does not fit at its assumed position I suppose that nothing speaks against using this method as a general replacement of Add in fpspreadsheet.

Probably.

Mattias

Mattias Gaertner wrote

The FPC sources are compiled with -O2 and without any checks. And TAvgLvlTree had a further call when comparing. I inlined that now. Please test by compiling lazutils with -O2. In my tests TAvgLvlTree is a bit faster than the old TAVLTree.

Right, I see this now too.

> You'll see also that the new optimized AddAscendingSquence speeds things > up considerably (4.6 sec vs 16 sec for 5000x5000). Why should someone consider an unrealistic test?

What's wrong with it?

Thank you for your changes!

AddAscendingSequence can be slower than a normal Add. You need to check common cases, not uncommon cases like generating a 5000x5000.

Mattias

Il 06/01/2017 13:40, Bart via Lazarus ha scritto:

And needless to say that the ICT department has forbidden me to use this program, because "it is not a commercial progra, and therefore there is no offical support for it, and unsupported programs cannot be installed on our system".

I think it would be useless to point out to your ICT department what happened to people using a supported commercial program lik Kylix (just to make an example), when Borland for its own stupid reasons decided to drop it!

A better approach could be to set up (yourself, or your sister if you have one, or an aged grandmother, or a friendly neighbour) a small company selling FPC, Lazarus or any other GPL software you know you can handle (it's perfectly legal to sell it, if you follow the licence rules) and providing support.

This would make both you and your ICT department happy, and maybe, instead of headaches you could even raise some extra money. ;-)

Give it a thought.

Giuliano

Mattias Gaertner wrote

You need to check common cases, not uncommon

IMHO it's very prone to error to deliberately define something as "common".

Even if you do a decent statistic of usage cases, this can vary after some time.

-Michael

Mattias Gaertner wrote

AddAscendingSequence can be slower than a normal Add. You need to check common cases, not uncommon cases like generating a 5000x5000.

I did not intend to write a general test which covers all "common" cases, but a test for the most relevant use case in my application in which users will notice the difference: reading a large file where nodes are in the correct order already.