Maps 101: All you need to know about them!

[TheDcoder]

Phew.... It took more than an hour to write Questions #3 & #4

I wonder what maps are capable of... gotta finish my project fast and start playing with them

 

Enjoy, TD

[guinness]

 

Q #4. Are Maps faster than Arrays?
A. You need to understand that Maps have different purpose than Arrays. Maps are designed to store data dynamically (like storing information for certain controlIDs of GUI) and Arrays are designed to store data in a order (for instance, Storing every character of a string in an element for easy access). If you still want to know then if Maps are faster, then the answer is maybe... Maps are *supposed* (I am not sure ) to be faster in addition of elements (while Arrays are painfully slow while adding or removing elements).

I guess you're talking about data retrieval? I would probably create a benchmark test, though in general arrays of normally faster due to be accessed in constant time, due to array[2] being ptr + 2 * sizeof(type). Of course I speak in general and not AutoIt specific. Anyway my point is test before making claims.

[TheDcoder]

@guinness I was more focusing on data addition rather than data retrieval, I also tried to do a benchmark test on data addition here, though I was not able to complete it successfully as the test was somewhat unfair... I will try to benchmark on data retrieval now.

 

TD

[Kealper]

The map data type is available in many popular programming languages, and has certain uses that traditional arrays aren't quite as suited-for, especially in an interpreted language such as AutoIt.

You can emulate maps using traditional arrays without too much hassle, but in interpreted languages, performance can suffer quite a bit.

Comparing the performance of arrays to maps is a bit of an apples-to-oranges comparison, as a traditional array can't do things maps can do. Because of this, I've written a little benchmark that runs on the latest beta version of AutoIt (3.3.15.0 at the time of writing). It uses a 2d array to create a case-sensitive key/value store. If you add data to a key that does not exist, that key is created with the data it was supposed to be assigned. Basically, it's using 2d arrays to create fakes of the new native map type.

Native maps can usually handle enormous amounts of key/value pairs and still be very fast at modifying or reading the data in them. AutoIt's new maps are no exception, either!

 

CLARIFICATION: Please understand that this benchmark is NOT comparing the performance of arrays to the performance of maps.
The two serve different purposes, and if you put arrays versus maps in a fair benchmark, arrays will be faster. This is true for pretty much any programming language.
This benchmark is comparing the methods available for doing a native, dynamically-sized, in-memory key/value store. In the current stable release of AutoIt, the only way to do this without relying on external COM objects (Scripting.Dictionary) is to use a dynamically-sized two-dimensional array. (Or two one-dimensional dynamically-sized arrays, but we'll not get into that as there's not really a good reason to do that over a two-dimensional one.) In the current beta of AutoIt, the map type allows for exactly that, without all of the boilerplate code needed to implement them, as well as a huge speed increase to them since the heavy lifting is being done internally in the interpreter as opposed to being done in AutoIt. One of the key features of this data type is that the amount of things it can store is not a fixed size. This means the more stuff you want to add, the bigger it will grow. The more things you delete from it, the smaller it shrinks. If you need to iterate over a map, it won't have to waste time running through, for example, 9,975 blank entries just to read the 25 populated entries like you would with a 10,000-element fixed-size array.
For those saying that this benchmark is not fair to arrays and that there's a more efficient way to do it so they end up doing much better in the benchmark: I know, this isn't meant to be "arrays vs. maps", it's meant to be "fake maps vs. native maps". There's also some optimization that can be done with my FakeMap code, because ReDim is actually pretty slow, but adding that would make the example code harder to read while the end result would still be the same.

 

The benchmark creates a specified number of elements randomly, and sets their values to a random number as well. It then creates one last element and reads that last element's data and prints it into the console. It also prints out the times that each step took, in milliseconds.

So, here is the result of these basic benchmarks:

1000+1 elements:

Fake map population time (1000 random elements): 1251.122ms
Fake map new element 1001 time: 2.022ms
Read data: Hello, World!
Fake map read element 1001 time: 1.12ms
Real map population time (1000 random elements): 2.489ms
Real map new element 1001 time: 0.01ms
Read data: Hello, World!
Real map read element 1001 time: 0.01ms

So from here, you can see that with only 1000 elements, the fake map took over 1.2 seconds to create 1000 new elements, 2ms to add the 1001st element, and then another 1ms to read that 1001st element. The native map only took about 2.5ms to create the first 1000 elements, and 0.1ms to create and read the 1001st. Wow!
Here's that same benchmark, but instead of 1,000, we'll bump it up to 10,000!

Fake map population time (10000 random elements): 123555.641ms
Fake map new element 10001 time: 21.328ms
Read data: Hello, World!
Fake map read element 10001 time: 11.637ms
Real map population time (10000 random elements): 27.36ms
Real map new element 10001 time: 0.014ms
Read data: Hello, World!
Real map read element 10001 time: 0.014ms

Two minutes for 10,000 new elements in the fake map? Yikes! As you can also see, although the fake map gets exponentially slower with each order of magnitude we go up, the native maps stay fairly consistent still, even at 10,000. At this scale, the amount of time calls to Random() take starts to show.
But what if we go further? Let's say... 1,000,000 elements. For obvious reasons, I won't run the fake map code with this many elements, otherwise we'd be here until this time next year waiting for the results... But here is what happens when we have a 1-million-element map, and add one more on to it, then read it back:

Real map population time (1000000 random elements): 24357.752ms
Real map new element 1000001 time: 0.063ms
Read data: Hello, World!
Real map read element 1000001 time: 0.029ms

As we can see, the two million calls made to Random() certainly did a number on that run time, weighing in at just over 24 seconds. We can safely assume that most of that 24 seconds was spent just generating random numbers because... Adding another element on top of that, then reading it back, is still incredibly fast, given how much data there is, at around 60 microseconds (that's 1/1000th of one millisecond!) to add a new value, and around 30 microseconds to read it back. Even more wow!

The code used for this back-of-the-napkin basic benchmark:

expandcollapse popup

Global $FakeMap = MapCreate()
Global $Map[]
Global $t
Global $TestSize = 1000
 
#Region Fake map benchmarking
$t = TimerInit()
For $i = 1 To $TestSize
    MapSet($FakeMap, Random(1, 1000000, 1), Random(1, 1000000, 1))
Next
ConsoleWrite("Fake map population time (" & $TestSize & " random elements): " & Round(TimerDiff($t), 3) & "ms" & @CRLF)
 
$t = TimerInit()
MapSet($FakeMap, "asdf", "Hello, World!")
ConsoleWrite("Fake map new element " & ($TestSize + 1) & " time: " & Round(TimerDiff($t), 3) & "ms" & @CRLF)
 
$t = TimerInit()
ConsoleWrite("Read data: " & MapRead($FakeMap, "asdf") & @CRLF)
ConsoleWrite("Fake map read element " & ($TestSize + 1) & " time: " & Round(TimerDiff($t), 3) & "ms" & @CRLF)
#EndRegion
 
#Region Real/native map benchmarking
$t = TimerInit()
For $i = 1 To $TestSize
    $Map[Random(1, 1000000, 1)] = Random(1, 1000000, 1)
Next
ConsoleWrite("Real map population time (" & $TestSize & " random elements): " & Round(TimerDiff($t), 3) & "ms" & @CRLF)
 
$t = TimerInit()
$Map["asdf"] = "Hello, World!"
ConsoleWrite("Real map new element " & ($TestSize + 1) & " time: " & Round(TimerDiff($t), 3) & "ms" & @CRLF)
 
$t = TimerInit()
ConsoleWrite("Read data: " & $Map["asdf"] & @CRLF)
ConsoleWrite("Real map read element " & ($TestSize + 1) & " time: " & Round(TimerDiff($t), 3) & "ms" & @CRLF)
#EndRegion
 
#Region Wrapper functions to emulate map support for this test
Func MapCreate()
    Local $aMap[1][2]
    $aMap[0][0] = 0
    Return $aMap
EndFunc
 
Func MapRead($aMap, $sKey)
    For $i = 1 To UBound($aMap, 1) - 1
        If $aMap[$i][0] == $sKey Then Return $aMap[$i][1]
    Next
    Return SetError(1, 0, "")
EndFunc
 
Func MapSet(ByRef $aMap, $sKey, $vVal)
    For $i = 1 To UBound($aMap, 1) - 1
        If $aMap[$i][0] == $sKey Then
            $aMap[$i][1] = $vVal
            Return
        EndIf
    Next
    Local $iSize = UBound($aMap, 1)
    ReDim $aMap[$iSize + 1][2]
    $aMap[$iSize][0] = $sKey
    $aMap[$iSize][1] = $vVal
    $aMap[0][0] = $iSize
EndFunc
#EndRegion

 

Edited December 10, 2015 by Kealper
Clarifying the purpose of this benchmark

[TheDcoder]

@Kealper Wow! Thanks was a nice piece of work ! I will add it to Q#4

 

P.S Please correct your code tags

[Kealper]

I guess you must have read the reply as soon as I had posted it, I changed them over to regular ol'

code tags as soon as I had posted it and seen that it didn't like [autoit] ones

EDIT: We're just not going to talk about why I edited this.

Edited November 22, 2015 by Kealper
Formatting... :|

[TheDcoder]

@Kealper I get notifications in real time

[argumentum]

But what if we go further? Let's say... 1,000,000 elements. For obvious reasons, I won't run the fake map code with this many elements, otherwise we'd be here until this time next year waiting for the results... But here is what happens when we have a 1-million-element map, and add one more on to it, then read it back:

Real map population time (1000000 random elements): 24357.752ms
Real map new element 1000001 time: 0.063ms
Read data: Hello, World!
Real map read element 1000001 time: 0.029ms

As we can see, the two million calls made to Random() certainly did a number on that run time, weighing in at just over 24 seconds.

nice thing these maps. Will come in handy.
As far as the fake maps ... I changed your code

expandcollapse popup

Global $FakeMap = MapCreate()
Global $Map[]
Global $t
Global $TestSize = 1000000

#comments-start
#Region Fake map benchmarking
$t = TimerInit()
For $i = 1 To $TestSize
    MapSet($FakeMap, Random(1, 1000000, 1), Random(1, 1000000, 1))
Next
ConsoleWrite("Fake map population time (" & $TestSize & " random elements): " & Round(TimerDiff($t), 3) & "ms" & @CRLF)

$t = TimerInit()
MapSet($FakeMap, "asdf", "Hello, World!")
ConsoleWrite("Fake map new element " & ($TestSize + 1) & " time: " & Round(TimerDiff($t), 3) & "ms" & @CRLF)

$t = TimerInit()
ConsoleWrite("Read data: " & MapRead($FakeMap, "asdf") & @CRLF)
ConsoleWrite("Fake map read element " & ($TestSize + 1) & " time: " & Round(TimerDiff($t), 3) & "ms" & @CRLF)
#EndRegion
#comments-end

#Region Real/native map benchmarking
$t = TimerInit()
For $i = 1 To $TestSize
    $Map[Random(1, 1000000, 1)] = Random(1, 1000000, 1)
Next
ConsoleWrite("Real map population time (" & $TestSize & " random elements): " & Round(TimerDiff($t), 3) & "ms" & @CRLF)

$t = TimerInit()
$Map["asdf"] = "Hello, World!"
ConsoleWrite("Real map new element " & ($TestSize + 1) & " time: " & Round(TimerDiff($t), 3) & "ms" & @CRLF)

$t = TimerInit()
ConsoleWrite("Read data: " & $Map["asdf"] & @CRLF)
ConsoleWrite("Real map read element " & ($TestSize + 1) & " time: " & Round(TimerDiff($t), 3) & "ms" & @CRLF)
#EndRegion

#Region Wrapper functions to emulate map support for this test
Func MapCreate()
    Local $aMap[1][2]
    $aMap[0][0] = 0
    Return $aMap
EndFunc

Func MapRead($aMap, $sKey)
    For $i = 1 To UBound($aMap, 1) - 1
        If $aMap[$i][0] == $sKey Then Return $aMap[$i][1]
    Next
    Return SetError(1, 0, "")
EndFunc

Func MapSet(ByRef $aMap, $sKey, $vVal)
    For $i = 1 To UBound($aMap, 1) - 1
        If $aMap[$i][0] == $sKey Then
            $aMap[$i][1] = $vVal
            Return
        EndIf
    Next
    Local $iSize = UBound($aMap, 1)
    ReDim $aMap[$iSize + 1][2]
    $aMap[$iSize][0] = $sKey
    $aMap[$iSize][1] = $vVal
    $aMap[0][0] = $iSize
EndFunc
#EndRegion

#Region ArrayKnownMaxSize
$t = TimerInit()
Dim $FakeMap[$TestSize+1][2]
$FakeMap[0][0] = 0
For $n = 1 To $TestSize ; MapSet : $TestSize times
    $FakeMap[0][0] = $FakeMap[0][0] + 1 ; just to fake unknown next entry
    $FakeMap[ $FakeMap[0][0] ][ 0 ] = Random(1, 1000000, 1)
    $FakeMap[ $FakeMap[0][0] ][ 1 ] = Random(1, 1000000, 1)
Next
ConsoleWrite("Array population time (" & $TestSize & " random elements): " & Round(TimerDiff($t), 3) & "ms" & @CRLF)
#EndRegion ArrayKnownMaxSize

#Region # try Assign & Eval
$t = TimerInit()
For $n = 1 To $TestSize ; MapSet : $TestSize times
    Assign("MyMapThing_" & Random(1, 1000000, 1) & "_0", Random(1, 1000000, 1), 2)
Next
ConsoleWrite("Assign population time (" & $TestSize & " random elements): " & Round(TimerDiff($t), 3) & "ms" & @CRLF)
$t = TimerInit()
Assign("MyMapThing_" & "asdf" & "_0", "Hello, World!", 2)
ConsoleWrite("Assign new element " & ($TestSize + 1) & " time: " & Round(TimerDiff($t), 3) & "ms" & @CRLF)
$t = TimerInit()
ConsoleWrite("Assign Read data: " & Eval("MyMapThing_" & "asdf"&"_0") & @CRLF)
ConsoleWrite("Assign read element " & ($TestSize + 1) & " time: " & Round(TimerDiff($t), 3) & "ms" & @CRLF)

#EndRegion # try Assign & Eval

 to show other aspects and I tried the 1,000,000 entries and returned:

Real map population time (1000000 random elements): 24247.229ms
Real map new element 1000001 time: 0.06ms
Read data: Hello, World!
Real map read element 1000001 time: 0.007ms
Array population time (1000000 random elements): 3590.172ms
Assign population time (1000000 random elements): 5589.787ms
Assign new element 1000001 time: 0.018ms
Assign Read data: Hello, World!
Assign read element 1000001 time: 0.012ms

so, Arrays are arrays and maps are maps but you did not code the array in a favorable way for the arrays.
And the assign thing is also nice. Again, variables are variables and maps are maps.

I'm looking into these new things myself and sharing your benchmark was good for me, thanks.

[Guest]

Why Maps > Array ?

Maps are just like arrays, instead they use "keys" to access elements inside them... A key can be either a string or an integer (Other datatypes work too but this fact is not documented so better stick to the official once ). Although Integers don't represent the order of elements in a map unlike in an array...

 From what I know this is the only reason.

But you can get this advantage with array in this way:

#AutoIt3Wrapper_Run_Au3Stripper=y
#Au3Stripper_Parameters=/RM /PE
#include <Array.au3>

Global Const $g_aArray_max = 3

Global Const $g_aArray_ix_FirstName = 0, $g_aArray_ix_LastName = 1, $g_aArray_ix_Age = 2

Global $g_aArray[1][$g_aArray_max] = [[0]]


; Add person:
$g_aArray[0][0] += 1
ReDim $g_aArray[$g_aArray[0][0]+1][$g_aArray_max]
    ; Set first name:
    $g_aArray[$g_aArray[0][0]][$g_aArray_ix_FirstName] = 'abc'
    ; Set last name:
    $g_aArray[$g_aArray[0][0]][$g_aArray_ix_LastName] = 'efg'
    ; Set age:
    $g_aArray[$g_aArray[0][0]][$g_aArray_ix_Age] = 24

 

And more important is that after you compile it this is how it looks:

Global $2z[1][3] = [[0]]
$2z[0][0] += 1
ReDim $2z[$2z[0][0] + 1][3]
$2z[$2z[0][0]][0] = 'abc'
$2z[$2z[0][0]][1] = 'efg'
$2z[$2z[0][0]][2] = 24

 

For Autoit this code is more simpler and should run faster in theory.

With maps - from my understanding these words (of the variables in the Map... in this case: "age" , "FirstName", "LastName" ) are remain. And words heavier then numbers so it should  run slowly or at least take more memory in theory.

 

 

Edited November 30, 2015 by Guest

[iamtheky]

@gil900

You would need to ensure that the new key being entered is unique (to mimic maps functionality), the penalty for that check may or may not be more than that of the key being a string rather than integer.

[guinness]

The benchmarks that have been presented here for arrays vs maps, is simply not a fair comparison.

[Guest]

You would need to ensure that the new key being entered is unique

I can understand when it can be confusing - when you have lots of keys and you write it with no order like this:

Global Const $g_Array_key_abc = 5, $g_Array_key_efg = 3,$g_Array_key_hik = 2, $g_Array_key_aex = 4, $g_Array_key_rgs = 1

 

Or like this:

Global Const $g_Array_key_abc = 5
; lots of code
; ...
; ...
; end

Global Const $g_Array_key_efg = 3

; lots of code
; ...
; ...
; end

Global Const $g_Array_key_hik = 2

; lots of code
; ...
; ...
; end

Global Const $g_Array_key_aex = 4

; lots of code
; ...
; ...
; end

 

Then what you say that need to be done is not easy..  Much easier to make a mistake when you make changes

But if you write it in order(by numbers)  and maintains that order and you write it all in the same area - for example like this:

Global Const $g_Array_key_abc = 1, $g_Array_key_efg = 2,$g_Array_key_hik = 3, $g_Array_key_aex = 4, $g_Array_key_rgs = 5

Then this is simple and very very hard to make mistake. So you almost don't feel it and probably get much faster code (Because the interpreter does not need to check for long address each time it need to read data...)

Edited November 30, 2015 by Guest

[iamtheky]

One more time: at what point do you ensure that there are no duplicate keys?

Global Const $g_Array_key_abc = 1, $g_Array_key_efg = 1,$g_Array_key_hik = 1, $g_Array_key_aex = 1, $g_Array_key_rgs = 1

msgbox(0 , '' , $g_Array_key_abc & @LF & $g_Array_key_efg & @LF & $g_Array_key_hik & @LF & $g_Array_key_aex & @LF & $g_Array_key_rgs)

 

Without any other rules your result is just a 2D array that you named map

 

 

Edited November 29, 2015 by boththose

[Guest]

One more time: at what point do you ensure that there are no duplicate keys?

Global Const $g_Array_key_abc = 1, $g_Array_key_efg = 1,$g_Array_key_hik = 1, $g_Array_key_aex = 1, $g_Array_key_rgs = 1

msgbox(0 , '' , $g_Array_key_abc & @LF & $g_Array_key_efg & @LF & $g_Array_key_hik & @LF & $g_Array_key_aex & @LF & $g_Array_key_rgs)

 

Without any other rules your result is just a 2D array that you named map

 

 

 

When I read carefully my code? (This is my answer)
I'm not sure I understand your point ..

You ensure this when you do the most basic thing - write code correctly.
The programmer's job is to write code without errors that working effectively as possible. and It's quite clear to me that I ensure that with my eyes ..
My rule here is simple - to write code without errors (as in your example in this case).

 

From what I understand, this is good if you have difficulty working with arrays or if you do not need to write code that runs fast as possible and/or in your case is more important that the code would be easier to understand by your team.
 

This means that there are good reasons of why the Map[] is good but I say it is very important to decide what to choose on the basis of the need and requirements..

 Again, maybe I did not understand what exactly are you talking about. In this case, I'm sorry.

EDIT:
I do not claim that Array is Map. I just say that Array is better if you know what you are doing. If not then Map is may be much better choice.

Edited November 29, 2015 by Guest

[iamtheky]

I am saying it is not a reasonable comparison, as the map datatype has additional controls.  And if your only benefit to the array is speed, you made a wrong turn at AutoIt.   I just say that if you know what you are doing, you wont grab an array when you need a map.

[Guest]

I am saying it is not a reasonable comparison, as the map datatype has additional controls.

I understand what you're saying later. I agree

 

And if your only benefit to the array is speed, you made a wrong turn at AutoIt.

You're right. What I am saying now does not belong here so I put it in spoiler.

I know that. I'm considering very very seriously to learn something new.
But speed is not the only thing that matters .. There is something in Autoit which makes it very worthwhile. And it's how easy it is...
 

Besides "Speed" factor there is "Easy" factor and in this case the "Easy" factor is so high that I believes that in most cases this factor compensating for disadvantage of the "Speed"... (I hope that you get it..)
 

My conclusion is to combine Autoit with other programming language that have the speed advantage.
For example do the most stuff in Autoit and anything else that requires speed - write as external dll ..

Edited November 30, 2015 by Guest

[TheDcoder]

@gil900 Arrays are arrays & Maps are maps, each of them have their own advantages and disadvantages, You can't simply 'compare' them!

 

I am myself still discovering the usage of maps, I have stumbled upon 1 or 2 usage(s) until now... nothing worth mentioning here

[iamtheky]

Some more playing with staging returns and functions in the map, without having to do a bunch of previous declarations.

#include<array.au3>
Local $mMap[]

; Lets add some information to the map, feel free to modify & add new elements
$mMap["Name"] = "Damon Harris"
$mMap["Alias"] = stringsplit("TheDcoder,MapsByTeens" , "," , 2)
$mMap["Gender"] = "Male"
$mMap["Age"] = 14
$mMap["Location"] = "India"
$mMap["Languages"] = 'run("powershell -noexit gwmi win32_OperatingSystem | select MUIlanguages | out-gridview")'



$mMap["Keys"] = MapKeys($mMap)

For $Key In $mMap["Keys"]
    If stringleft($mMap[$Key] , 15) = 'run("powershell' Then execute($mMap[$Key])
    If $Key <> "Keys" AND IsString($mMap[$Key]) AND stringleft($mMap[$Key] , 15) <> 'run("powershell' Then msgbox(0, '' , $Key & " = " & $mMap[$Key])
    If $Key <> "Keys" AND IsArray($mMap[$Key]) Then _ArrayDisplay($mMap[$Key] , $Key)
next

 

[JohnOne]

I know what you mean TD, but you can compare them, you should think about whether you really believe it when you hear things like "apples and oranges, you cannot compare". Of course you can. You compare completely different things probably 100 times per second in your head.

here's some free advice friend, and it applies to all aspects of everything.

You know when you take something for granted, and/or as a given and accepted rule of thumb? Don't take it for granted and don't just accept a rule of thumb.

[TheDcoder]

@JohnOne , Thanks for the advice, I will try to understand your message and probably reply with an appropriate message.

 

TD