Two Chop Binary Tree / faster than hash

[Stanley Durham]

WORD/LONG ~ Key/Value ~ Tree

Chop Tree: comments

This is a small binary tree.
Key = 0 to 65,535
unique Keys
Long Value may not be NULL

- way faster than hash
- traverse Keys in order
- store/restore to string

ZIP: Chop2Tree_DLL-1.zip

 
 
'pb 5/9 (4/8 should be OK)
    'Two Chop Binary Tree (number Trie or Radix tree)
    'WORD/LONG ~ Key/Value store
    '   Key = 0 to 65535
    '   Key must be unique
    '   Value = any LONG except ZERO
    '       stored Value may NOT be NULL !!!
    '
    '   memory use: (50,000 Word/Long pairs: 6 bytes) = 4 bytes per pair (including tree structure)
    '       uses less memory than an arrays of same size
    '           (if Keys are in somewhat of a sequence)
    '
    '   Speed: faster than hash
    '       basically; it's a double Byte array lookup
    '           value = rootArr( childArr() )
    '
    '   the Keys aren't stored in the tree, only their path
    '       a Key is in tree if its path isn't NULL; we can still GetKey()
    '
    '   Store/Restore from string
    '
    '   - faster than hash
    '   - fast Set(), Remove()
    '   - don't have to worry about hash count
    '   - traverse tree in Key order
    '   - if Keys are in close sequence, tree acts as a compression algorithm
    '
    '   name: "Two Chop"
    '       we chop the WORD key into two Bytes
    '           one Byte stored in root node
    '           next Byte stored in root's child
    '           the whole tree is only two nodes deep
    '           it's a Byte array of Byte arrays
    '           BUT:
    '           the adjustable range concept allows us the keep the tree as small as possible
    '
    'NOTE: this code implements a new breakthrough innovation for Trie/Radix nodes.
    '   It uses an adjustable range child node structure in each node.
    '   Each node's children array adjust to the widest range necessary; node.low, node.high
    '   The child node array expands and contracts as Keys are added/deleted.
    '   This post serves ar prior-art to the concept and may NOT be patented without my ppermission.
    '   (don't want to loose the right to use my own code)
    '
    'free; use at your own risk
    '   may NOT be used for sale as a lone product without permission
 
 
Declare Function Chop2Tree_Alloc Lib "Chop2Tree_DLL-1.dll" () As Long
    'allocate new instance - return handle
 
Declare Sub Chop2Tree_Free Lib "Chop2Tree_DLL-1.dll" (ByVal tree As Long)
    'close tree - free all resources
 
Declare Sub Chop2Tree_Clear Lib "Chop2Tree_DLL-1.dll" (ByVal tree As Long)
    'delete all data
 
Declare Function Chop2Tree_Count Lib "Chop2Tree_DLL-1.dll" (ByVal tree As Long) As Long
    'get Key/Value count
 
Declare Sub Chop2Tree_Set Lib "Chop2Tree_DLL-1.dll" (ByVal tree As Long, ByVal key As Word, ByVal value As Long, ByVal replaceValue As Byte)
    'add Key/Value to tree
    '   if Key exist and replaceValue = True then old value replaced with new value
    'NOTE: Value can't be zero (zero Key OK)
 
Declare Function Chop2Tree_Get Lib "Chop2Tree_DLL-1.dll" (ByVal tree As Long, ByVal key As Word) As Long
    'get Key's Value
 
Declare Function Chop2Tree_FastGet Lib "Chop2Tree_DLL-1.dll" (ByVal tree As Long, ByVal key As Word) As Long
    'get Key's Value - no pointer are bounds checking
    '   warning!!!
    '       tree handle has to be good
    '       and Key has to be in tree
    '   otherwise, bad things will happen
 
Declare Function Chop2Tree_Contains Lib "Chop2Tree_DLL-1.dll" (ByVal tree As Long, ByVal key As Word) As Long
    'True/False if Key in tree
 
Declare Sub Chop2Tree_Remove Lib "Chop2Tree_DLL-1.dll" (ByVal tree As Long, ByVal key As Word)
    'remove Key/Value from tree
 
Declare Function Chop2Tree_Store Lib "Chop2Tree_DLL-1.dll" (ByVal tree As Long) As String
    'store tree in string (persist)
 
Declare Function Chop2Tree_StoreValidate Lib "Chop2Tree_DLL-1.dll" (ByRef storedTree As String) As Long
    'validate storage string
    '   string has front and back DWord validation hash cookies
 
Declare Sub Chop2Tree_Restore Lib "Chop2Tree_DLL-1.dll" (ByVal tree As Long, ByRef storedTree As String)
    'restore tree from string saved with Trie_Store()
    '   tree's current contents cleared
 
    '----------------------------------------------------------
    '
    '   Cursor Functions
    '
    '----------------------------------------------------------
 
Declare Function Chop2Cursor_Alloc Lib "Chop2Tree_DLL-1.dll" (ByVal tree As Long) As Long
    'allocate new cursor - return handle
 
Declare Sub Chop2Cursor_Free Lib "Chop2Tree_DLL-1.dll" (ByVal cursor As Long)
    'free cursor
 
Declare Function Chop2Cursor_GoFirst Lib "Chop2Tree_DLL-1.dll" (ByVal cursor As Long) As Long
    'move to first Key in tree
    '   True/False
 
Declare Function Chop2Cursor_GoNext Lib "Chop2Tree_DLL-1.dll" (ByVal cursor As Long) As Long
    'move to next Key in tree
    '   True/False
 
Declare Function Chop2Cursor_GoGetKey Lib "Chop2Tree_DLL-1.dll" (ByVal cursor As Long) As Word
    'get Key at current position
 
Declare Function Chop2Cursor_GoGetValue Lib "Chop2Tree_DLL-1.dll" (ByVal cursor As Long) As Long
    'get Value at current position
 
Declare Sub Chop2Cursor_GoSetValue Lib "Chop2Tree_DLL-1.dll" (ByVal cursor As Long, ByVal value As Long)
    'change Value at current position

[Guy Dombrowski]

Faster yet

Stanley,

For an index having keys from 0 to 65,535 I simply use one array x(65535) to store each record positions and then all you have to do to find the record is read the corresponding array.
This is the logic behind my SmartSort algorithm.

[Stanley Durham]

reply



.

[Guy Dombrowski]

Comments

Stanley,

Far from me to put down your nice code but memory is getting bigger all the time and if you want speed it is the way to go.
But if you have only a few keys to check and you want to save ram, a simple sequential read will do the job just as well with a lot less code. (meaning work)

[Stanley Durham]

Guy,
The powers that be don't want discussion in this section, so my reply is over here.

Chop Tree: comments