List vs Map Benchmark

[minimy]

This is a simple benchmark to know where and when is better use Map or List.

Code: Select all

Structure Item
  id.i
  value.i
EndStructure
NewList myList.Item()
NewMap myMap.Item()
Define startTime, endTime, i, j, searchId, foundValue
Define listTime, mapTime, listSearchTime, mapSearchTime
Define numElements = 100000
Define numSearches = 10000

; Benchmark con List
startTime = ElapsedMilliseconds()
For i = 1 To numElements
  AddElement(myList())
  myList()\id = i
  myList()\value = i * 2
Next
ForEach myList()
  i = myList()\value
Next
endTime = ElapsedMilliseconds()
listTime = endTime - startTime

; Benchmark con Map
startTime = ElapsedMilliseconds()

For i = 1 To numElements
  AddMapElement(myMap(), Str(i))
  myMap()\id = i
  myMap()\value = i * 2
Next
ForEach myMap()
  i = myMap()\value
Next
endTime = ElapsedMilliseconds()
mapTime = endTime - startTime

; Búsquedas aleatorias en List
startTime = ElapsedMilliseconds()
For j = 1 To numSearches
  searchId = Random(numElements) + 1
  ResetList(myList())
  While NextElement(myList())
    If myList()\id = searchId
      foundValue = myList()\value
      Break
    EndIf
  Wend
Next
endTime = ElapsedMilliseconds()
listSearchTime = endTime - startTime

; Búsquedas aleatorias en Map 
startTime = ElapsedMilliseconds()
For j = 1 To numSearches
  searchId = Random(numElements) + 1
  If FindMapElement(myMap(), Str(searchId))
    foundValue = myMap()\value
  EndIf
Next

endTime = ElapsedMilliseconds()
mapSearchTime = endTime - startTime
MessageRequester("Resultados Benchmark List vs Map", 
                 "Insert and tour ("+Str(numElements)+" elementos):" + #CRLF$ +
                 "  List: " + Str(listTime) + " ms" + #CRLF$ +
                 "  Map: " + Str(mapTime) + " ms" + #CRLF$ + #CRLF$ +
                 "Random search (" + Str(numSearches) + " intentos):" + #CRLF$ +
                 "  List: " + Str(listSearchTime) + " ms" + #CRLF$ +
                 "  Map: " + Str(mapSearchTime) + " ms")

[idle]

A map search is O(1) and degrades toward O(n) fully loaded.
A list is O(n)
That should be enough to tell you which one to use.

An issue arises if you haven't sized the map to the expected load and it's performance will degrade. PB map defaults to 512 elements. So that's not going to work well for 100k items as it causes multiple resizes and leads to multiple probes.

[minimy]

Thanks idle for the information. I just put this to help noobs members.