On Tue, 10 Jan 2017 12:10:31 +0100
Werner Pamler via Lazarus <lazarus@lists.lazarus-ide.org> 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?
>
> 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.
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
--
_______________________________________________
Lazarus mailing list
Lazarus@lists.lazarus-ide.org
http://lists.lazarus-ide.org/listinfo/lazarus
