Announcement

Collapse

Forum Guidelines

This forum is for finished source code that is working properly. If you have questions about this or any other source code, please post it in one of the Discussion Forums, not here.
See more
See less

Two Chop Binary Tree / faster than hash

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Two Chop Binary Tree / faster than hash

    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

    Code:
     
     
    '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
    Last edited by Stanley Durham; 19 May 2009, 03:38 PM.
    stanthemanstan~gmail
    Dead Theory Walking
    Range Trie Tree
    HLib ~ Free Data Container Lib ~ Arrays, Lists, Stacks, Queues, Deques, Trees, Hashes

  • #2
    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.
    Old QB45 Programmer

    Comment


    • #3
      reply



      .
      stanthemanstan~gmail
      Dead Theory Walking
      Range Trie Tree
      HLib ~ Free Data Container Lib ~ Arrays, Lists, Stacks, Queues, Deques, Trees, Hashes

      Comment


      • #4
        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)
        Old QB45 Programmer

        Comment


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

          Chop Tree: comments
          stanthemanstan~gmail
          Dead Theory Walking
          Range Trie Tree
          HLib ~ Free Data Container Lib ~ Arrays, Lists, Stacks, Queues, Deques, Trees, Hashes

          Comment

          Working...
          X