NumericMap

[idle]

NumericMap supports Numerical keyed Maps
windows linux osx

When will this go native Fred?

Code: Select all

;NumericMap hack For structured Numeric keyed Maps 
;windows linux osx 
CompilerIf #PB_Compiler_Version > 602
  CompilerError "Attention - Check internal pb-function NumericMap!"
CompilerEndIf

NewMap dummy() 
ClearMap(dummy()) 
ResetMap(dummy())
FreeMap(dummy())

Import ""
  PB_NewNumericMap(ElementSize.i,*StructureMap,*Address,HashTabelSize.l);
  PB_FreeMap(*map)                                                      ;
  PB_ResetMap(*Map)                                                     ;
  PB_ClearMap(*Map)                                                     ;
  PB_MapSize(*Map)                                                      ;
  PB_PushMapPosition(*map)                                              ;
  PB_PopMapPosition(*map)                                               ;
  PB_NextMapElement(*Map)                                               ;
  PB_FindNumericMapElement(*Map,Key.i)                                  ;
  PB_AddNumericMapElement(*Map,Key.i)                                   ;
  PB_AddNumericMapElement2(*Map,Key.i,ElementCheck=#PB_Map_ElementCheck);
  PB_DeleteNumericMapElement2(*Map,Key.i)                               ;
  PB_DeleteNumericMapElement(*Map)                                      ;
  PB_CopyMap(*Map,*DestinationMap)                                      ;
  PB_CopyMap2(*Map,*DestinationMap,Clear.l)                             ;
EndImport

Macro NewNumericMap(pmap,HashTableSize,StructureType,IsStructure=0) 
  Global structadr=0
  EnableASM
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
    CompilerIf IsStructure 
      lea rax,[s_#StructureType]
      mov [v_structadr],rax
    CompilerEndIf 
  CompilerElse
    CompilerIf IsStructure  
      lea eax,[s_#StructureType]
      mov [v_structadr],eax
    CompilerEndIf 
  CompilerEndIf
  DisableASM
  PB_NewNumericMap(SizeOf(StructureType),structadr,@pmap,HashTableSize)
EndMacro   

Procedure NumericMapkey(pMap) 
  Protected ele,key   
  ele = PeekI(pMap)
  If ele 
    key = PeekI(ele+SizeOf(Integer)) 
  EndIf   
  ProcedureReturn key 
EndProcedure   

Procedure FreeNumericMap(mp) 
   !MOV    rcx,qword [p.v_mp]
   !CALL   PB_FreeMap
 EndProcedure   
 
 Procedure ClearNumericMap(mp) 
   !MOV    rcx,qword [p.v_mp]
   !CALL   PB_ClearMap
 EndProcedure  
 
 Procedure ResetNumericMap(mp) 
   !MOV    rcx,qword [p.v_mp]
   !CALL   PB_ResetMap
 EndProcedure   
  
CompilerIf #PB_Compiler_IsMainFile 
  
  ;Note you need to use a structured element pointer even for native types 
  
  Structure foo
    List controls.i()
    i.i 
    s.s 
  EndStructure   
  
  
  Procedure test() 
    Protected mp, *el.foo 
    NewNumericMap(mp,512,foo,#PB_Structure) ;create the map and pass map variable, number of elements, the name of the structure , if the structure contains a list map or array use the flag #PB_Structure  
    
    *el = PB_AddNumericMapElement(mp,123)   
    
    AddElement(*el\controls())
    *el\controls() = 111
    AddElement(*el\controls())
    *el\controls() = 112
    *el\i = 123
    *el\s = "Hello" 
    ;
    *el = PB_AddNumericMapElement2(mp,345)
    AddElement(*el\controls())
    *el\controls() = 113
    AddElement(*el\controls())
    *el\controls() = 114
    
    *el\i = 345
    *el\s = "World"
    ;
    *el = PB_FindNumericMapElement(mp,123)
    ForEach *el\controls() 
      Debug "list Controls " + *el\controls() 
    Next   
    Debug "integer " + *el\i
    Debug "string "  + *el\s 
    
    *el = PB_FindNumericMapElement(mp,345)
    ForEach *el\controls() 
      Debug "list Controls " + *el\controls() 
    Next   
    Debug "integer " + *el\i
    Debug "string "  + *el\s 
    
    Debug "+++++++++++"
    Debug "walk the map"
    Debug "+++++++++++"
    
    ResetNumericmap(mp) 
    
    Repeat 
      *el = PB_NextMapElement(mp) 
      If *el  
        Debug "mapkey " + NumericMapkey(mp) 
        ForEach *el\controls() 
          Debug "list Controls " + *el\controls() 
        Next   
        Debug "integer " + *el\i
        Debug "string "  + *el\s 
      EndIf   
    Until *el=0   
    
    Debug "++++++++++++++"
    Debug "clear map" 
    ClearNumericMap(mp);
    ResetNumericMap(mp) 
    
    Repeat 
      *el = PB_NextMapElement(mp) 
      If *el  
        Debug "mapkey " + NumericMapkey(mp) 
        ForEach *el\controls() 
          Debug "list Controls " + *el\controls() 
        Next   
        Debug "integer " + *el\i
        Debug "string "  + *el\s 
      EndIf   
    Until *el=0   
    Debug "should be nothing" 
    
    FreeNumericmap(mp)
            
    Debug "++++++++++++"
    Debug "test with a native type via pointer"  
    Protected *elf.float   
    NewNumericMap(mp,512,float) ;create the map and pass map variable, number of elements, the name of the structure 
    *elf = PB_AddNumericMapElement(mp,123)
    *elf\f = #PI 
    *elf = PB_AddNumericMapElement(mp,345)
    *elf\f = 2*#PI 
    *elf = PB_FindNumericMapElement(mp,123)
    Debug *elf\f 
    
    PB_DeleteNumericMapElement2(mp,345) 
    
    *elf = PB_FindNumericMapElement(mp,345)
    If *elf 
      Debug *elf\f 
    Else 
      Debug "deleted key 345"
    EndIf 
    
    Debug NumericMapkey(mp)
    
    *elf = PB_FindNumericMapElement(mp,123)
    If *elf 
      Debug *elf\f 
    EndIf 
    
    Debug NumericMapkey(mp)
    
    FreeNumericmap(mp)
            
    MessageRequester("test","ok")
    
  EndProcedure 
  
  test() 
  
CompilerEndIf 

[Fred]

Messing with internal code isn't really a trick and tips as it can be broken anytime. If it's not released, it's because it's ready for

[chi]

Messing with internal code isn't really a trick and tips as it can be broken anytime. If it's not released, it's because it's ready for

So what's the problem with numeric maps? They have been secretly implemented for over 4 years into the Map library and it seems they work just fine with this hack...

[mk-soft]

Everything that is internal can change. So you have to check this with a new version of Purebasic.

Code: Select all

CompilerIf #PB_Compiler_Version > 570
  CompilerError "Attention - Check internal pb-function NumericMap!"
CompilerEndIf

[idle]

Messing with internal code isn't really a trick and tips as it can be broken anytime. If it's not released, it's because it's ready for

Note to self, don't unwrap Fred's xmas presents

[idle]

Everything that is internal can change. So you have to check this with a new version of Purebasic.

Code: Select all

CompilerIf #PB_Compiler_Version > 570
  CompilerError "Attention - Check internal pb-function NumericMap!"
CompilerEndIf

Thank added it

[chi]

Is there a reason behind not importing PB_NumericMapKey(*Map)?

[skywalk]

Haha, great find.
I think idle proved there is a Santa!

[idle]

Is there a reason behind not importing PB_NumericMapKey(*Map)?

It isn't in the header and I couldn't get it to work with PB_MapKey(PB_Map *Map, int PreviousPosition); So I just did it manually.

[idle]

Is there a reason behind not importing PB_NumericMapKey(*Map)?

It isn't in the header and I couldn't get it to work with PB_MapKey(PB_Map *Map, int PreviousPosition); So I just did it manually.

[Tenaja]

NumericMap supports Numerical keyed Maps
windows linux osx

Code: Select all

;NumericMap hack for structured Numeric keyed Maps 
;windows linux osx 
CompilerIf #PB_Compiler_Version > 571
  CompilerError "Attention - Check internal pb-function NumericMap!"
CompilerEndIf

Import ""
  PB_NewNumericMap(ElementSize.i,*StructureMap,*Address,HashTabelSize.l);
  PB_FreeMap(*Map)                                                      ;
  PB_ResetMap(*Map)                                                     ;
  PB_ClearMap(*Map)                                                     ;
  PB_MapSize(*Map)                                                      ;
  PB_PushMapPosition(*map)                                              ;
  PB_PopMapPosition(*map)                                               ;
  PB_NextMapElement(*Map)                                               ;
  PB_FindNumericMapElement(*Map,Key.i)                                  ;
  PB_AddNumericMapElement(*Map,Key.i)                                   ;
  PB_AddNumericMapElement2(*Map,Key.i,ElementCheck=#PB_Map_ElementCheck);
  PB_DeleteNumericMapElement2(*Map,Key.i)                               ;
  PB_DeleteNumericMapElement(*Map)                                      ;
  PB_CopyMap(*Map,*DestinationMap)                                      ;
  PB_CopyMap2(*Map,*DestinationMap,Clear.l)                             ;
EndImport

Macro NewNumericMap(pmap,HashTableSize,StructureType,IsStructure=0) 
  Global structadr=0
  EnableASM
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
    CompilerIf IsStructure 
      lea rax,[s_#StructureType]
      mov [v_structadr],rax
    CompilerEndIf 
  CompilerElse
    CompilerIf IsStructure  
      lea eax,[s_#StructureType]
      mov [v_structadr],eax
    CompilerEndIf 
  CompilerEndIf
  DisableASM
  PB_NewNumericMap(SizeOf(StructureType),structadr,@pmap,HashTableSize)
EndMacro   

Procedure NumericMapkey(pMap) 
  Protected ele,key   
  ele = PeekI(pMap)
  If ele 
    key = PeekI(ele+SizeOf(Integer)) 
  EndIf   
  ProcedureReturn key 
EndProcedure   

CompilerIf #PB_Compiler_IsMainFile 
  
  ;Note you need to use a structured element pointer even for native types 
  
  Structure foo
    List controls.i()
    i.i 
    s.s 
  EndStructure   
  
  
  Procedure test() 
    Protected mp, *el.foo 
    NewNumericMap(mp,512,foo,#PB_Structure) ;create the map and pass map variable, number of elements, the name of the structure  
    
    *el = PB_AddNumericMapElement(mp,123)   
    
    AddElement(*el\controls())
    *el\controls() = 111
    AddElement(*el\controls())
    *el\controls() = 112
    *el\i = 123
    *el\s = "Hello" 
    ;
    *el = PB_AddNumericMapElement2(mp,345)
    AddElement(*el\controls())
    *el\controls() = 113
    AddElement(*el\controls())
    *el\controls() = 114
    
    *el\i = 345
    *el\s = "World"
    ;
    *el = PB_FindNumericMapElement(mp,123)
    ForEach *el\controls() 
      Debug "list Controls " + *el\controls() 
    Next   
    Debug "integer " + *el\i
    Debug "string "  + *el\s 
    
    *el = PB_FindNumericMapElement(mp,345)
    ForEach *el\controls() 
      Debug "list Controls " + *el\controls() 
    Next   
    Debug "integer " + *el\i
    Debug "string "  + *el\s 
    
    Debug "+++++++++++"
    Debug "walk the map"
    Debug "+++++++++++"
    
    PB_ResetMap(mp) 
    Repeat 
      *el = PB_NextMapElement(mp) 
      If *el  
        Debug "mapkey " + NumericMapkey(mp) 
        ForEach *el\controls() 
          Debug "list Controls " + *el\controls() 
        Next   
        Debug "integer " + *el\i
        Debug "string "  + *el\s 
      EndIf   
    Until *el=0   
    
    Debug "++++++++++++++"
    Debug "clear map" 
    PB_ClearMap(mp);
    PB_ResetMap(mp) 
    Repeat 
      *el = PB_NextMapElement(mp) 
      If *el  
        Debug "mapkey " + NumericMapkey(mp) 
        ForEach *el\controls() 
          Debug "list Controls " + *el\controls() 
        Next   
        Debug "integer " + *el\i
        Debug "string "  + *el\s 
      EndIf   
    Until *el=0   
    Debug "should be nothing" 
    
    PB_FreeMap(mp)
    
    Debug "++++++++++++"
    Debug "test with a native type via pointer"  
    Protected *elf.float   
    NewNumericMap(mp,512,float) ;create the map and pass map variable, number of elements, the name of the structure 
    *elf = PB_AddNumericMapElement(mp,123)
    *elf\f = #PI 
    *elf = PB_AddNumericMapElement(mp,345)
    *elf\f = 2*#PI 
    *elf = PB_FindNumericMapElement(mp,123)
    Debug *elf\f 
    
    PB_DeleteNumericMapElement2(mp,345) 
    
    *elf = PB_FindNumericMapElement(mp,345)
    If *elf 
      Debug *elf\f 
    Else 
      Debug "deleted key 345"
    EndIf 
    
    Debug NumericMapkey(mp)
    
    *elf = PB_FindNumericMapElement(mp,123)
    If *elf 
      Debug *elf\f 
    EndIf 
    
    Debug NumericMapkey(mp)
    
    PB_FreeMap(mp) 
    
  EndProcedure 
  
  test() 
  
CompilerEndIf 

I'd this significantly different than the trie from a few years ago?
viewtopic.php?f=13&t=58708

[idle]

@Tenaja

A trie is quite different, probably easier to read up on the differences than have me try to explain, ...pages later

https://en.wikipedia.org/wiki/Trie
https://en.wikipedia.org/wiki/Hash_table

[wilbert]

I'd this significantly different than the trie from a few years ago?

Array, Map or Trie

Imagine you have 1000 different cards with 4 digit numbers (like 0013, 3653, 8984, 1453) and a name on them.

Array
If you use the numbers as an index for an array to store the names, the array would need to have a size of 10,000 items.
So only 10% of the array would be used. But it would be very fast since you can immediately pick the right item.
If the numbers are bigger like with memory pointers, using the pointer as an index for an array isn't working anymore.

Map
If you throw your 1000 cards into 100 different buckets and you know in what bucket to search, you only have to search through a few of them which is still fast and you don't need a lot of space.
If you would throw all cards into the same bucket, you still have to go through all your cards which makes no sense. That's why the numbers (map keys) are 'hashed'. Trying to evenly spread your cards over all buckets. The more buckets you have, the faster a map will be but it will also take up more space.

Trie
A trie works more or less by letting each digit refer to the next one.
Imagine index cards with the numbers 0-9 on each card and a reference for each number to another index card.

If you take for example 8984, the first index card will have a reference at number '8' referring to a second index card.
This second card will have a reference at number '9' referring to a third index card.
This third card will have a reference at number '8' referring to a fourth index card.
This fourth card will have a reference at number '4' to a string with the name you want to associate with the number 8984.

So with a trie, you make more memory jumps to get each reference but each time you know where to go so you don't have to search through a bucket.
This takes up more space in memory compared to a map since each index card needs to have room for multiple references but if you have a map with few buckets and a lot of items, a trie can be quite a bit faster compared to a map.

[box_80]

I been wondering about the different myself. I been getting a lot of mixed answers on websites about performance. A lot depends on the programs exact needs. The exact implementation of the data structure. I have very little experience with this stuff myself.

Here someone testing in C
http://loup-vaillant.fr/projects/string ... /benchmark

[wilbert]

A lot depends on the programs exact needs. The exact implementation of the data structure.

You couldn't be more right

It's always best to first think about what you exactly need.
And the implementation is also important. As far as I can tell from the benchmarks you are referring to, the code for the trie handles 2 bits at a time.
If you would handle 4 or 5 bits at a time, it will be a lot faster but also consume more memory.