Dictionary Vs Array tradeoffs

General
4

depends on how you’d use arrays to mimic dictionaries
if you have “key” and “value” then arrys need 2 matched arrays - one for keys and the other for values

that said here my little test method

Public Sub testSpeedDiff(param1 as Integer)
  
  Dim keys() As String
  Dim values() As String
  
  Dim dict As New dictionary
  
  // now into the arrays we put keys and value and the same set into the dict
  
  Redim Keys(param1)
  Redim values(param1)
  
  TextArea1.AppendText "Size = "  + Str(param1) + EndOfLine
  
  
  For i As Integer = 0 To param1 
    
    keys(i) = Str(i)
    values(i) = Str(i)
    
    dict.value(Str(i)) = Str(i)
  Next
  
  Dim randomKeys() As String
  Dim r As New random
  
  For i As Integer = 1 To 100
    Dim keyToLookup As Integer = r.InRange(0, param1)
    randomKeys.append str(keyToLookup)
  Next
  
  Dim startTime As Double
  Dim endTime As Double
  
  starttime = Microseconds
  For i As Integer = 0 To randomKeys.ubound
    Dim idx As Integer = keys.IndexOf( randomKeys(i) )
    Dim s As String = values(idx)
  Next
  endTime = Microseconds
  TextArea1.AppendText "arrays took " + Str(endTime-startTime) + " msec" + EndOfLine
  
  starttime = Microseconds
  For i As Integer = 0 To randomKeys.ubound
    Dim s As String = dict.Lookup( randomKeys(i), "" )
  Next
  endTime = Microseconds
  TextArea1.AppendText "dictionary took " + Str(endTime-startTime) + " msec" + EndOfLine
End Sub

Size = 10
arrays took 66.31799 msec
dictionary took 299.209 msec
Size = 100
arrays took 353.892 msec
dictionary took 192.686 msec
Size = 1000
arrays took 3204.535 msec
dictionary took 205.907 msec
Size = 10000
arrays took 38622.73 msec
dictionary took 277.168 msec
Size = 100000
arrays took 422759.3 msec
dictionary took 354.648 msec

dictionaries have a much “flatter” perforamce curve mostly unrelated to their size (it is but require some math to explain that I just dont feel like going into - look into the performance characteristics of red-black trees)

arrays are much more linear compared to their size

1 Like