Associative Array functions

[jftuga]

I wish AAs were built into the language. For example:

$age["Jack"] = 2

$age["Jes"] = 5

$a = $age["Jes"]

( now $a would equal 5)

There should also be a way to iterate over the keys, as well as being able to delete keys.

-John

[Nutster]

Ok, I am back. The problem with the test script is that my hash functions were using a weak hash function, which combined with the sequential keys being given, to create a perfect storm of cascading resizes. Attached please find a corrected version of my associative array functions. I adapted a stronger hash function from someone else's post of a hash table. Thank you.

AssocArrays.au3

Edited December 14, 2007 by Nutster

[martin]

Ok, I am back. The problem with the test script is that my hash functions were using a weak hash function, which combined with the sequential keys being given, to create a perfect storm of cascading resizes. Attached please find a corrected version of my associative array functions. I adapted a stronger hash function from someone else's post of a hash table. Thank you.

Yes, that seems to have fixed it. I have tried it with up to 50,000 keys and no problems.

Since you have written some of the code for the variable storage system in AutoIt, maybe you could explain something about it to me. I mean maybe you would be willing to, I know you are able to. I can see how a compiler would deal with variables, or at least I can guess; I assume it would simply replace them all with pointers to memory locations. I can't work out how the compiler, or interpreter, would deal with the Assign and Eval functions in cases like Assign("Key2376",99,2) followed later by Eval("Key2376"); how do they work internally without Eval getting slower and slower the more variables that are assigned?

I imagine that to deal with dynamically declared variables you will either require a linear search or you use something like hash tables. If it was a linear search then the more variables stored the longer it would take to retrieve them all, but I find that the time to retrieve the keys using Assign/Eval is pretty constant per 1000 keys up to 500,000 keys. So I'm interested to know how that's done?

You might also be interested to know that although the Scripting.Dictionary object method is about 3 times faster than the Assign/Eval method to start with, the more keys I generate the more the Assign/Eval method catches up with it. By the time I get to 500,000 keys A/E takes about 50% longer than the Object method to assign the keys but reads them about 50% faster! I think that something quite clever must be going on inside AutoIt, but maybe I'm just not quite understanding something.

Edit:removed some rubbish.

Edited December 15, 2007 by martin

[randallc]

Hi,

1. So is there a "_HashSave" / "_HashLoad"

2. Or will just saving the Array2D to a file, save the "hash" capability with it?

3. [ie is all the detail saved in the 2D Array, or is there some other recording function?]

4. You understand that I don't understand the "Hash" or how it is being saved/ recorded!

Best, Randall

Edited December 15, 2007 by randallc

[martin]

Hi,

1. So is there a "_HashSave" / "_HashLoad"

2. Or will just saving the Array2D to a file, save the "hash" capability with it?

3. [ie is all the detail saved in the 2D Array, or is there some other recording function?]

4. You understand that I don't understand the "Hash" or how it is being saved/ recorded!

Best, Randall

With Nutster's method the arrays are 'self contained' as I understand them, so if you save them and then read them again you still have all the original functionality.

If you will excuse an attempt by someone who is trying to understand all this as well, here is my understanding of the use of hash tables so far.

First you try to get a number to represent the key so that you know where to store it. This could be easy if we weren't worried about the size of the array to store everything. We could just say we will allow keys up to 50 characters long. We work out the alphabetical value of the key and that is it's position in the array. But of course the array size is a bit large at more than a million Terrabytes so some compromise has to be made to reduce it.

So we say lets start with an array of 200 elements for example. Work out a value to give the key. This value might be a number like 1789 which is too large for the array so we say well we'll put it in element Mod(1789,200). This is Nutster's HasPos function.

The next problem is that this position might already be used so we say we'll move up the elements until we find a free one and put it there. Next problem is that you might then come to the end of the array so you have to grow it. As soon as you grow the array all the keys have to be repositioned because now we are using mod(keyvalue,newarraysize). That's why Nutster'sAssocArraAssign function is recursive.This slows the assign process down and to reduce the number of times this happens you want to grow the array by a good size. Nutster says that 30% is good and that sounds reasonable to me until the array gets very big anyway.

If you store the array and then you read it again or some other program reads it, all the information you need is there, which is the size of the array and the amount for growth. Of course the different programs which use the array have to use the same methods to work out the key values and the way to position everything.

[randallc]

Hi,

Thanks, that illuminates things!

Seems to work well too.

Best, Randall

PS I guess that means that

1. Loading and saving the Hash Array could be speeded up considerably by using a delimited 1D array instead [with minor performance hit only on retrieval, and Assign, I suspect]

2. creating the Hash Array from another 2D array could be accelerated considerably using a vbs routine.

Would those be of value?

I will think on it..

[martin]

1. Loading and saving the Hash Array could be speeded up considerably by using a delimited 1D array instead [with minor performance hit only on retrieval, and Assign, I suspect]

If you mean using the Assign/Eval idea in my post then yes you could use a 1D array because you don't need to save the key values in the array to write or read. But that's not an option if you need to save then load the array again later because you would have lost the key names and the array would be unusable.

You can't use a 1D array for the hash table method because there will be collisions, and you won't be able to see if the key name is correct or find where it is stored.

2. creating the Hash Array from another 2D array could be accelerated considerably using a vbs routine.

I don't know if that's true or not.

[Nutster]

David,

How does your implementation compare (in terms of speed) to using something like:

$dict = ObjCreate("Scripting.Dictionary")

$dict.Add( $key, $val )

$val = $dict.Item($key)

Thanks,

-John

I don't know how it would compare. Why don't you do a test comparison and let us know the results? I have not used the Scripting.Dictionary object before. I don't even know if I have access to it.

[martin]

I don't know how it would compare. Why don't you do a test comparison and let us know the results? I have not used the Scripting.Dictionary object before. I don't even know if I have access to it.

Some answers in my post #20.

I've done a few tests on the three methods, here are some results.

keys             write 1000 read 1000          write 100,000        read 100,000        write 500,000        read 500,000
 ScriptDict                 26             21               3518                  3070              41573                39167 
 Assign/Eval                   85              31               8649                  3688              47337                19773
 Hash Table               2171            683             317410                 80492               ???                  ???

                                                                                           Times in mS

Some questions in my post #23.

This is what I used to make the tests

expandcollapse popup

; HashTestAssoc.au3

;Comment out one of the 2 includes to test the other
;#include "AssocArray3.au3";martin
;#include <assocarrays.au3>;Nutster 

Global $iCount, $iSize, $iSize1= Number(InputBox("Number of keys to read/write","number"))
Global $nTmp
Global $sName
Global $avArray
Local $aArrayfile[$iSize1], $sStringFile, $aArray1;= StringSplit($data, ":")
;======================================================
global $knames[5] = ["dog","canary","bicycle","radiator","improvisation"]
$dict = ObjCreate("Scripting.Dictionary")
$dict.Add( 'kip', 87 )
$tt = timerinit()
For $i = 1 To $iSize1-1
   $dict.Add( $knames[mod($i,5)] & $i,'Value' & $i)
Next
$dif = TimerDiff($tt)
consolewrite("time to write 10000 = " & $dif & ', ')
$tt = timerinit()
For $i = 1 To $iSize1-1
$val = $dict.Item( $knames[mod($i,5)] & $i)
next
$dif1 = timerdiff($tt)
consolewrite("time to read 10000 = " & $dif1 & @LF)
AssocArrayCreate ($avArray, $iSize1)   ; Create the associative array with storage for $iSize1 elements.
$tt = timerinit()
For $i = 1 To $iSize1-1
    If AssocArrayAssign ($avArray,  $knames[mod($i,5)] & $i,"Value"&$i)= False Then ExitLoop
Next
$dif2 = TimerDiff($tt)
consolewrite("time to write " & $iSize1 & " = " & $dif2 & ', ')

;~;======================================================
$tt = timerinit()
For $i = 1 To $iSize1-1
$val = AssocArrayGet ($avArray, $knames[mod($i,5)] & $i)
next
$dif3 = timerdiff($tt)
consolewrite("time to read " & $iSize1 & " = " & $dif3 & @LF)
$timer2 = TimerInit()

while 1
    $test =  StringStripWS(InputBox("test","number"),8)
if $test = '' then exitloop 
    $test = $knames[mod($test,5)] & $test
$sValue = AssocArrayGet($avArray, $test)
 msgbox(0,$test,$sValue)
 wend
;~;======================================================

Edited December 16, 2007 by martin

[Nutster]

Yes, that seems to have fixed it. I have tried it with up to 50,000 keys and no problems.

Since you have written some of the code for the variable storage system in AutoIt, maybe you could explain something about it to me. I mean maybe you would be willing to, I know you are able to. I can see how a compiler would deal with variables, or at least I can guess; I assume it would simply replace them all with pointers to memory locations. I can't work out how the compiler, or interpreter, would deal with the Assign and Eval functions in cases like Assign("Key2376",99,2) followed later by Eval("Key2376"); how do they work internally without Eval getting slower and slower the more variables that are assigned?

I imagine that to deal with dynamically declared variables you will either require a linear search or you use something like hash tables. If it was a linear search then the more variables stored the longer it would take to retrieve them all, but I find that the time to retrieve the keys using Assign/Eval is pretty constant per 1000 keys up to 500,000 keys. So I'm interested to know how that's done?

You might also be interested to know that although the Scripting.Dictionary object method is about 3 times faster than the Assign/Eval method to start with, the more keys I generate the more the Assign/Eval method catches up with it. By the time I get to 500,000 keys A/E takes about 50% longer than the Object method to assign the keys but reads them about 50% faster! I think that something quite clever must be going on inside AutoIt, but maybe I'm just not quite understanding something.

Keep in mind, I haven't looked at the AutoIt variable system in a about 4 years, so things may have changed. Generally a fully compiled language, like C++ or Java does replace the names with pointers to the actual storage of the variables. This saves space and time. In a compiled language, the Assign, Eval and Execute function can not be used, because all the names, along with other human-readable information, are tossed away during the compile. Interpreted languages, including AutoIt, need to store a name/value pair and reference the values using the name as the program runs. Even when compiled, AutoIt remains interpreted. Assign, Eval and Execute use part of the interpreter that is included so the source code can be executed to do their work.

When I was rewriting the variables one time, I implemented both a binary search tree and a linked list to compare the timings. The binary search tree has some extra overhead that made it faster only after about 50 variables were added. As the developers believed that most scripts would employ less than 50 variables, we went with the linked list. Hmm, I wonder. If you include some of those huge Include files, you get way more than 50 variables. Maybe the global variables should use a binary tree and the local variables stay as linked lists. Uhh, never mind. Just got distracted. It may have been changed since I was working on them.

It sounds like Scripting.Dictionary is using a binary search array. It is fast to find elements, but slow to insert new elements. The linked list I used is quick to insert new elements, but slow to find them. The hash table that I provided is fast to insert, if it does not have to resize, and fast to find, but because the hash table is written in AutoIt instead of a compiled language like C++, it automatically runs slower. Take a look at this for my explanation about that. Written in C++, it would be faster than either. Hmm, hash table DLL? Sorry, I got distracted again.

Any more questions, ask away. I just may need some time to answer.

[SkinnyWhiteGuy]

Since you've mentioned it Nutster, I've been wondering about the use of an external approach to hash tables versus a native approach. I know that the compiled version would be faster, but my main thought has been if the DllCall functions sending requests/getting answers and all is more expensive time-wise than an all AutoIt solution, it wouldn't be that beneficial in the long run.

Only reason I point this out, is because I've often thought the same thing about some cryptography stuff I work with, wondering if it would be worth it to rework it all as a dll solution, but if the extra time it took to call the dll, get the answer, and handle all that made it equal to, or even worse, than an all AutoIt solution, I'd rather leave it all in one file with AutoIt and not have to FileInstall another file. If, however, it is found that Dll's provide a much larger speed boost, I'll see how much cryptography stuff I can convert, as well.

BTW, in the post in the Ideas thread about this same subject, I linked to my attempt to use the same hash function from Wikipedia, but instead of making the array grow, and doing the mod the smart way you do, I just made the array max size to start with, so each "hash" that way is the same size. Ah well, live and learn (from someone who's been doing it longer than you usually).

[Nutster]

Ok, I ran your tests after I modified it a little bit (see attached). My hash table is significantly slower than using the Dictionary object for any size I tried. It might be from the fact that I have an old machine running at 400 MHz. I still like what I wrote because it is all AutoIt and it works (most of the time). I am thinking of trying the DLL. Let's see, how are plugin's done in AutoIt?

HashTestAssoc.au3

[WolfWorld]

This is very cool I use this in PHP if autoit put it as a part of the program it will be very cool

[Nutster]

Hi,

1. So is there a "_HashSave" / "_HashLoad"

2. Or will just saving the Array2D to a file, save the "hash" capability with it?

3. [ie is all the detail saved in the 2D Array, or is there some other recording function?]

4. You understand that I don't understand the "Hash" or how it is being saved/ recorded!

Best, Randall

• Okay, you asked for it. Back on the first post of this thread, I updated the files with AssocArraySave and AssocArrayLoad. These functions save the hash table as a CSV text file and read a CSV file into an associative array. The array in the file is not stored sorted.
• The hash capability is part of the script / application, not the array.
• The array stores the keys and values. The location of the key-value pairs is determined by the hash function.
• Read the other posts in the thread for more information on hash tables. There are also a couple of other recent threads in this forum about hash tables.

Edit: Fix grammar and construction mistakes. Edited December 24, 2007 by Nutster

[Nutster]

This is very cool I use this in PHP if autoit put it as a part of the program it will be very cool

There a no plans to add associative arrays as a built-in feature of AutoIt. I think if I write this implementation in a DLL to be called with DLLCall, then that will speed this up to be generally faster than other objects. Maybe next year.

[az2000]

Attached please find an Include file and an exerciser that demonstrates how to use my associative array functions. Read the comments at the top of each function for more details on their use.

Your function helped me greatly. Associative arrays are a fundamental part of programming for me. I don't know how other AutoIT users get by without it.

A couple of feature requests:

1. An "exists" function

I can use the "get" function because you return False if the item doesn't exist. But, the conditional logic is convoluted. The number 0 and empty string also seem to evaluate to False. So, if the item exists but contains either of those values it would evaluate like the item didn't exist.

This is how I do it:

If (AssocArrayGet($my_hash, $i) <> False) or (AssocArrayGet($my_hash, $i) <> 5) Then
 ; do something because it exists
EndIf

The idea is, if it's not Boolean False it exists. Or, if the length of the returned value isn't 5 (the length of the string "False") it exists. That second part causes 0 and "" hash values to be treated as not boolean False.

If there's a better way to do this in AutoIT, I'd like to know. Otherwise, an "exists" function would be nice.

2. A "keys" function

Sometimes it's useful to get the keys of a hash so the hash can be iterated over like an array. Being able to get an array of "keys" makes it easier. Otherwise, I have to maintain an array of keys as I build the hash.

3. The create function should treat the "size" parameter literally

You add 25% to the size parameter even if the growth parameter is 0. If I say the hash won't grow, then it shouldn't be created with extra space for growth.

I think it should use the growth parameter when creating the array's initial size. If I say 0 growth, it should be created with no space for growth. If I say 50%, it should be created with that growth, not a hard-coded 25% growth.

Thanks for the time you spent creating this. I wish AutoIT had built-in function to do this.

EDIT: Regarding #1. I just realized your "get" function sets @ERROR if the item doesn't exist. All I have to do is call the "get" function and then "If Not @ERROR" means the item exists.

I think it would be clearer if there were an "exists" function. Just "if exists($key)". But, it's not as convoluted as I originally thought.

Edited June 19, 2009 by az2000

[az2000]

The hash idea is a bit complicated and I don't see what the advantage is. Isn't it simpler, and faster, to do something like this. (It's only shown as an idea and obviously not fully developed.)

Your approach (setting global variables) resonated with me. I started to create my own associative array logic, and chose to do it the same way. Just use eval, assign, and isDeclared.

But, if a person wants to have a "keys" function (to return all the keys in an AA) it can't be done without maintaining some kind of index for the hash. Then it starts to slow down like your tests found Nutster's to be.

Without that index, you can't do other things like have a "delete" function to remove a key. That's another function which should be added to Nutster's. Doing an "exists" is kind of meaningless if you can't delete keys. Setting an entry to "" leaves an existing entry.

So, based on the functions Nutster provided, I agree that you can do the same functions faster (and maybe more intuitively, depending on an individual's tastes).

But, Nutster's method provides for functionality that he hasn't implemented (keys, values, exists, delete). To me, those are essential for AA processing. (Scripting.Dictionary has it. But, I don't like being dependent on whether the user has those Microsoft add-ons installed. AA processing shouldn't be this hard. I can't believe how much time I've spent trying to do something that seems to be as essential to programming as the "if" operation.).

Mark

[martin]

Your approach (setting global variables) resonated with me. I started to create my own associative array logic, and chose to do it the same way. Just use eval, assign, and isDeclared.

But, if a person wants to have a "keys" function (to return all the keys in an AA) it can't be done without maintaining some kind of index for the hash. Then it starts to slow down like your tests found Nutster's to be.

Without that index, you can't do other things like have a "delete" function to remove a key. That's another function which should be added to Nutster's. Doing an "exists" is kind of meaningless if you can't delete keys. Setting an entry to "" leaves an existing entry.

So, based on the functions Nutster provided, I agree that you can do the same functions faster (and maybe more intuitively, depending on an individual's tastes).

But, Nutster's method provides for functionality that he hasn't implemented (keys, values, exists, delete). To me, those are essential for AA processing. (Scripting.Dictionary has it. But, I don't like being dependent on whether the user has those Microsoft add-ons installed. AA processing shouldn't be this hard. I can't believe how much time I've spent trying to do something that seems to be as essential to programming as the "if" operation.).

Mark

I'm not sure if you're saying that you can't return a list of all the keys with the method I showed, or delete a key, but I think you can do both. That is to say I think that functions to do that could be added quite easily. The same with Exists.

[az2000]

I'm not sure if you're saying that you can't return a list of all the keys with the method I showed, or delete a key, but I think you can do both. That is to say I think that functions to do that could be added quite easily. The same with Exists.

It seemed to me like it didn't maintain a namespace for each hash. I tried using it and when I had the same key value in two hashes something was clobbered. I lost one of them.

I was thinking if you had to maintain true name spaces for each hash it would begin to slow it down similarly what you found with Nutster's.

Edit: Sorry. I made a remark about using "assign" with invalid variable names (containing spaces, dollar signs, etc). I didn't realize AutoIT allows that.

Edited June 20, 2009 by az2000

[Nutster]

Your function helped me greatly. Associative arrays are a fundamental part of programming for me. I don't know how other AutoIT users get by without it.

A couple of feature requests:

1. An "exists" function

I can use the "get" function because you return False if the item doesn't exist. But, the conditional logic is convoluted. The number 0 and empty string also seem to evaluate to False. So, if the item exists but contains either of those values it would evaluate like the item didn't exist.

This is how I do it:

If (AssocArrayGet($my_hash, $i) <> False) or (AssocArrayGet($my_hash, $i) <> 5) Then
; do something because it exists
EndIf

The idea is, if it's not Boolean False it exists. Or, if the length of the returned value isn't 5 (the length of the string "False") it exists. That second part causes 0 and "" hash values to be treated as not boolean False.

If there's a better way to do this in AutoIT, I'd like to know. Otherwise, an "exists" function would be nice.

2. A "keys" function

Sometimes it's useful to get the keys of a hash so the hash can be iterated over like an array. Being able to get an array of "keys" makes it easier. Otherwise, I have to maintain an array of keys as I build the hash.

3. The create function should treat the "size" parameter literally

You add 25% to the size parameter even if the growth parameter is 0. If I say the hash won't grow, then it shouldn't be created with extra space for growth.

I think it should use the growth parameter when creating the array's initial size. If I say 0 growth, it should be created with no space for growth. If I say 50%, it should be created with that growth, not a hard-coded 25% growth.

Thanks for the time you spent creating this. I wish AutoIT had built-in function to do this.

EDIT: Regarding #1. I just realized your "get" function sets @ERROR if the item doesn't exist. All I have to do is call the "get" function and then "If Not @ERROR" means the item exists.

I think it would be clearer if there were an "exists" function. Just "if exists($key)". But, it's not as convoluted as I originally thought.

Glad you like it.

The 25% extra space (called slack space, or just slack) during creation is not really to allow for growth, but to help avoid collisions when inserting elements in the hash table. If two elements have the same hash index, then a collision occurs and the search and insertions slow down. By adding a little extra space, this reduces the number of collisions and speeds up operations in the hash table. The fuller a hash table is, the more collisions are likely to occur and the slower it gets.

You could create a hash function to exactly match your data, thus avoiding the need for slack space, but the function would need to be rewritten for each set of data, and you would need to know the data before hand. This is used in some games. This function is meant to have a good general solution, so there are compromises.

Adding AssocArrayExists($aHashTable, "key") (returns True or False), AssocArrayDelete($aHashTable, "key") (returns True if deleted, False if not found), AssocArrayKeys($aHashTable) (returns 1D array of index keys) all look like good ideas. I will see about implementing them soon, hopefully this week. I do not see the value of AssocArrayValues($aHashTable). How would it be used?