You are welcome using this topic for questions about how to use or possible bugs, posting code examples and suggestions about new features
LZLE can be found here : viewtopic.php?f=8&t=26533
What is it ? LZLE is an intuitive list implementation for FreeBasic :
It offers an instruction set for manipulating lists using some memory virtualization and map/reduce features.
-------------------- Preamble --------------------
One of the difficulties of using a list engine is the technical heterogeneity of the developers. It is difficult to meet the expectations of beginner or intermediate programmers while at the same time some developers will have developed their own tools and their own way of working with them.
This tool (LZLE) comes from my own experience and my own tools. Initially, I saw it only as a simple toolbox, that is to say that the homogeneity of the overall logic was only seen from an end user point of view. This global logic has been the subject of many technical and conceptual changes, such as the abandonment of the idea of the 'BranchConsider' on a body to the benefit of the 'Snatch' multi-instances at the same time richer, more flexible and more explicit. And so on.
As the project progressed, difficulties became clear:
First, at the technical level, the project was an opportunity to develop and acquire skills, even at a level sometimes dilettante or self-taught.
But the real challenge lies in the richness of the problem: from the moment you start working on the memory and that the program itself is a project to help the user to program on the memory, the Pandora's box the computer is open: there are always ideas for improvements and it affects both the performance and functionality or even the intrinsic logic of the tool's work.
Important functional and technical achievements are still to be considered but would require more time and especially skills from my point of view very specific or too difficult to acquire.
Accumulation of simple things makes it a complex result, and this complex result is itself simplistic with regard to the technical perspectives imaginable in the medium term or sometimes effective in another way in a professional context.
Working with the tool therefore involves learning. This is inevitable because the tool itself wants to be easy to approach must also be able to allow the achievement of complexity and because this complexity affects the way of working with RAM.
It is nevertheless possible to use the tool in a simple and effective way, but the deepening will always be exciting, if only by the ideas and perspectives of functional orientations.
The documentation thus becomes a site in its own right unless it is first done with a series of commented examples, which is the case here.
LZLE and its associated 'documentation' is not intended to deliver a truth about how to work with memory but to propose methods of analysis and associated practical solutions around the use of lists.
The way of using the tool is multiple leaving a space of expression to the creativity.
-------------------- Essential features --------------------
The tool can manage lists in memory indexed or unindexed, meaning : behave like a classic list or as a hashtable, depending on usage.
The developer thus specifies the most optimal memory management for his algorithms : the tool is used to better automate the management of the memory while keeping for the developer the possibility of a certain fineness in the specifications.
The basic syntax is similar to a ForEach:
ForEach ref in MyVar .. End ForEach
Is translated:
For i = 1 to MyList.AllOf: MyList.BlindStep
...
Next i
Or
MyList.AllOf:
For i = 1 to MyList.Count: MyList.BlindStep (-1)
...
Next i
Or
MyList.AllOf:
While MyList.fStep
..
Wend
But iterators are also available for indexed entries:
While MyList.HashStep
...
Wend
Iterators on indexed entries also work on unindexed entries.
To create an unindexed entry, use the keyword Tag (Key) or BlindTag (Key) (equivalent to Add (Key or Value)). Indeed, when we know in advance that the key is unique, and that we will not need an index, it is possible to fill fast an unindexed list using BlindTag.
To create an indexed entry, use the keyword HashTag (Key).
Same spirit for not indexed ('flat') lists :
mylist.Add ($ Key, $ Value) is translated:
mylist.BlindTag ($ Key): mylist.Val ($ Value) or mylist.BlindTag ($ Key): mylist.RwTag1 ($ Value) (depending on the value size)
mylist.Add ($ Key, $ Value1, $ Value2, etc) is translated:
mylist.BlindTag ($ Key): mylist.Val ($ Value1): mylist.BlindTag ($ Key): mylist.Val ($ Value2): etc
Or you can also support multi-values with string concatenation using .val property (long strings) :
mylist.BlindTag ($ Key): mylist.Val ($ Value1+stringSep+$ Value2+etc..)
Also available :
* Multi-values features using HashTag ($ Key) with HashKeyUnique property previously set to 0
* Reverse or partial iterarors on non indexed and indexed lists using fStepRev, BlindStep (-1), HashSpetpRev, KeyStepRev.
* You can choose how and when a list, a branch of a tree or even a listnode can be send to garbage or to protected flat list or to another list.
meaning : list data exchanges at any level supported, recycling on demand or on any subset or on whole list (using Snatch, NodeFlat, Recycle, GarbageFlat and GarbageSnatch).
* Data can be sent from indexed to non indexed and vice versa(NodeFlat and RestoreHash).
* Creation & management index supported (CopyCat and Follow).
* Syntax behavior is optimized for detecting new entries while setting (If MyList.HashTag ($ Key)).
* Soft deletion is possible on indexed lists (RwTag1 ("") and parsing with KeyStep).
* Reverse seek supported, other advanced optimizations options.
* Hierarchical count down. Consistent speed. Consistent deallocations.
* Tracking enable features that would require pointers just by instruction set extension and without having to manipulate pointers (HoldBack, Track, TrackStep)
A "companion extension" is in development and is dedicated to integration with Arrays https://freebasic.net/forum/viewtopic.php?f=8&t=27695
---------------------------------------------------------
001 : Basic knowledeges working with "flat" list
By 'flat list' we mean a list in which the elements are connected to each other in a sequential order: to find a given element we must then go through the elements that precede it. This type of list is the easiest to understand.
Code: Select all
' TUTO 001 : Basic knowledeges working with "flat" list
# Define IsTEST 0
# IF (IsTEST=1)
Print "Regular release" ' 0.994
#Include once "F:\Basic\LZLE_TEST.bi"
# ELSE
Print "NEW release" ' 0.995
#Include once "F:\Basic\LZLE_.bi"
# ENDIF
Dim MyList As List
Dim i As Integer
'Flat list : each flat list entry can be set with MyList.BlindTag("Key") : in a "flat" list elements are linked in a sequential order
'Be carefull : BlindTag just Add an element at the end of the list without checking if the Key already exists or not
'This is usefull fast filling a list with elements you know they are not redondant
For i=1 to 20
MyList.BlindTag(str(i)) ' str(i) is going to be the key of the element - this instruction create a new element in list
MyList.RwTag1(str(i) & "*") ' each element of the list can store a small value in Tag1 to Tag4 : for one small values just use Tag1 may be best choice
MyList.Val(str(i) & "+") ' a bigger string can be stored in MyList.Val
Next i
'Let's see the sequential parsing : this is equivalent a "Foreach"
For i=1 To MyList.AllOf : MyList.BlindStep
Print "Key= " & MyList.Tag & " " & MyList.Tag(1) & " " & MyList.Val
Next i
Sleep
'There is another way to parse a flat list
Print "Second Parsing method (Flat) :"
MyList.AllOf
While MyList.fStep
Print "Key= " & MyList.Tag & " " & MyList.Tag(1) & " " & MyList.Val
Wend
Sleep
' You can as well parse backward
Print "Third Parsing method (Flat) :"
MyList.AllOf
While MyList.fStepRev
Print "Key= " & MyList.Tag & " " & MyList.Tag(1) & " " & MyList.Val
Wend
Sleep
'Now we know how to fill and parse a flat list
'Important feature is to know wether an element is alraedy in list or not
If MyList.HasTag("15") Then
Print "Found : " & MyList.Tag & " " & MyList.Tag(1) & " " & MyList.Val
End If
'You can notice the current element is now the one was found
If MyList.HasTag("73") Then
'Never happend
Else
Print "Not Found : 73"
End If
Print "Current : " & MyList.Tag & " " & MyList.Tag(1) & " " & MyList.Val
MyList.fStep
Print "Current is now : " & MyList.Tag & " " & MyList.Tag(1) & " " & MyList.Val
Sleep
MyList.First
Print "Current : " & MyList.Tag & " " & MyList.Tag(1) & " " & MyList.Val ' this is the first "hidden" element : it is the starting point of the flat list
MyList.fStep
Print "Current is now : " & MyList.Tag & " " & MyList.Tag(1) & " " & MyList.Val
Sleep
Print
Print "---- Accessing elements while creating them ----"
'MyList.Tag("Key") is equivalent to BlindTag if an element does not exist and to HasTag if an element exist.
If MyList.Tag("15") Then 'Code for an Update
Print "Found : " & MyList.Tag & " " & MyList.Tag(1) & " " & MyList.Val
MyList.Val( MyList.Val + " ##")
Else
'Never happend
End If
If MyList.Tag("73") Then ' => "Creating 73"
'Never happend
Else 'Code for a new element
Print "New = 73"
MyList.RwTag1("73" & "*")
MyList.Val("73" & "+")
End If
MyList.Root
sleep
Print "Result :"
For i=1 To MyList.AllOf : MyList.BlindStep
Print "Key= " & MyList.Tag & " " & MyList.Tag(1) & " " & MyList.Val
Next i
MyList.First : MyList.fStep ' stepping hidden node
Print "First= " & MyList.Tag & " " & MyList.Tag(1) & " " & MyList.Val
MyList.Last : MyList.fStepRev ' stepping back hidden node
Print "Last= " & MyList.Tag & " " & MyList.Tag(1) & " " & MyList.Val
' Let's see some other feature
Print "Count= " & MyList.Count
Print "Value of Tag 12 = " & MyList.ValTag("12")
' Aside & Recover
For i=1 To MyList.AllOf : MyList.BlindStep
If MyList.Tag="17" Then : MyList.Aside : End If
Next i
Print "Current= " & MyList.Tag & " " & MyList.Tag(1) & " " & MyList.Val
MyList.Recover
Print "Recover= " & MyList.Tag & " " & MyList.Tag(1) & " " & MyList.Val
MyList.Destroy
gCollector.Destroy
Print "%%AllocateDeallocateCounter =" & AllocateDeallocateCounter
Sleep
System
fStep and fStepRev do this more securely and returns true if the next or previous element could be reached.
bStep is faster but does not check: a loop of type For i = 1 to MyList.AllOf: MyList.bStep: ..: Next i will be faster than a loop of type While MyList.fStep: .. : Wend both because of the For next and the gain of a test per node traveled. BlindStep is the backward-compatible version of fStep and also lets you navigate +n or -n items in the list at a time : MyList.BlindStep(3) jump 3 nodes forward, MyList.BlindStep(-2) jump 3 nodes backward with no check like bStep.
When using bStep or BlindStep(n) you must ensure you do not jump out of the list (before first node or after last node) otherwise you may crash or get unexpected results. fStep and fStepRev shall be secured.
fmove is changing the position of a node in a non indexed (flat) list
Code: Select all
# Define IsTEST 0
# IF (IsTEST=1)
Print "Regular release" ' 0.994
#Include once "F:\Basic\LZLE_TEST.bi"
# ELSE
Print "NEW release" ' 0.995
#Include once "F:\Basic\LZLE_.bi"
# ENDIF
Dim MyList As List
Dim i As Integer
For i=10 to 20
Print "Already exists ? " & MyList.Tag(str(i))
Next i
For i=1 to MyList.AllOf : MyList.bStep
Print MyList.Tag
Next i
Print "--------------"
Print "Current=" & MyList.Tag
sleep
Print "Current is send 4 nodes backward :"
MyList.fMove(-4)
For i=1 to MyList.AllOf : MyList.bStep
Print MyList.Tag
Next i
sleep
Print "Already exists ? " & MyList.Tag("11") ' Tag "11" already exists so, it just moving cursor to it.
' MyList.Tag("key") always set cursor to Tag and return 1 if key already exists in list otherwise return 0
' MyList.HasTag(key) Return 1 if key already exists in list otherwise return 0 and you can choose wether you want to set cursor on key on success or not (AutoCursor 0/1 property)
Print "Tag 11 is send 6 nodes forward :"
MyList.fMove(6) 'Tag 11 is send 6 nodes forward
For i=1 to MyList.AllOf : MyList.bStep
Print MyList.Tag
Next i
MyList.Destroy
gCollector.Destroy
Print "%%AllocateDeallocateCounter =" & AllocateDeallocateCounter
sleep
system
Code: Select all
# Define IsTEST 0
# IF (IsTEST=1)
Print "Regular release" ' 0.994
#Include once "F:\Basic\LZLE_TEST.bi"
# ELSE
Print "NEW release" ' 0.995
#Include once "F:\Basic\LZLE_.bi"
# ENDIF
Dim MyList As List
Dim i As Integer
For i=20 to 35
MyList.Tag(str(i))
MyList.RwTag1(Chr(100-i))
MyList.Val(" ==>" & str(i))
Next i
For i=1 to MyList.AllOf : MyList.bStep
Print "Tag=" & MyList.Tag & " - Tag1=" & MyList.Tag(1) & " value=" & MyList.Val
Next i
sleep
' Bug report (Beta 0.99) please replace the following line in LZLE ValTag Property:
' If bSearchRes=1 Then : If str_value=this.Tag(0) Then : pValTmp=pSearchNode : Return this.ValPrivate : End If
'By : If bSearchRes=1 And str_value=this.Tag(0) Then : pValTmp=pSearchNode : Return this.ValPrivate
'The list contains CONST MAX_COLS columns for values
Print "List contains 25 ? " & MyList.HasTag("25") & " ListContains K ? " & MyList.HasTag("K")
Print MyList.ValTag("30") & " is the value of key '30'"
MyList.ColTags(1) 'Setting working column to 1 (Tag1 is considered as if it were keys column
Print "List contains 25 ? " & MyList.HasTag("25") & " ListContains K ? " & MyList.HasTag("K")
Print MyList.ValTag("30") & " is the value of key '30'" 'Return empty string when key is not found
sleep
sleep
Print "CAREFULL : list till is on ColTag(1) mode : " & MyList.ColTags
For i=1 to MyList.AllOf : MyList.bStep
Print "Tag=" & MyList.Tag & " - Tag1=" & MyList.Tag(1)
Next i
sleep
Print "Just indicates working key tag is back to index 0"
MyList.ColTags(0)
For i=1 to MyList.AllOf : MyList.bStep
Print "Tag=" & MyList.Tag & " - Tag1=" & MyList.Tag(1)
Next i
sleep
Print "Doing a 'flat' sort Ascending but on index column 1 :"
MyList.ColTags(1)
' MyList.ColSort(0)
MyList.fSort
For i=1 to MyList.AllOf : MyList.bStep
Print "Tag=" & MyList.Tag & " - Tag1=" & MyList.Tag(1)
Next i
sleep
'Please note that First and Last are pointing nodes that are previous first key and after last key
'Because these instructions are mostly used for preparing iteration
MyList.First : MyList.BlindStep
Print "First=" & MyList.Tag
MyList.Last : MyList.BlindStep(-1)
Print "Last=" & MyList.Tag
Print "Count=" & MyList.Count
MyList.Destroy
gCollector.Destroy
Print "%%AllocateDeallocateCounter =" & AllocateDeallocateCounter
sleep
system
002 : Understanding list implementation
What we call here a hash list is a cascading tree of keys, the concatenation of the cascaded keys forming the key of an element of the list. This name of "hash list" does not correspond to the technical or scientific terminology but to an intuitive interpretation used in the common language (by reference to #HashTag which is worldwide known by anybody as a keyword allowing to access the data related). Each branch of the tree is concretely a "flat list" and each flat list is made of sequential cascaded keys (Tags). Thus, a hash list is a hierarchical organization of flat lists with n levels sharing in principle the same length of cascaded keys. (the key is split into a hierarchy of sub-keys called Tags which are assigned to the hierarchical tree). So far, you can see a hash list as an indexed list. The main interest is the search speed which is much faster on indexed values.
=> LZLE helps user handling the complexity of indexed lists as they can be manipulated combining advantages of non indexed lists.
One example is if the list contains the keys "12" and "123" : the list element containing the Tag "2" will be at the same time the last element of the key "12", but also the cascaded tag allowing access to "3", last element forming the key "123". By key, we mean the complete key representing a hashtag. Each hashtagged value represent a key item accessing to an element of the list thrue a hierarchy of Tags.
=> Working with list is becoming very easy just having a mental representation of that tree of indexed values, and imagine you can just pick values in the tree to send them to a garbage collector, to a protected flat list or to another list and vice-versa.
To resume this a very simple way :
MyList.HashTag("1234") => "1", "12", "123" and "1234" are 'HashTags' but only "1234" is 'HashKey' as well
MyList.HashTag("1234") and MyList.HashTag("12") => => "1", "12", "123" and "1234" are 'HashTags', "12" and "1234" are 'HashKeys'
A value will be (automatically) considered as a key from the moment it has been explicitely 'hashtagged'
The exemple below illustrate the difference between keys and tag (cascaded parts of a key).
Code: Select all
' TUTO 002 : Understanding list implementation
' The list object is a combination of 3 lists (basically)
' 1 : a TREE list (elements are linked as a tree structure, so they are indexed) and this Tree can be manipulated as well as a "hash list" (tree) or as a flat list into any branch of the tree
' 2 : a Garbage Collector which is a sequential (flat) list of element identified by Chr(3)
' 3 : a Protected flat list which is a sequential (flat) list of element that is a children of the First visible node Chr(4)
' It is important to understand some of the power of the engine is the hability to handle Tree items as if they were flat and the user
' can goes from flat to tree or from tree to flat in a list depending on the optimization strategy he or she wants to implement in algorithms.
' Working with list is becoming trivial just having a mental representation of that tree of indexed values, and imagine you can just pick values in the tree to send them to garbage collector or to protected flat list
' You don't have to manage Garbage Collector, it is automatic.
' Protected flat list is so called, because you can "Recycle" a whole tree, sending all items to garbage collector, the protected flat list is not destroyed and can be restored as an index (tree)
' A lot of other features are also provided : for exemple, it is possible to use several instances to perform some specific manipulations such as working just on a part of a tree or sending datas to another list
# Define IsTEST 0
# IF (IsTEST=1)
Print "Regular release" ' 0.994
#Include once "F:\Basic\LZLE_TEST.bi"
# ELSE
Print "NEW release" ' 0.995
#Include once "F:\Basic\LZLE_.bi"
# ENDIF
Dim MyList As List
Dim i As Integer
For i=220 to 240
MyList.HashTag(Str(i))
Next i
Print "TREE Representation --"
MyList.RootNode
While MyList.HashStep
Print "Key= " & MyList.HashTag & " current Tag=" & MyList.Tag
Wend
Print "----------------------"
Print "1st element Key=" & Chr(4) & " Tag=" & Chr(4) & " = Protected flat list entry"
Print "2nd element Key=" & Chr(4) & " Tag= : Protected flat list always contain an empty element"
Print "3rd element Key=" & Chr(3) & " Tag=" & Chr(3) & " Garbage Collector always contain at least 1 element"
Print "Tree structure : by default, the keys are indexed character by character"
Print "----------------------"
Sleep
Print
Print "KEYS Representation --"
MyList.Root
While MyList.KeyStep
Print "Key= " & MyList.HashTag & " current Tag=" & MyList.Tag
Wend
Print "----------------------"
sleep
' Notice a element is marked as a key as soon as it has been "HashTagged"
' This is indicated by Tag1 wich is not empty (if no value, the key is indicated by a blank)
Print "New HashTag 23"
MyList.HashTag("23")
MyList.Root
While MyList.KeyStep
Print "Key= " & MyList.HashTag & " current Tag=" & MyList.Tag
Wend
Print "----------------------"
Sleep
MyList.HashTag("23") ' Set cursor to key "23"
MyList.RwTag1("") ' unmark the element as key
MyList.Root
While MyList.KeyStep
Print "Key= " & MyList.HashTag & " current Tag=" & MyList.Tag
Wend
Print "----------------------"
Print
Sleep
' Same as Tag with flat list, HashTag is returning 1 if element exist, otherwise it is created
If MyList.HashTag("24") Then
Print "24 found : code for updating values associated with that key (Tag1-4 and Val)"
Else
'Never happend
End If
If MyList.HashTag("21") Then
'Never happend
Else
Print "21 not found but now created : code for new values"
End If
' This is very practical when adding new values to an indexed list
' Same as HasTag with flat list, HasHashTag is testing wether an element is present or not but without creating it
If MyList.HasHashTag("21") Then
Print "21 found"
End If
If MyList.HasHashTag("19") Then
Print "19 not found, not created"
End If
Sleep
MyList.Root
While MyList.KeyStep
Print "Key= " & MyList.HashTag & " current Tag=" & MyList.Tag
Wend
Print "----------------------"
' But now, do not forget we are parsing a tree wich some elements are keys and other not
' So, HasKey is equivalent to HasHashTag returning 1 only on Key elements, 0 if HashTag exists, otherwise -1
If MyList.HasKey("220") Then
Print "Key 220 found"
End If
If MyList.HasKey("22") Then
Else
Print "Key 22 NOT found"
End If
'Like the flat list, you can also parse backward
Print "Parse back showing whole Tree structure"
MyList.Root
While MyList.HashStepRev
Print "Key= " & MyList.HashTag & " current Tag=" & MyList.Tag
Wend
Print "*----------------------"
sleep
Print "Parse back showing keys"
MyList.Root
While MyList.KeyStepRev
Print "Key= " & MyList.HashTag & " current Tag=" & MyList.Tag
Wend
Print "%----------------------"
MyList.Destroy
gCollector.Destroy
Print "%%AllocateDeallocateCounter =" & AllocateDeallocateCounter
sleep
system
Code: Select all
' TUTO 003 : Navigating
# Define IsTEST 0
# IF (IsTEST=1)
Print "Regular release" ' 0.994
#Include once "F:\Basic\LZLE_TEST.bi"
# ELSE
Print "NEW release" ' 0.995
#Include once "F:\Basic\LZLE_.bi"
# ENDIF
Dim MyList As List
Dim i As Integer
For i=220 to 240
MyList.HashTag(Str(i))
Next i
Print "TREE Representation --"
MyList.RootNode
While MyList.HashStep
Print "Key= " & MyList.HashTag & " current Tag=" & MyList.Tag
Wend
Print "0----------------------"
Sleep
'The list can be parse as a series of flat lists
MyList.Root
While MyList.fStep
Print "HashTag=" & MyList.HashTag & " current Tag=" & MyList.Tag
Wend
Print "1----------------------"
' Note the root list just contains "2"
Print "Tag2 exists ? " & MyList.Tag("2")
Print "Going to sublist (children) of 2"
MyList.Down
'Print "*HashTag=" & MyList.HashTag & " current Tag=" & MyList.Tag
While MyList.fStep
Print "HashTag=" & MyList.HashTag & " current Tag=" & MyList.Tag
Wend
Print "2----------------------"
'sleep : system
MyList.Tag("3")
Print "Going to sublist (children) of 3"
MyList.Down
While MyList.fStep
Print "HashTag=" & MyList.HashTag & " current Tag=" & MyList.Tag
Wend
Print "Returning to level up"
MyList.Up ' Up and Down will return 1 on success and 0 on failure (if you are top or bottom of the list)
MyList.AllOf
While MyList.fStep
Print "HashTag=" & MyList.HashTag & " current Tag=" & MyList.Tag
Wend
' It is possible to navigate up and down, but also to direct access with HashTag
Print "Direct access to 22"
MyList.HashTag("22")
MyList.AllOf
While MyList.fStep
Print "HashTag=" & MyList.HashTag & " current Tag=" & MyList.Tag
Wend
Print "-----"
' Aside and Recover also operational with indexed elements
MyList.Aside
MyList.Root : MyList.fStep
Print "HashTag=" & MyList.HashTag & " current Tag=" & MyList.Tag
MyList.Recover
Print "HashTag=" & MyList.HashTag & " current Tag=" & MyList.Tag
MyList.Destroy
gCollector.Destroy
Print "%%AllocateDeallocateCounter =" & AllocateDeallocateCounter
sleep
system
The lzle engine is inspired by the following paradigms:
The work of the processor on the RAM is approached from the angle of a logistic flow optimization problem: each memory address or element of the list is a little like a small packet that must be sent to the destination. What matters is not the routing speed of a package but the overall fluidity. Take a metaphor: the Wintergaten Marble Machine (see YouTube): each ball vector is a node of the list, the re-routing of the balls must be continuous with minimal cost. The music is your program, the notes represent the progress of your algorithm and the fall of the metal balls as you reuse the memory continuously.
The list engine knows that each ball is identical and therefore substitutable, whereas at the level of the VM of the OS this information can not be presupposed. As soon as the memory substitution takes place in the program, it is not necessary for the OS or the machine to request the cache to defragment and organize the reallocation.
Intrinsic optimization is more about flow efficiency than pure speed, trying to keep cache and UAL as safe as possible.
The cache can be used, for example, for quick tables to perform calculations from reading the list's nodes, such as musical notes in your algorithms.
Similarly, any optimization calculation has a cost and the UAL that is not requested to accelerate the calculation of memory access remains available for other processes, which can be useful if you plan to launch several programs using simultaneously the engine lzle.
Two other points are also to consider:
Parsing optimization: complex because variable and dependent on the structure of the dataset. This problem is approached in two ways: by the presence of a basic optimization algorithm (will be the object of future evolutions, depending on the results obtained) but effective for the sequential keys (transparent to the user) of a on the one hand, by the flexibility allowed by the instruction set to allow finesse in the coding on the other hand, the latter point being very important to consider.
The optimization of the memory load: it can be technical (length of hashLen intermediate keys to optimize rather than the speed or the memory), or conceptual and algorithmic of the developer by the way the keys are organized (more the left part is common to a large number of keys, the less the tree will take up space in memory).
In the musical field, there is no better solution. It is thought that the instrument serves the musician whereas it is sometimes the musician should be at the service of his instrument.
004 : Using meters and exemple with HashTag/NodeFlat/RestoreHash (?=>"Map/Reduce/Rollbackreduce")
Like the notion of 'HashTag' which is not a hash key, the notion of 'Map Reduce' is an analogy. It is possible to browse the algoritmic tree in a manner that appears recursive to the user and implement key association functions. An example of feedback from the lower nodes is the calculation function of the count by branch. But the analogy relates to the notion of transformation from a tree structure to a sequential structure in ram. There is no parallelization, but we could see the tool as an aid to the preparation of input data, or as a tool for experimenting data processing.
Code: Select all
' TUTO 004 : Using meters and exemple with HashTag/NodeFlat/RestoreHash (?=>"Map/Reduce/Rollbackreduce")
' The list object implements the following meters :
' MyList.Count : the number of elements in current flat list
' MyList.NodeCount : the number of elements that were created :
' this number is bigger than the number of elements you can normally parse because some of them are hidden when parsing
' each flat list is preceeded by an hidden entry element
' MyList.BranchCount : the number of chidrens in a branch : this meter is off by default because it is consuming a few ressources to update meters of each parents nodes on each move
' MyList.FlatCount : the number of elements in protected flat list
' MyList.GarbageCount : the number of elements in GarbageCollector
' MyList.ContainerCount : the number of MyList.Val in hidden GarbageCollector : usually, you do not need to care with this
# Define IsTEST 0
# IF (IsTEST=1)
Print "Regular release" ' 0.994
#Include once "F:\Basic\LZLE_TEST.bi"
# ELSE
Print "NEW release" ' 0.995
#Include once "F:\Basic\LZLE_.bi"
# ENDIF
Dim MyList As List
Dim i As Integer
MyList.BranchCountDown(1) 'Activate
For i=220 to 240
MyList.HashTag(Str(i))
Next i
Print "TREE Representation --"
MyList.Root
While MyList.HashStep
Print "Key= " & MyList.HashTag & " current Tag=" & MyList.Tag & " branch " & str(MyList.BranchCount) & " count=" & str(MyList.Count)
Wend
Print "----------------------"
Sleep
'Let's Garbage the tree
MyList.Recycle
MyList.RootNode
While MyList.HashStep
Print "Key= " & MyList.HashTag & " Tag=" & MyList.Tag
Wend
Print "----------------------"
Print "De-referenced elements=" & MyList.GarbageCount & " Total elements=" & MyList.NodeCount
' About NodeCount : Garbage=29 elements + 1 Last + 1 First (not visible) + 2 for flat list + 3 (internal)=36
Sleep
For i=120 to 130
MyList.HashTag(Str(i))
Next i
Print "TREE Representation --"
MyList.RootNode
While MyList.HashStep
Print "Key= " & MyList.HashTag & " current Tag=" & MyList.Tag & " branch " & str(MyList.BranchCount) & " count=" & str(MyList.Count)
Wend
Print "----------------------"
Print "De-referenced elements = " & MyList.GarbageCount & " Total elements=" & MyList.NodeCount
Sleep
' Total of elements is same because the new tree construction used de-refenced nodes
Print "Now sending 2 elements of the Tree to the protected flat list"
MyList.NFrecursive(1)
MyList.HashTag("121") : MyList.NodeFlat
MyList.HashTag("122") : MyList.NodeFlat
MyList.NFrecursive(0)
' This for the exemple, NodeFlat is multimode and is designed by default to be used into a Loop using HashStep or KeyStep
' Outside the Loop scope, we may specified NFrecursive(1) thrue otherwise parents nodes will be ignored by NodeFlat with consequence Tree index not properly maitained & memory usage not optimal.
Print "TREE Representation --"
MyList.RootNode
While MyList.HashStep
Print "Key= " & MyList.HashTag & " current Tag=" & MyList.Tag & " branch " & str(MyList.BranchCount) & " count=" & str(MyList.Count)
Wend
Print "----------------------"
' 121 and 122 have been moved to flat list
Print "Flat list=" & MyList.FlatCount
Print "De-referenced elements=" & MyList.GarbageCount & " Total elements=" & MyList.NodeCount
Print
Print "Now accessing and parsing the flat list"
MyList.FlatStack
While MyList.fStep
Print "Key= " & MyList.HashTag & " current Tag=" & MyList.Tag
Wend
Print
Print "Or alternative parsing for protected flat list"
For i=1 To MyList.AllOf : MyList.fStep
Print "Key= " & MyList.HashTag & " current Tag=" & MyList.Tag
Next i
Print
' To leave the protected flat list just do (and not MyList.Up)
Print "KeyStep : "
MyList.Root
While MyList.KeyStep
Print "Key= " & MyList.HashTag & " current Tag=" & MyList.Tag
Wend
Print "----------------------"
Sleep
Print "Sending 124 and 125 to derefenced elements"
MyList.NFMethod(-1) 'Default is 1
MyList.HashTag("124") : MyList.NodeFlat
MyList.HashTag("125") : MyList.NodeFlat
MyList.RootNode
While MyList.HashStep
Print "Key= " & MyList.HashTag & " current Tag=" & MyList.Tag
Wend
Print "----------------------"
Print "De-referenced elements=" & MyList.GarbageCount & " Total elements=" & MyList.NodeCount
Sleep
' Let's Garbage the tree
MyList.Recycle
MyList.RootNode
While MyList.HashStep
Print "Key= " & MyList.HashTag & " current Tag=" & MyList.Tag
Wend
Print "Tree garbaged ----------------------"
' Accessing flat list
Print "Accessing and parsing the flat list"
MyList.FlatStack
While MyList.fStep
MyList.RestoreHash
Wend
MyList.RootNode
While MyList.HashStep
Print "Key= " & MyList.HashTag & " current Tag=" & MyList.Tag & " branch " & str(MyList.BranchCount) & " count=" & str(MyList.Count)
Wend
Print "121 and 122 are now restored as indexed elements"
MyList.Destroy
gCollector.Destroy
Print "%%AllocateDeallocateCounter =" & AllocateDeallocateCounter
sleep
system
The list object is a combination of 3 lists (basically)
1 : a Tree list (elements are linked as a tree structure, so they are indexed) and this Tree can be manipulated as well as a "hash list" (tree) or as a flat list into any branch of the tree
2 : a Garbage Collector which is a sequential (flat) list of element identified by Chr(3)
3 : a Protected flat list which is a sequential (flat) list of element that is a children of the First visible node Chr(4)
In combination with Map/Reduce/RollBackReduce, data exchanges and possibilities of navigation, a wide panel of operations can be performed on indexed lists in a very intuitive and versatile way.
Code: Select all
' TUTO 005 : Managing several instances
# Define IsTEST 0
# IF (IsTEST=1)
Print "Regular release" ' 0.994
#Include once "F:\Basic\LZLE_TEST.bi"
# ELSE
Print "NEW release" ' 0.995
#Include once "F:\Basic\LZLE_.bi"
# ENDIF
Dim MyList_1 As List
Dim MyList_2 As List
Dim i As Integer
For i=220 to 240
MyList_1.HashTag(Str(i))
Next i
Print "TREE Representation --"
MyList_1.Root
While MyList_1.HashStep
Print "Key= " & MyList_1.HashTag & " current Tag=" & MyList_1.Tag
Wend
Print "----------------------"
Sleep
Print "Going 22 on list 1"
MyList_1.HasHashTag("22") 'Set cursor to 22 without making "22" considered a key
Print "Key= " & MyList_1.HashTag
Print "List 2 Snatching List 1"
MyList_2.Snatch(MyList_1)
Sleep
Print "Result on List 1 :"
MyList_1.RootNode
While MyList_1.HashStep
Print "Key= " & MyList_1.HashTag & " current Tag=" & MyList_1.Tag
Wend
Print "----------------------"
Print
Sleep
Print "Result on List 2 :"
MyList_2.RootNode
While MyList_2.HashStep
Print "Key= " & MyList_2.HashTag & " current Tag=" & MyList_2.Tag
Wend
Print "----------------------"
Sleep
'Let's Garbage the tree
MyList_2.Recycle
Print "Tree garbaged on list 2"
Print "Result on List 2 :"
MyList_2.RootNode
While MyList_2.HashStep
Print "Key= " & MyList_2.HashTag & " current Tag=" & MyList_2.Tag
Wend
Print "----------------------"
Sleep
'Now List 1 is snatching Lit 2 garbage
Print "List 1 garbage count=" & MyList_1.GarbageCount
Print "List 2 garbage count=" & MyList_2.GarbageCount
MyList_1.GarbageSnatch(MyList_2)
Print "List 1 new garbage count=" & MyList_1.GarbageCount
Print "List 2 new garbage count=" & MyList_2.GarbageCount
Print "Result on List 1 :"
MyList_1.RootNode
While MyList_1.HashStep
Print "Key= " & MyList_1.HashTag & " current Tag=" & MyList_1.Tag
Wend
Print "----------------------"
MyList_1.Destroy : MyList_2.Destroy
gCollector.Destroy
Print "%%AllocateDeallocateCounter =" & AllocateDeallocateCounter
Sleep
' Snatch can be performed from a list to another on anywhere : a branch of the Tree,
' the dereferenced elements list, or even the protected flat list
' In previous exemple we used Snatch to garbage a specific branch in List 1, transfering work to a second List instance
' We can imagine List2 can be used as filter to transfert choosen element to flat list 2, and so on
' In combination with Map/Reduce/RollBackReduce and possibilities of navigation, a so wide panel of
' operations can be performed on indexed lists in a very intuitive and versatile way
System
Here some new exemple and one FIX :
Illustrate how to sort & track
Code: Select all
# Define IsTEST 0
# IF (IsTEST=1)
Print "Regular release" ' 0.994
#Include once "F:\Basic\LZLE_TEST.bi"
# ELSE
Print "NEW release" ' 0.995
#Include once "F:\Basic\LZLE_.bi"
# ENDIF
Dim MaListe1 As List
Dim i as integer
'MaListe1.Root
Print "Start"
MaListe1.HashTag("D4") : MaListe1.HoldBack : MaListe1.RwTag1("D4-1")
MaListe1.HashTag("C") : MaListe1.HoldBack : MaListe1.RwTag1("C")
MaListe1.HashTag("A") : MaListe1.HoldBack : MaListe1.RwTag1("A")
MaListe1.HashTag("B") : MaListe1.HoldBack : MaListe1.RwTag1("B")
MaListe1.HashTag("C5") : MaListe1.HoldBack : MaListe1.RwTag1("C5")
MaListe1.HashTag("C4") : MaListe1.HoldBack : MaListe1.RwTag1("C4")
MaListe1.HashTag("C3") : MaListe1.HoldBack : MaListe1.RwTag1("C3")
MaListe1.HashTag("D2") : MaListe1.HoldBack : MaListe1.RwTag1("D4-2")
MaListe1.HashTag("D1") : MaListe1.HoldBack : MaListe1.RwTag1("D4-3")
MaListe1.Root
While MaListe1.KeyStep
Print MaListe1.HashTag
Wend
Print ' "OK -------------"
Sleep
Print "Liste 1 (...Partial sort on D branch) :"
MaListe1.Root : MaListe1.HashTag("D") : MaListe1.Down
MaListe1.fSort
MaListe1.Root
While MaListe1.HashStep
Print MaListe1.HashTag
Wend
Print "OK -------------"
sleep
Print "Snatching C branch from List 1 to List2 : "
Dim MaListe2 As List
MaListe1.HashTag("C")
MaListe2.Snatch(MaListe1)
Print "Liste 1 :"
MaListe1.Root
While MaListe1.KeyStep
Print MaListe1.HashTag
Wend
Print ' "OK -------------"
Print "Liste 2 :"
MaListe2.Root
While MaListe2.KeyStep
Print MaListe2.HashTag
Wend
sleep
Print
Print "Sorting Liste 2 in 2 steps :"
MaListe2.NFMethod(1)
MaListe2.Root
While MaListe2.HashStep
MaListe2.NodeFlat
Wend
MaListe2.HashSort(1)
MaListe2.FlatStack
While MaListe2.fStep
MaListe2.RestoreHash
Wend
'Print "OK -------------"
Print "Liste 2 sorted after Reduce+Restore :"
MaListe2.Root
While MaListe2.KeyStep
Print MaListe2.HashTag
Wend
'MaListe2.Root : MaListe2.fStep
MaListe2.HashTag("C") ' Set cursor to C on liste 2 : snatch entry point
MaListe1.Root
MaListe1.Snatch(MaListe2)
Print "OK -------------"
Print "Liste 1 (partially sorted) :"
MaListe1.Root
While MaListe1.HashStep
Print MaListe1.HashTag
Wend
Print : sleep
MaListe1.fSortMethod(-1)
MaListe1.Root : MaListe1.fSort
Print "Liste 1 : root flat list REV sorted !! ) :"
MaListe1.Root
While MaListe1.HashStep
Print MaListe1.HashTag
Wend
Print "OK -------------"
sleep
Print "Reduce+Restore on Liste1's root flat list"
MaListe1.Root : MaListe1.NFMethod(3)
While MaListe1.fStep
MaListe1.NodeFlat
Wend
MaListe1.FlatStack
MaListe1.HashSort(1)
While MaListe1.fStep
Print "Restoring sorted : " & MaListe1.Tag
MaListe1.RestoreHash
Wend
Print "Liste 1 (...sorted !! ) :"
MaListe1.Root
While MaListe1.HashStep
Print MaListe1.HashTag
Wend
Print "OK -------------"
sleep
MaListe1.fSortMethod(-1)
MaListe1.Sort
Print "WHOLE Liste 1 (...sorted Rev !! ) :"
MaListe1.Root
While MaListe1.HashStep
Print MaListe1.HashTag
Wend
Print "OK -------------"
sleep
Print "Chronological parsing on List1 :"
MaListe1.Root
MaListe1.Track
While MaListe1.TrackStep
Print MaListe1.HashTag
Wend
Print "Reduce+Restore + HoldBack Tracking - fixed"
Print
sleep
Print "Sorting on Tag1 :"
MaListe1.fSortMethod(1)
MaListe1.ColSort(1)
MaListe1.Sort
MaListe1.Root : MaListe1.RootNode
While MaListe1.HashStep
Print MaListe1.HashTag & " Tag1= " & MaListe1.Tag(1)
Wend
Print "###############"
Print "Fin"
Sleep
Print "%?=" & AllocateDeallocateCounter & " nodecount=" & MaListe1.NodeCount
MaListe1.Destroy :MaListe2.Destroy : gCollector.Destroy
Print "%%=" & AllocateDeallocateCounter & " nodecount=" & MaListe1.NodeCount
sleep
system
Code: Select all
# Define IsTEST 0
# IF (IsTEST=1)
Print "Regular release" ' 0.994
#Include once "F:\Basic\LZLE_TEST.bi"
# ELSE
Print "NEW release" ' 0.995
#Include once "F:\Basic\LZLE_.bi"
# ENDIF
Dim MaListe As List ': MaListe.Root
MaListe.HashLen(1)
MaListe.SeekMethod(1)
MaListe.HashSort(1)
Dim str_tmp As String="ABCDEFGHIJKLMNOPKRSTUVWXYZ"
Dim i as integer : Dim t as integer : Dim k as string
Print time
For t=1 To 12
Print "Clef ++"
For i=2000000 To 1000000 Step -1
MaListe.HashTag( str_tmp & str(i)) : MaListe.RwTag1("#" & str(i)) : MaListe.RwTag2("123456" & str(i)) : MaListe.RwTag3("123456" & str(i)) : MaListe.RwTag4("123456" & str(i))
Next i
If str_tmp<>"" Then : Print "Oui" : Else : Print "Non" : End If
Print "Sorting"
If t=1 or t=2 Then
Print "Sorting using whole rebuild "
MaListe.Root
MaListe.NFMethod(1)
While MaListe.KeyStep
MaListe.NodeFlat
Wend
MaListe.FlatStack
While MaListe.fStep
' ? "* " & MaListe.HashTag
MaListe.RestoreHash
Wend
' MaListe.Up
Else
'MaListe.Root
Print "Sorting using Sort property "
MaListe.Sort
End If
Print "Sorting done"
Print "Garbage=" & MaListe.GarbageCount
Print "Recycle.." & MaListe.Recycle
' Print "Dealloues=" & MaListe.DropAll & " nodecount=" & MaListe.NodeCount
' Print "Recycle : garbage=" & MaListe.GarbageCount & " container=" & MaListe.ContainerCount
If str_tmp="" Then : str_tmp="ABCDEFGHIJKLMNOPKRSTUVWXYZ" : Else : str_tmp="" : End If
Next t
Print time
Print "Fin"
'MaListe.DropAll
Print "%?=" & AllocateDeallocateCounter & " nodecount=" & MaListe.NodeCount
MaListe.Destroy : gCollector.Destroy
Print "%%=" & AllocateDeallocateCounter & " nodecount=" & MaListe.NodeCount
sleep
system
Code: Select all
# Define IsTEST 0
# IF (IsTEST=1)
Print "Regular release" ' 0.994
#Include once "F:\Basic\LZLE_TEST.bi"
# ELSE
Print "NEW release" ' 0.995
#Include once "F:\Basic\LZLE_.bi"
# ENDIF
Dim MaListe1 As List
Dim i As Integer
For i=110 to 122
MaListe1.HashTag(str(i)) : MaListe1.RwTag1(str(i-100))
Next i
MaListe1.NFMethod(1)
MaListe1.Root
While MaListe1.HashStep
MaListe1.NodeFlat
Wend
MaListe1.Recycle
Print "#"
MaListe1.RootNode
While MaListe1.HashStep
Print MaListe1.HashTag & " - " & MaListe1.Tag(1)
Wend
Print "##"
sleep
MaListe1.ColTags(1)
MaListe1.RHmethod(1)
MaListe1.FlatStack
While MaListe1.fStep
If MaListe1.Tag<>"" Then
? "Restoring to tree structure=>" & MaListe1.Tag(1)
MaListe1.RestoreHash
End If
Wend
Print "*"
MaListe1.ColTags(0)
MaListe1.Root
While MaListe1.HashStep
Print MaListe1.HashTag & " - " & MaListe1.Tag(0) & " -" & MaListe1.Tag(1) & "-"
Wend
Print "fin"
MaListe1.Destroy : gCollector.Destroy
Print "%%=" & AllocateDeallocateCounter & " nodecount=" & MaListe1.NodeCount
sleep
system
Code: Select all
# Define IsTEST 0
# IF (IsTEST=1)
Print "Regular release" ' 0.994
#Include once "F:\Basic\LZLE_TEST.bi"
# ELSE
Print "NEW release"' 0.995
#Include once "F:\Basic\LZLE_.bi"
# ENDIF
Dim MaListe As List
Dim MaListe2 As List
Dim i as integer
For i=11 to 28
MaListe.HasHTag(Str(i))
MaListe.RwTag1("ABC"+Str(i))
If i=14 Or i=15 Or i=20 Or i=21 Then : MaListe.RwTag1("ABC13") : End If
MaListe.Val("Long string accepted here.. "+Str(i))
Next i
MaListe.HasHTag("1") : MaListe.RwTag1("") ' 1 is not a key, so RwTag1("") neutralize HashTag implicit key setting. This way HashTag is used as a if it were a setcursor before copying to List2
'***********************
MaListe.ColTags(1) ' The index on list2 will be build from list's tag1 (not from tree hierarchy cascaded keys
MaListe.CopyCatMethod(0)
MaListe2.TrackMultiKeys(1) ' Is Doing a HolBack on each indexed key
MaListe.CopyCat(MaListe2) 'CopyCat is a special feature wich is copying a branch from a list to another while setting a tracking from List2 to source list : this tracking is used by SourceList.Follow(TargetList)
' It is possible to use destination list (List2) as an index on source list. It is also possible to build several indexes on a single source list.
' Optimize mem usage to requirements increasing or decreasing Constants RUP_COLS=1 and MAX_COLS=5 depending on the number of indexes needed
MaListe.ColTags(0)
Print "MV auto tracking"
MaListe2.Track(1)
While MaListe2.TrackStep
' Print MaListe2.HashTag
MaListe.Follow(MaListe2)
Print "hashtag=" & MaListe.HashTag & " tag1=" & MaListe.Tag(1) & " value=" & MaListe.Val & " List2=" & MaListe2.HashTag
Wend
Print "ok?"
sleep
MaListe.HasHTag("2") : MaListe.RwTag1("TITI")
MaListe.ColTags(1)
MaListe.CopyCat(MaListe2)
MaListe.ColTags(0) ' Back to 'Normal' context
Print "List2 : "
MaListe2.Root
While MaListe2.HashStep
Print "hashtag=" & MaListe2.HashTag
Wend
Print "---------------"
Sleep
Print
Print "List :"
MaListe.Root
While MaListe.HashStep
Print "hashtag=" & MaListe.HashTag & " tag1=" & MaListe.Tag(1) & " value=" & MaListe.Val
Wend
Print "---------------"
sleep
MaListe2.HasHTag("ABC12")
MaListe.Follow(MaListe2)
Print "Following exemple :"
Print "Key=" & MaListe.HasHTag & " val=" & MaListe.Val
sleep
Print
Print "Follow in a loop"
MaListe2.fSortMethod(-1)
MaListe2.Sort
MaListe2.Root
While MaListe2.HashStep
'While MaListe2.KeyStep
If MaListe.Follow(MaListe2) Then
Print " Maliste hashTag= " & MaListe.HashTag & " - Maliste2 hashTag= " & MaListe2.HashTag ' & " val=" & MaListe.Val
Else
Print "* " & MaListe2.HashTag
End If
Wend
Print "---------------"
Print "MV auto tracking"
MaListe2.Track(1)
While MaListe2.TrackStep
' Print MaListe2.HashTag
MaListe.Follow(MaListe2)
Print "hashtag=" & MaListe.HashTag & " tag1=" & MaListe.Tag(1) & " value=" & MaListe.Val & " List2=" & MaListe2.HashTag
Wend
Print "?? ok?"
sleep
MaListe2.Root
MaListe.Destroy : MaListe2.Destroy : gCollector.Destroy
Print "??=" & AllocateDeallocateCounter & " nodecount=" & MaListe.NodeCount & " container=" & MaListe.ContainerCount & " nodecount=" & MaListe2.NodeCount & " container=" & MaListe2.ContainerCount
Print "Fin"
sleep
system