Sign in to follow this  
Followers 0

arrays with string elements

26 posts in this topic

Posted

Couldn't AutoIt have arrays with string elements such as $array['hi']

(if this is already in autoit, i sure didnt see it in the manual...)

Share this post


Link to post
Share on other sites



Posted

This is most properly called an associative array, in other programming languages called a dictionary or a hash.

While you can do this in AutoIt now:

Enum $Hi, $Bye, $Huh, $max
Dim $ourArray[$max]

$ourArray[$Hi] = "Hi."
$ourArray[$Bye] = "Bye."
$ourArray[$Huh] = "Say what?"

...I doubt that that would be satisfying to anybody since it wouldn't let you arbitrarily assign a new element to it without worrying about array bounds, Redim. etc...

This is someone's opportunity for credibility: download the AutoIt 3 source, make an implementation of associative arrays and post it to this forum.

Share this post


Link to post
Share on other sites

Posted

Most of this has been covered before. Here is some of the prior work.

#include-once
;------------------------------------------------------------------------------
;
; AutoIt Version: 3.0
;
; Script Function:
;  "Hash" - an associative container of key/value pairs
;
; Note that the name is taken from the Perl "Hash" and is not a "hash table"
;
; Author:		 Graham Shanks
;
; Version 1.0   28/01/2004  Initial release
; Version 1.1   10/03/2004  Initial release
;------------------------------------------------------------------------------


;------------------------------------------------------------------------------
; Description:  Create a hash (associative array) from a string containing a 
;			   series of key/value pairs
;
; Parameters:
;   $string	 A string containing the data to be entered into the hash
;   $sep1	   The delimeter between elements
;   $sep2	   The delimeter between the key and the value within the element
;
; Returns:
;   Success:	The hash. 
;   Failure:	If any of the elements do not contain a key/value pair (i.e.
;			   $sep2 is not contained in in the element) then @error is set 
;			   to the index of the offending element. An empty hash is 
;			   returned
;
; Example:
;
;   $dLanguages = HashCreate("0436:Afrikaans\041c:Albanian\0401:Arabic Saudi Arabia\0801:Arabic Iraq\0c01:Arabic Egypt\1001:Arabic Libya\0409:English", "\", ":")
;
;   MsgBox(4096 +64,"","Your PC speaks " & HashLookUp($dLanguages, @OSLANG))
;   MsgBox(4096 +64,"","Some South Africans speak " & HashLookUp($dLanguages,"0436"))
;------------------------------------------------------------------------------
Func HashCreate($string, $sep1, $sep2)
 Local $Result[3]

 $temp = StringSplit($string, $sep1)

 Local $keys[$temp[0]]
 Local $data[$temp[0]]

 for $i = 1 to $temp[0]
   $split = StringSplit($temp[$i], $sep2)
   if @error == 1 then
	 $Result[0] = 0
	 $Result[1] = 0
	 $Result[2] = 0
	 SetError($i)
	 return $Result
   endif
   $keys[$i-1] = $split[1]
   $data[$i-1] = $split[2]
 next

; sort on BOTH $keys AND $data
 HashQuickSort($keys, $data, 0, $temp[0]-1)

 $Result[0] = $temp[0]
 $Result[1] = $keys
 $Result[2] = $data
 return $Result
EndFunc

;------------------------------------------------------------------------------
; Description:  Create an empty hash (associative array)
;
; Returns:	  The hash. 
;
; Example:
;
;   $hash = HashCreateEmpty()
;
;------------------------------------------------------------------------------
Func HashCreateEmpty()
 Local $Result[3]
 $Result[0] = 0
 $Result[1] = 0
 $Result[2] = 0
 return $Result
EndFunc

;------------------------------------------------------------------------------
; Description:  Insert a key/value pair into a hash (associative array)
;
; Parameters:
;   $hash	   The hash
;   $key		The key
;   $value	  The value associated with teh key
;
; Returns:	  Nothing
;
; Example:
;
;   $hash = HashCreateEmpty()
;   HashInsert($hash, "0436", "Afrikans")
;
;   MsgBox(4096 +64,"","Some South Africans speak " & HashLookUp($hash,"0436"))
;
;------------------------------------------------------------------------------
Func HashInsert(ByRef $hash, $key, $value)
 Local $keys[HashSize($hash)+1]
 Local $data[HashSize($hash)+1]

 for $i = 0 to HashSize($hash)-1
   $keys[$i] = HashKey($hash, $i)
   $data[$i] = HashData($hash, $i)
 next
 $keys[HashSize($hash)] = $key
 $data[HashSize($hash)] = $value
 HashQuickSort($keys, $data, 0, HashSize($hash))
 $hash[0] = HashSize($hash)+1
 $hash[1] = $keys
 $hash[2] = $data
EndFunc

;------------------------------------------------------------------------------
; Description:  Look up the value associated with the specified key in the 
;			   specified hash
;
; Parameters:
;   $hash	   The hash
;   $key		The key to look up
;
; Returns:
;   Success:	The value associated with the specified key
;   Failure:	If the key is not in the hash, then zero is returned and 
;			   @Error is set to 1
;------------------------------------------------------------------------------
Func HashLookUp(ByRef $hash, $key)
 $l = 0
 $u = HashSize($hash) - 1
 while $l <= $u
   $m = int(($l+$u)/2)
   $t = HashKey($hash, $m)
   if $t < $key then
	 $l = $m + 1
   else
	 if $t > $key then
	   $u = $m - 1
	 else
	   return HashData($hash, $m)
	 endif
   endif
 wend

 SetError(1)
 return 0
EndFunc

;------------------------------------------------------------------------------
; Description:  Gets the size of the specified hash container
;
; Parameters:
;   $hash	   The hash
;
; Returns:	  The number of key/value pairs in the hash
;------------------------------------------------------------------------------
Func HashSize(ByRef $hash)
 return $hash[0]
EndFunc

;------------------------------------------------------------------------------
; The following functions are for internal use and are not intended for use by 
; users. Ignore this and on your own head be it :-)
;------------------------------------------------------------------------------

; Gets the key at the specified position
Func HashKey(ByRef $hash, $index)
 return HashKeyHelper($hash[1],$index)
EndFunc

; Gets the data at the specified position
Func HashData(ByRef $hash, $index)
 return HashDataHelper($hash[2],$index)
EndFunc

; Helper function for HashKey
Func HashKeyHelper(ByRef $keys, $index)
 return $keys[$index]
EndFunc

; Helper function for HashData
Func HashDataHelper(ByRef $data, $index)
 return $data[$index]
EndFunc

Func HashIndexFind(ByRef $hash, $key)
 $l = 0
 $u = HashSize($hash) - 1
 while $l <= $u
   $m = int(($l+$u)/2)
   $t = HashKey($hash, $m)
   if $t < $key then
	 $l = $m + 1
   else
	 if $t > $key then
	   $u = $m - 1
	 else
	   return $m
	 endif
   endif
 wend

 SetError(1)
 return 0
EndFunc

; Debug aid - gathers the contents into a string
Func HashDisplay(ByRef $hash)
 $dummy = ""
 for $i = 0 to HashSize($hash)-1
   $dummy = $dummy & " " & $i & " <" & HashKey($hash, $i) & "> <" & HashIndexFind($hash, $i) & "> <" & HashData($hash,$i) & ">" & @CRLF
 next
 return $dummy
EndFunc

; Get a random value in the range $l to $u
Func HashRandInt($l, $u)
 return $l + int(($u - $l + 1) * Random(0, 1))
EndFunc

; Swap two element
Func HashSwap(ByRef $a, ByRef $b)
 $temp = $a
 $a = $b
 $b = $temp
EndFunc

; Quick sort routine - uses insertion sort on small subfiles
Func HashQuickSort(ByRef $keys, ByRef $data, $l, $u)
 while 1
   if $u - $l < 9 then
  ; Insertion sort
	 for $step = $l to $u
	   $dummy1 = $keys[$step]
	   $dummy2 = $data[$step]
	   for $j = $step-1 to $l step -1
		 if $keys[$j] > $dummy1 then
		   $keys[$j+1] = $keys[$j]
		   $data[$j+1] = $data[$j]
		 else
		   exitloop
		 endif
	   next
	   $keys[$j+1] = $dummy1
	   $data[$j+1] = $dummy2
	 next
	 return
   else
  ; The actual quick sort
	 $x = HashRandInt($l, $u)
	 HashSwap($keys[$l], $keys[$x])
	 HashSwap($data[$l], $data[$x])
	 $t = $keys[$l]
	 $m = $l
	 for $i = $l + 1 to $u
	   if $keys[$i] < $t then
		 $m = $m + 1
		 HashSwap($keys[$m], $keys[$i])
		 HashSwap($data[$m], $data[$i])
	   endif
	 next
	 HashSwap($keys[$l], $keys[$m])
	 HashSwap($data[$l], $data[$m])
	 HashQuickSort($keys, $data, $l, $m - 1)
	 $l = $m + 1
   endif
 wend
EndFunc



#include "Hash-better.au3"

$data = "0436,Afrikaans:041c,Albanian:0401,Arabic_Saudi_Arabia:_
0801,Arabic_Iraq:0c01,Arabic_Egypt:1001,Arabic_Libya:_
1401,Arabic_Algeria:1801,Arabic_Morocco:1c01,Arabic_Tunisia:_
2001,Arabic_Oman:2401,Arabic_Yemen:2801,Arabic_Syria:_
2c01,Arabic_Jordan:3001,Arabic_Lebanon:3401,Arabic_Kuwait:_
3801,Arabic_UAE:3c01,Arabic_Bahrain:4001,Arabic_Qatar:_
042b,Armenian:042c,Azeri_Latin:082c,Azeri_Cyrillic:_
042d,Basque:0423,Belarusian:0402,Bulgarian:0403,Catalan:_
0404,Chinese_Taiwan:0804,Chinese_PRC:0c04,Chinese_Hong_Kong:_
1004,Chinese_Singapore:1404,Chinese_Macau:041a,Croatian:_
0405,Czech:0406,Danish:0413,Dutch_Standard:0813,Dutch_Belgian:_
0409,English_United_States:0809,English_United_Kingdom:_
0c09,English_Australian:1009,English_Canadian:_
1409,English_New_Zealand:1809,English_Irish:_
1c09,English_South_Africa:2009,English_Jamaica:_
2409,English_Caribbean:2809,English_Belize:2c09,English_Trinidad:_
3009,English_Zimbabwe:3409,English_Philippines:0425,Estonian:_
0438,Faeroese:0429,Farsi:040b,Finnish:040c,French_Standard:_
080c,French_Belgian:0c0c,French_Canadian:100c,French_Swiss:_
140c,French_Luxembourg:180c,French_Monaco:0437,Georgian:_
0407,German_Standard:0807,German_Swiss:0c07,German_Austrian:_
1007,German_Luxembourg:1407,German_Liechtenstein:0408,Greek:_
040d,Hebrew:0439,Hindi:040e,Hungarian:040f,Icelandic:_
0421,Indonesian:0410,Italian_Standard:0810,Italian_Swiss:_
0411,Japanese:043f,Kazakh:0457,Konkani:0412,Korean:0426,Latvian:_
0427,Lithuanian:042f,Macedonian:043e,Malay_Malaysia:_
083e,Malay_Brunei_Darussalam:044e,Marathi:0414,Norwegian_Bokmal:_
0814,Norwegian_Nynorsk:0415,Polish:0416,Portuguese_Brazilian:_
0816,Portuguese_Standard:0418,Romanian:0419,Russian:_
044f,Sanskrit:081a,Serbian_Latin:0c1a,Serbian_Cyrillic:_
041b,Slovak:0424,Slovenian:040a,Spanish_Traditional_Sort:_
080a,Spanish_Mexican:0c0a,Spanish_Modern_Sort:_
100a,Spanish_Guatemala:140a,Spanish_Costa_Rica:_
180a,Spanish_Panama:1c0a,Spanish_Dominican_Republic:_
200a,Spanish_Venezuela:240a,Spanish_Colombia:280a,Spanish_Peru:_
2c0a,Spanish_Argentina:300a,Spanish_Ecuador:340a,Spanish_Chile:_
380a,Spanish_Uruguay:3c0a,Spanish_Paraguay:400a,Spanish_Bolivia:_
440a,Spanish_El_Salvador:480a,Spanish_Honduras:_
4c0a,Spanish_Nicaragua:500a,Spanish_Puerto_Rico:0441,Swahili:_
041d,Swedish:081d,Swedish_Finland:0449,Tamil:0444,Tatar:_
041e,Thai:041f,Turkish:0422,Ukrainian:0420,Urdu:_
0443,Uzbek_Latin:0843,Uzbek_Cyrillic:042a,Vietnamese"

$hash = HashCreate($data, ":", ",")

MsgBox(4096 +64,"HashTest","Your PC speaks " & HashLookUp($hash, @OSLANG))
MsgBox(4096 +64,"","Some South Africans speak " & HashLookUp($hash,"0436"))

Share this post


Link to post
Share on other sites

Posted

Sorry for brining out old topic but i've been working with hashes (http://www.autoitscript.com/forum/index.php?showtopic=11611) in autoit for longer while now. I am also aware of the 3 other hash (associative arrays) topics that one can find on this marvelous forum. However i believe hashes are aought to be very fast (like in PERL) and this can only be achieved when natively supported by AutoIt.

For example I've now made a script that writes about 900KB of data to file. It goes thru a lot of files (.inf files that are around hdd) gets some stuff from it and puts it into the file. This alone when run 1st time (as in not cached at all by system takes about 20seconds). And i mean whole process of opening every inf file it finds and putting it to one file (However i do open the file once and close it once. I tried to use IniWriteSection and similar but due to closing/opening all the time it was far tooo slow) in format:

[\C\AM\1\Amdagp8x.inf]

1=AMDAGP_Install,PCI\VEN_1022&DEV_7454

2=AMD2k_Install,PCI\VEN_1022&DEV_7455

3=AMDXP_Install,PCI\VEN_1022&DEV_7455

[\C\AM\2\amdioapic.inf]

1=NO_DRV,PCI\VEN_1022&DEV_7451

[\C\AM\3\Amd8131.inf]

1=Amd8131_Inst,PCI\VEN_1022&DEV_7450&CC_0604

2=Amd8131_Inst64,PCI\VEN_1022&DEV_7450&CC_0604

[\C\AM\4\AmdShpc.inf]

1=AmdShpc_Inst,PCI\VEN_1022&DEV_7450&CC_0604

2=AmdShpc_Inst,PCI\VEN_1022&DEV_7458&CC_0604

3=AmdShpc_Inst32,PCI\VEN_1022&DEV_7450&CC_0604

4=AmdShpc_Inst32,PCI\VEN_1022&DEV_7458&CC_0604

5=AmdShpc_Inst64,PCI\VEN_1022&DEV_7450&CC_0604

6=AmdShpc_Inst64,PCI\VEN_1022&DEV_7458&CC_0604

When i simply add _HashF_Put ($special_value[2], $all_inf[$a], $Hardware_Memory_HWID)

to get it added to hash (into memory so i could work on it as my program is still running) the time from 20seconds extends to 5 minutes!!!

While I have successfully used Hash by MrRider for smaller tasks and it was great it's just not enough on this task. So maybe associative arrays could be put on to do list as natively included in AutoIt.

Ps. I haven't yet tested other hash implementations but i guess it will be more or less the same.

MadBoy

Share this post


Link to post
Share on other sites

Posted

Sorry for brining out old topic but i've been working with hashes (http://www.autoitscript.com/forum/index.php?showtopic=11611) in autoit for longer while now. I am also aware of the 3 other hash (associative arrays) topics that one can find on this marvelous forum. However i believe hashes are aought to be very fast (like in PERL) and this can only be achieved when natively supported by AutoIt.

For example I've now made a script that writes about 900KB of data to file. It goes thru a lot of files (.inf files that are around hdd) gets some stuff from it and puts it into the file. This alone when run 1st time (as in not cached at all by system takes about 20seconds). And i mean whole process of opening every inf file it finds and putting it to one file (However i do open the file once and close it once. I tried to use IniWriteSection and similar but due to closing/opening all the time it was far tooo slow) in format:

When i simply add _HashF_Put ($special_value[2], $all_inf[$a], $Hardware_Memory_HWID)

to get it added to hash (into memory so i could work on it as my program is still running) the time from 20seconds extends to 5 minutes!!!

While I have successfully used Hash by MrRider for smaller tasks and it was great it's just not enough on this task. So maybe associative arrays could be put on to do list as natively included in AutoIt.

Ps. I haven't yet tested other hash implementations but i guess it will be more or less the same.

MadBoy

Yes I think so too. These include functions you can find on forums are just to make autoit do associative array for me, but generally with no added usability or speed when it uses iteration through whole array while looking for hash...

Share this post


Link to post
Share on other sites

Posted

You can use the VBS dictionary object also.

Share this post


Link to post
Share on other sites

Posted

A few years ago I created an associative array routine that used a two-dimensional array to store the key and the data. I used a binary search, but I have rewritten it using a hash table for faster inserts. This is not that well tested (read none other than tidy and syntax check did not complain), but it should work pretty much as written. Let me know any comments please.

#cs ----------------------------------------------------------------------------
	
	AutoIt Version: 3.2.9.14 (beta)
	Author:         David Nuttall
	
	Script Function:
	Associative Array functionality
	
#ce ----------------------------------------------------------------------------

AutoItSetOption("MustDeclareVars", True)

#cs
	Function:  AssocArrayCreate
	Purpose:  Create an associative array in a variable.
	Parameters:
	$aArray:  The variable to have an associative array create in it.
	$nSize:  The starting size of the new array
	$nGrowth:  How much to grow the array by each time it needs to grow
	Return value:  True if the associative array could be created; False otherwise
	Notes:
#ce
Func AssocArrayCreate(ByRef $aArray, Const $nSize, Const $nGrowth = 99)
	If IsNumber($nSize) = 0 Then
		; Need a number here
		Return False
	ElseIf $nSize < 1 Then
		; Too small
		Return False
	Else
		Local $nHashSize = $nSize + 1
		
		While NotPrime($nHashSize)
			$nHashSize += 1
		WEnd
		Dim $aArray[2][$nHashSize]
		$aArray[0][0] = 0	; Active array size
	EndIf
	If IsNumber($nGrowth) = 0 Then
		; Need a number here
		Return False
	ElseIf $nGrowth < 2 Then
		; Too small
		$aArray[1][0] = 2
	Else
		$aArray[0][0] = $nGrowth
	EndIf
	Return True
EndFunc   ;==>AssocArrayCreate

#cs
	Function:  AssocArrayAssign
	Purpose:  Assign a value to an element of an associative array.
	Parameters:
	$aArray:  The array containing an associative array
	$sKey:  The key value in the array
	$vValue:  The value to assign to the element of the associtive array
	Return value:  True if the value could be assigned; False otherwise
	Notes:  This uses a hash table.  There is probably a faster way to resize a hash table.
	It grows the array if hash key collisions occur more than 3 times in a row or the hask key collision push the assignment off the end of the array.
#ce
Func AssocArrayAssign(ByRef $aArray, Const $sKey, Const $vValue)
	Local $nPos = HashPos($sKey, UBound($aArray, 2))
	Local $nCollide = 0
	
	While $nPos < UBound($aArray, 2)
		Switch $aArray[0][$nPos]
			Case ""
				; Not found.  Fill it in
				$aArray[0][$nPos] = $sKey
				$aArray[1][$nPos] = $vValue
				$aArray[0][0] += 1
				Return True
			Case $sKey
				; Found the correct key
				$aArray[1][$nPos] = $vValue
				Return True
			Case Else
				; Key collision
				$nCollide += 1
				If $nCollide > 3 Then ExitLoop
		EndSwitch
	WEnd
	; Not found, at end of array or too many collisions
	; Grow the array and try again.
	Local $aTmp = $aArray
	Local $nHashSize = UBound($aArray, 2) + $aArray[1][0] ' Adding the old size and the growth rate
	Local $i
	
	While NotPrime($nHashSize)
		$nHashSize += 1
	WEnd
	Dim $aArray[2][$nHashSize]	; Reset size
	$aArray[0][0] = 0	; Active array size
	$aArray[1][0] = $aTmp[1][0]
	
	AssocArrayAssign($aArray, $skey, $vValue)	; Assign the value that got us here in the first place
	; Assign the old values 
	For $i = 1 To UBound($aTmp, 2)
		If $aArray[0][$i] > "" Then
			AssocArrayAssign($aArray, $aTmp[0][$i], $aTmp[1][$i])
		EndIf
	Next
	Return True
EndFunc   ;==>AssocArrayAssign

#cs
	Function:  AssocArrayGet
	Purpose:  Get the value of an element in an associative array.
	Parameters:
	$aArray:  The array containing an associative array
	$sKey:  The key value in the array
	Return value:  Value in the element if found.  Otherwise, sets @Error to 1
	Notes:  This uses a hash table, which is pretty fast.  It could be replaced with another fast search method.
#ce
Func AssocArrayGet(ByRef Const $aArray, Const $sKey)
	Local $nPos = HashPos($sKey, UBound($aArray, 2))
	
	While $nPos < UBound($aArray, 2)
		Switch $aArray[0][$nPos]
			Case ""
				; Not found
				SetError(1)
				Return False
			Case $sKey
				; Got it
				Return $aArray[1][$nPos]
		EndSwitch
	WEnd
	; Not found at end of array
	SetError(1)
	Return False
EndFunc   ;==>AssocArrayGet

#cs
	Function:  NotPrime
	Purpose:  Determine if a number is not prime.  Support function for hash table.
	Parameters:
	$nValue:  The value to test for prime.
	Return value:  True if number is not prime.  False if prime.  Sets @Error to 1 if not an integer.
	Notes:
#ce
Func NotPrime(Const $nValue)
	Local $nTest
	
	If IsNumber($nValue) = 0 Then
		Return False
	ElseIf IsInt($nValue) = 0 Then
		Return False
	ElseIf $nValue < 2 Then
		; Lowest prime is two.  Smaller numbers do not qualify.
		Return True
	EndIf
	For $nTest = 2 To Int(Sqrt($nValue))
		If Mod($nValue, $nTest) = 0 Then
			; Has a factor of $nTest.  Composite!
			Return True
		EndIf
	Next
	Return False	; Is Prime
EndFunc   ;==>NotPrime

#cs
	Function:  HashPos
	Purpose:  Give the position to look for the given key in the hash table.
	Parameters:
	$sKey:  The key value in the hash table
	$nSize:  The size of the hash table to work with.
	Return value:  True if number is not prime.  False if prime.  Sets @Error to 1 if not an integer.
	Notes:
#ce
Func HashPos(Const $sKey, Const $nSize)
	Local $nPos = 0, $i
	
	For $i = 1 To StringLen($sKey)
		$nPos = $nPos + Asc(StringMid($sKey, $i, 1)) * $i
	Next
	$nPos = Mod($nPos, $nSize)
	If $nPos = 0 Then $nPos = 1	; Skip over housekeeping values
	Return $nPos
EndFunc   ;==>HashPos

Share this post


Link to post
Share on other sites

Posted (edited)

hi, tHanks,

Are you saying that is quicker than "@Condoman in post #3?

Best, randall

PS - Could you possibly show quick usage example? - thanks

Edited by randallc

Share this post


Link to post
Share on other sites

Posted

I've done something similar to Nutster's solution, but didn't use a hash function for the look up. This post has the file to download, and it uses a simple 2 element array to hold the data, with the 1st element a string, and the second element another array that contains all values. Keys are stored in order, with each key surrounded by the ESC character (not something anyone would use for a key normally). Lookups are done using a method of StringInStr() and StringReplace(), so lookups are however fast that is for strings. I use it, and I only notice it slow down on adding entries when it's already large, but it still seems fast enough for my purposes. Obvious limits are size of string and number of array elements.

Share this post


Link to post
Share on other sites

Posted

I've done something similar to Nutster's solution, but didn't use a hash function for the look up. This post has the file to download, and it uses a simple 2 element array to hold the data, with the 1st element a string, and the second element another array that contains all values. Keys are stored in order, with each key surrounded by the ESC character (not something anyone would use for a key normally). Lookups are done using a method of StringInStr() and StringReplace(), so lookups are however fast that is for strings. I use it, and I only notice it slow down on adding entries when it's already large, but it still seems fast enough for my purposes. Obvious limits are size of string and number of array elements.

Ok, thanks;

Could you also post an example of usage, just to get me started easily?

Thanks, Randall

Share this post


Link to post
Share on other sites

Posted

Function names are the same in one of Gary's posts where he made a wrapper function for the VBS object, but sure:

#include "Dictionary.au3"
$dict = _InitDictionary()

_AddItem($dict, "a", 123)
_AddItem($dict, "b", "Test")
_AddItem($dict, "c", "This couild be an array or any other object in AutoIt.")

If _ItemExists($dict, "a") Then
	MsgBox(0,"a",_Item($dict,"a")) ; If an Item isn't found, returns 0 with @error set to 1
EndIf

If _ItemExists($dict, "b") Then
	MsgBox(0,"Before",_Item($dict,"b"))
	_ChangeItem($dict, "b", "tEST")
	MsgBox(0,"After",_Item($dict,"b"))
EndIf

; You can also change keys with _ChangeKey($dict, "original", "new")

If _ItemExists($dict, "c") Then
	MsgBox(0, "Before",_ItemCount($dict))
	_ItemRemove($dict, "c")
	MsgBox(0, "After",_ItemCount($dict))
EndIf

$array = _GetItems($dict)
$keys = _GetKeys($dict)
For $i = 1 To $array[0]
	ConsoleWrite($keys[$i] & "=>" & $array[$i] & @CRLF)
Next

The library itself could use some more error checking, but it works for me.

Share this post


Link to post
Share on other sites

Posted

Thanks!

Although it is slower, this gives an esay Array-like syntax;

$timer = TimerInit()
$hash = ObjCreate("System.Collections.Hashtable")
For $i = 0 To UBound($aArray2) - 1
	$hash.add($aArray2[$i][0], $aArray2[$i][1])
Next
MsgBox(4096 + 64, "HashTest", "Your PC speaks " & $hash(@OSLang) & Round(TimerDiff($timer), 2))
;======================================================
$hash(@OSLang)="hi"
MsgBox(4096 + 64, "HashTest", "Your PC speaks " & $hash(@OSLang) & Round(TimerDiff($timer), 2))
;======================================================
(apology to whoever wrote it ? gary or Ptrex?)

So attached are comparisons with post #3 except nutser's which i Can't get working..

Best, randall

Share this post


Link to post
Share on other sites

Posted

Hello guys,

I see the thread grown a bit. I will try Nutster solution but i don't expect miracles. I even built myself kind of simple hash with the least error checking as possible, no collision detection or anything and yet it's very slow for me. Takes about 6 minutes to put 17000 records into it (reading from file). I guess the ReDim is problem here and if i would define it at the begining it would be much faster. Search thru that array is very fast, just adding takes ages :) I would love to have those hash functions built in as it would be probably much more efficient (just like with DllCallBack).

#include <array.au3>

Global $hardware_array

$hardware_array = _SpecialArrayDefine($hardware_array)
_SpecialArrayAdd($hardware_array, "1111", "MyID")
_SpecialArrayAdd($hardware_array, "1112", "SomethingElse")
_SpecialArrayAdd($hardware_array, "1113", "1SomethingElse")
$test_value = _SpecialArraySearch($hardware_array, "1113", 1)

; Checking if it works :)
ConsoleWrite(@CR & $test_value)
_ArrayDisplay($hardware_array)
; End of checking


Func _SpecialArraySearch(ByRef $avArray, $avArraySearchElement, $avArrayReturnColumn)
    Local $a
    If IsArray($avArray) Then
        For $a = 1 To UBound($avArray) - 1
            If $avArray[$a][0] = $avArraySearchElement Then
                Return $avArray[$a][$avArrayReturnColumn]
            EndIf
        Next
    EndIf
    SetError(1)
    Return -1
EndFunc   ;==>_SpecialArraySearch
Func _SpecialArrayDefine(ByRef $avArray)
    Dim $avArray[1][2]
    $avArray[0][1] = UBound($avArray, 2)
    $avArray[0][0] = UBound($avArray)
    Return $avArray
EndFunc   ;==>_SpecialArrayDefine
Func _SpecialArrayAdd(ByRef $avArray, $avArrayElement, $avArrayValue)
    If IsArray($avArray) Then
        ReDim $avArray[UBound($avArray) + 1][2]
        $avArray[UBound($avArray) - 1][0] = $avArrayElement
        $avArray[UBound($avArray) - 1][1] = $avArrayValue
        $avArray[0][0] = UBound($avArray) - 1
    Else
        SetError(1)
        Return -1
    EndIf
    Return $avArray
EndFunc   ;==>_SpecialArrayAdd

With regards,

MadBoy

Share this post


Link to post
Share on other sites

Posted

I have now did one more test this time without ReDim but with known amount of elements. And it's a LOT faster. So we know that ReDiming is bottlneck in here :)

Test results:

Array Creation time - Test 1 - 368.474205520534

Array Creation time - Test 2 - 430427.323305057

Search for 1SomethingElse in 0.160914306147848

#include <array.au3>

Global $hardware_array
Global $hardware_array_bis[17000][2]

; Fastest solution but requires knowledge on amount of elements:
$timea1 = TimerInit()
For $a = 1 To 16999
    _SpecialArrayAddBis($hardware_array_bis, $a, "MyID" & $a, $a)
Next
ConsoleWrite(@CR & "Array Creation time - Test 1 - " & TimerDiff($timea1))
_ArrayDisplay($hardware_array_bis)

; Slowest solution, doesn't require knowledge on amount of elements:
$timea2 = TimerInit()
$hardware_array = _SpecialArrayDefine($hardware_array)
_SpecialArrayAdd($hardware_array, "1111", "MyID")
_SpecialArrayAdd($hardware_array, "1112", "SomethingElse")
_SpecialArrayAdd($hardware_array, "1113", "1SomethingElse")
For $a = 1 To 17000
    _SpecialArrayAdd($hardware_array, $a, "MyID" & $a)
Next
ConsoleWrite(@CR & "Array Creation time - Test 2 - " & TimerDiff($timea2))
_ArrayDisplay($hardware_array)

; Search solution, quite fast
$timea3 = TimerInit()
$test_value = _SpecialArraySearch($hardware_array, "1113", 1)
ConsoleWrite(@CR & "Search for " & $test_value & " in " & TimerDiff($timea3) & @CRLF)

Func _SpecialArraySearch(ByRef $avArray, $avArraySearchElement, $avArrayReturnColumn)
    Local $a
    If IsArray($avArray) Then
        For $a = 1 To UBound($avArray) - 1
            If $avArray[$a][0] = $avArraySearchElement Then
                Return $avArray[$a][$avArrayReturnColumn]
            EndIf
        Next
    EndIf
    SetError(1)
    Return -1
EndFunc   ;==>_SpecialArraySearch
Func _SpecialArrayDefine(ByRef $avArray)
    Dim $avArray[1][2]
    $avArray[0][1] = UBound($avArray, 2)
    $avArray[0][0] = UBound($avArray)
    Return $avArray
EndFunc   ;==>_SpecialArrayDefine
Func _SpecialArrayAddBis(ByRef $avArray, $avArrayElement, $avArrayValue, $avArrayPredefinedPosition)
    $avArray[$avArrayPredefinedPosition][0] = $avArrayElement
    $avArray[$avArrayPredefinedPosition][1] = $avArrayValue
EndFunc   ;==>_SpecialArrayAddBis
Func _SpecialArrayAdd(ByRef $avArray, $avArrayElement, $avArrayValue)
    If IsArray($avArray) Then
        ReDim $avArray[UBound($avArray) + 1][2]
        $avArray[UBound($avArray) - 1][0] = $avArrayElement
        $avArray[UBound($avArray) - 1][1] = $avArrayValue
        $avArray[0][0] = UBound($avArray) - 1
    Else
        SetError(1)
        Return -1
    EndIf
    Return $avArray
EndFunc   ;==>_SpecialArrayAdd

Share this post


Link to post
Share on other sites

Posted (edited)

Hi,

Madboy, I can speed yours up a lot;

1. As you say, eliminate the redim.

2. Read File to 2D Array much faster; use my UDF for Array2D

[removed scripts as slow after all...] But then I thin having "inbuilt" hash will nor be much faster, because you will always have to read file into 2D Array, which is the slowest part; so unless that is improved, the hash can't go much faster, I suspect.

Best, randall

Edited by randallc

Share this post


Link to post
Share on other sites

Posted

Hi,

Madboy, I can speed yours up a lot;

1. As you say, eliminate the redim.

2. Read File to 2D Array much faster; use my UDF for Array2D

3. [above 2 are incorporatd in the following script example, using your post #4 example of file; I can speed the "Dictionary2.au3" even faster using vbs if you want and prepared to try it and give feedback.]

; HashTest3.au3

;~ #include "HashShanks.au3"
#include "Dictionary2.au3"; modified from @SkinnyWhiteGuy
;~ #include "Dictionary.au3"
;~ #include "HashTableMS.au3"
#include "Array2D.au3" ;[comment out or delete all lines , UDF in my sig, after about 769 "#Cs; Func _hndButton_Array1Box_Transpose"]
;~ #include "assocArrayHashPrimeNutster.au3"

;======================================================
local $data, $sFileCsv=@ScriptDir&"\arraytester.csv"
Local $aArray[1][1], $aArray1 ;= StringSplit($data, ":")
$fileRead=StringReplace(StringReplace(FileRead($sFileCsv),"=",","),"[",",,")
$aArray1 = StringSplit($fileRead, @CRLF,1)
_ArrayDisplay($aArray1)
Local $aArray2 = _Array2DCreateFromArraySt($aArray1, 1, 0, ",")
_ArrayDisplay($aArray2)
;======================================================
$timer = TimerInit()
$dict = _InitDictionaryArray($aArray2)
For $i = 0 To UBound($aArray2) - 1
    _AddItemArray($dict, $aArray2[$i][1], $aArray2[$i][2])
Next
MsgBox(4096 + 64, "HashTest", "Your PC speaks " & _Item($dict, "AmdShpc_Inst32") & Round(TimerDiff($timer), 2))
But then I thin having "inbuilt hash will nor be much faster, because you will always have to read file into 2D Array, which is the slowest part; so unless that is improved, the hash can't go much faster, I suspect.

Best, randall

Thanks, i will try it. However i think my simple function _SpecialArrayAddBis will do for this little project of mine that i need it for. I just need to know amount of elements in the array prior to adding. All in all i would love to see hashes incorporated :)

Share this post


Link to post
Share on other sites

Posted

Thanks, i will try it. However i think my simple function _SpecialArrayAddBis will do for this little project of mine that i need it for. I just need to know amount of elements in the array prior to adding. All in all i would love to see hashes incorporated :)

Hi,

Yes, I see my version is still slow for large files; I thought SkinnyWhiteGuy 's version would be fast

Oh well.

Best, Randall

Share this post


Link to post
Share on other sites

Posted

As did I, but it wasn't as fast as I'd hoped, and I think I know why. Somewhere on the forum is a post from the Dev who wrote the initial Array code, including ReDim, and he says that ReDim makes things go real slow because of the way it has to work (internally copying all the data from the old array to a new array of the correct size, etc...). His suggestion was to only ReDim every so often, and in large chunks. I couldn't figure out how to do that in my functions, so I didn't worry so much about it. Since the ReDim is the bottleneck (as you two found), it just goes to show the problem with trying to use dynamically increasing arrays like this. I had another solution, but it didn't work on the project I was working on. Here that one is, for you to play with (based on the Wikipedia article for hash tables).

New_Hash.au3

Share this post


Link to post
Share on other sites

Posted

There are two main tricks to avoiding array resizing. First, take a hint in the creation function which specifies an initial size (This should be optional and default to something small). For example, if I have an idea I'm going to be working with 1000+ elements, I would specify 1000 as the hint. The function would then initially allocate the array with 1000 elements. The second trick is to grow by 1.3x the size of the array when you need to grow. The value 1.3 is a common growth factor.

Share this post


Link to post
Share on other sites

Posted

There are two main tricks to avoiding array resizing. First, take a hint in the creation function which specifies an initial size (This should be optional and default to something small). For example, if I have an idea I'm going to be working with 1000+ elements, I would specify 1000 as the hint. The function would then initially allocate the array with 1000 elements. The second trick is to grow by 1.3x the size of the array when you need to grow. The value 1.3 is a common growth factor.

So i went with this idea and decided to check how it goes. It doesn't use ReDim at all. It simply uses _SpecialArrayUbound to know where to put next element in array (checks for empty place in array and sets $array[0][0])

Result isn't satisfying:

Array Creation time - Test 1 - 450314.424878022

Global $my_array

$timea1 = TimerInit()
_SpecialArrayDefine($my_array, 100000)
For $c = 1 To 16999
    _SpecialArrayAdd($my_array, $c, "Id for " & $c)
Next
ConsoleWrite(@CR & "Array Creation time - Test 1 - " & TimerDiff($timea1))

$answer = _SpecialArraySearch($my_array, "33", 1)
MsgBox(0,"Search Test", $answer)

; FUNCTIONS
Func _SpecialArrayDefine(ByRef $avArray, $avArrayElements)
    Dim $avArray[$avArrayElements][2]
    $avArray[0][1] = UBound($avArray, 2)
    $avArray[0][0] = _SpecialArrayUbound($avArray)
    Return $avArray
EndFunc   ;==>_SpecialArrayDefine
Func _SpecialArrayUbound($avArray)
    Local $a
    For $a = 1 To UBound($avArray) - 1
        If $avArray[$a][0] = "" Then Return $a
    Next
EndFunc   ;==>_SpecialArrayUbound
Func _SpecialArrayAdd(ByRef $avArray, $avArrayElement, $avArrayValue)
    $avArray[$avArray[0][0]][0] = $avArrayElement
    $avArray[$avArray[0][0]][1] = $avArrayValue
    $avArray[0][0] = _SpecialArrayUbound($avArray)
EndFunc   ;==>_SpecialArrayAdd
Func _SpecialArraySearch(ByRef $avArray, $avArraySearchElement, $avArrayReturnColumn)
    Local $a
    If IsArray($avArray) Then
        For $a = 1 To _SpecialArrayUbound($avArray) - 1
            If $avArray[$a][0] <> "" Then
                If $avArray[$a][0] = $avArraySearchElement Then
                    Return $avArray[$a][$avArrayReturnColumn]
                EndIf
            Else
                SetError(1)
                Return -1
            EndIf
        Next
    EndIf
    SetError(1)
    Return -1
EndFunc   ;==>_SpecialArraySearch
;END FUNCTIONSoÝ÷ Ù8^¢yr¢Ø^®'^j+-¢ë²i×b¶*'j[Ú®&ì!Èp¢é]ë-究¶^­ëazw±µé©·'¥zg§¶+"Ø^+-N«zË¥¶+)­ç­Êxz«¨µà+­¬­æ­ígzËuãOuó4ïyãÏêº^jëh×6#include <array.au3>

Global $my_array
Global $special_value = 1

$timea1 = TimerInit()
_SpecialArrayDefine($my_array, 100000)
For $c = 1 To 16999
    _SpecialArrayAdd($my_array, $c, "Id for " & $c)
Next
_SpecialArrayUbound($my_array)
ConsoleWrite(@CR & "Array Creation time - Test 1 - " & TimerDiff($timea1))

_ArrayDisplay($my_array)
$answer = _SpecialArraySearch($my_array, "33", 1)
MsgBox(0,"Search Test", $answer)

; FUNCTIONS
Func _SpecialArrayDefine(ByRef $avArray, $avArrayElements)
    Dim $avArray[$avArrayElements][2]
    $avArray[0][1] = UBound($avArray, 2)
    $avArray[0][0] = _SpecialArrayUbound($avArray)
    Return $avArray
EndFunc   ;==>_SpecialArrayDefine
Func _SpecialArrayUbound(ByRef $avArray)
    Local $a
    For $a = 1 To UBound($avArray) - 1
        If $avArray[$a][0] = "" Then
            $avArray[0][0] = $a
            Return $a
        EndIf
    Next
EndFunc   ;==>_SpecialArrayUbound
Func _SpecialArrayAdd(ByRef $avArray, $avArrayElement, $avArrayValue)
    $avArray[$special_value][0] = $avArrayElement
    $avArray[$special_value][1] = $avArrayValue
    $special_value += 1
EndFunc   ;==>_SpecialArrayAdd
Func _SpecialArraySearch(ByRef $avArray, $avArraySearchElement, $avArrayReturnColumn)
    Local $a
    If IsArray($avArray) Then
        For $a = 1 To _SpecialArrayUbound($avArray) - 1
            If $avArray[$a][0] <> "" Then
                If $avArray[$a][0] = $avArraySearchElement Then
                    Return $avArray[$a][$avArrayReturnColumn]
                EndIf
            Else
                SetError(1)
                Return -1
            EndIf
        Next
    EndIf
    SetError(1)
    Return -1
EndFunc   ;==>_SpecialArraySearch
;END FUNCTIONS

Share this post


Link to post
Share on other sites

Posted

As did I, but it wasn't as fast as I'd hoped, and I think I know why. Somewhere on the forum is a post from the Dev who wrote the initial Array code, including ReDim, and he says that ReDim makes things go real slow because of the way it has to work (internally copying all the data from the old array to a new array of the correct size, etc...). His suggestion was to only ReDim every so often, and in large chunks. I couldn't figure out how to do that in my functions, so I didn't worry so much about it. Since the ReDim is the bottleneck (as you two found), it just goes to show the problem with trying to use dynamically increasing arrays like this. I had another solution, but it didn't work on the project I was working on. Here that one is, for you to play with (based on the Wikipedia article for hash tables).

Hi,

You will see that i had eliminated redim in "dictionary2.au3", but it was still slow; I think it might be because you were using an array to hold an array too, and repeatedly refinig that; I don't think autoIt likes that for speed; see warning in Helpfile)

Best, randall

Share this post


Link to post
Share on other sites

Posted (edited)

So i went with this idea and decided to check how it goes. It doesn't use ReDim at all. It simply uses _SpecialArrayUbound to know where to put next element

Good work!

For your precise problem, you have your answer.

If you already have written your file, it might be faster to use RegExp on the file, as you only need to read the file to a string, not to an array at all;

Then the file read is only about 80msecs,

The search is faster [unless, as with "1131", it is at the beginning of your array], usually about 30msecs wherever in the file.

Best, Randall

; HashTest6.au3
#include<_ArrayRegExp.au3>
Local $aArrayfile[17000], $sStringFile, $aArray1 ;= StringSplit($data, ":")
$sFileCsv2 = @ScriptDir & "\arraytester2.csv"
;======================================================
;~ For $i = 0 To 17000-1
;~ 	$aArrayfile[$i]=",Key"&$i&",Value"&$i
;~ Next
;~ _FileWriteFromArray($sFileCsv2,$aArrayfile)
;======================================================
$timer = TimerInit()
$fileRead = StringReplace(StringStripCR(FileRead($sFileCsv2)), ",", "|")
ConsoleWrite("Read;" & Round(TimerDiff($timer), 2) & "msecs" & @LF)
$timer2 = TimerInit()
Local $sValue = _HashValue($fileRead, "Key11131", 1, 2); _HashValue(ByRef $sStringFile, $sKey, $KeyColumn, $ValColumn)
ConsoleWrite("$sValue=" & $sValue & @LF)
ConsoleWrite("Just Find ;" & Round(TimerDiff($timer2), 2) & "msecs" & @LF)

Func _HashValue(ByRef $sStringFile, $sKey, $KeyColumn, $ValColumn)
	Local $arStrings = _ArrayRegExp($sStringFile, $sKey, $KeyColumn);_FindLinesRegExp($s_FileF, $s_Searches, $i_Column = 0,  $i_Case = 0)
	If Not IsArray($arStrings) Or Not StringInStr($arStrings[0], "|") Then Return 0
	For $i = 0 To UBound($arStrings) - 1
		$aArrayTemp = StringSplit($arStrings[$i], "|")
		If $aArrayTemp[$KeyColumn+1] == $sKey Then Return $aArrayTemp[$ValColumn+1]
	Next
	Return 0
EndFunc   ;==>_HashValue
Edited by randallc

Share this post


Link to post
Share on other sites

Posted

Well, building off of what Valik said about avoiding ReDimming constantly, and randallc's point about Arrays in arrays, I have created the following. All function calls are the same, but the internals are a bit different, and the _InitDictionary() function now has an optional parameter that you can use to set the size of the array before using it (it defaults to 1000 currently), and if it needs to grow, it grows by 1.3. I'm still testing this (first test I ran in the application I'm mainly using it in now actually ran slower than my older one), so I'm not sure if all the logic errors are worked out, but they seem to be for the most part working just like earlier.

Dictionary.au3

Share this post


Link to post
Share on other sites

Posted

Somewhere on the forum is a post from the Dev who wrote the initial Array code, including ReDim, and he says that ReDim makes things go really slow because of the way it has to work (internally copying all the data from the old array to a new array of the correct size, etc...). His suggestion was to only ReDim every so often, and in large chunks.

That Dev would be me. In any programming language, you want to minimize the number of the time you have to resize and reassign data structures; this is always a significant time waster.

As I said in my prior post, I did not test the code I posted, beyond Syntax Checker and Tidy not complaining. I should have time this weekend (maybe even tonight) to test it and build an example exerciser using the functions I posted and will post the whole thing in Example Scripts once it is working.

Share this post


Link to post
Share on other sites

Posted

I thought it was you (avatar reminded me), but wasn't completely sure (someone else had that one at one time). I hope your tests go well as mine did.

Share this post


Link to post
Share on other sites
Sign in to follow this  
Followers 0