Help with best way to do this function

[Champak]

I need help with how to attack the following function.

FIRST:

I have a listview. When I click a particular cell I want it to activate a function that will look in a 1D array at all the numbers contained in it. I then want it to seek out the lowest number that is NOT in the array, and if there is no number available then increment by one based on the max number, and then populate the listview cell with that number, and then also insert that number into the array, so now the next time I go through the process this number it just found/added wont be available. 

Or another thought if there is away to populate another array with all the missing numbers in the first array.

This is going to be a critical function and I don't know the best way to go about searching for the lowest number that isn't in the array. Right now my thought is to do a loop based on the array count and then cycle through like this:

$j = 0
$addnumber = true

for $i = 0 to uboundarray

    if $i <> $j then 
        NumberFound()
        $addnumber = false
    endif
    
    $j += 1
    
next

if $addnumber = true then AddNumber()

The array of numbers is coming from a database and will be sorted already.

The issue and function seems simple enough and this seems to be good enough, but could this fail in some way, or is there a faster way (the array will be getting up in 20000+)?

SECOND

Every time my app loads it will be getting these numbers from a remote database where things may be added (not while I'm processing), so I need a way to store the numbers that I've added locally while I'm editing. That way when the app loads and grabs the numbers from the database, it will see that I've added numbers locally so it will disgard the remote numbers and work of the local ones. Usually I would use the registry to store this info, but I don't know if the reg_multi_sz can hold 20000+ entries, and I also don't want to be bothered with the @LF cycling to save things off every entry. What other way efficient way could I use to store the info locally besides msqlite...don't want something that requires another program?

Edited May 17, 2023 by Champak

[sylremo]

FIRST question: If you are asking about how to add/search elements on a large array without slowing down, then yes, there are many topics around the forum. But if I were you, at least I would avoid using Redim.

SECOND question: if you don't want to use SQLite, CSV would be an Ok alternative, I guess.

tbh, idk why with so many posts you've asked, you still seem to have trouble explaining the problem, I assumed, because I literally have to use paraphrase tool to get a grip on what you're trying to say. If English isn't your first language, try using a translator and then replacing any words that shouldn't be translated, like me back in the day. That should do the trick. Have a nice day.

[Andreik]

Arrays can be slow in AutoIt, why not implementing this in a database, where querying 20k records is a trivial task and you can easily search for minimum or maximum?

[Champak]

Thanks, I didn't want to implement the database because I want to keep the footprint of the app as small as possible not requiring the install of another app. Also as far as the database doing the search, I'm not aware of the minimum function working in the way I need. I need to find the "minimum" number NOT in the array, as opposed to finding the minimum number present (the way I believe it works). Ex. (1, 2, 4, 5, 6, 7 ) I need to find 3, not 1.

[ioa747]

  

3 hours ago, Champak said:

Ex. (1, 2, 4, 5, 6, 7 ) I need to find 3, not 1

 

#include <Array.au3>

Global $aArray[6] = [1, 2, 4, 5, 6, 7]
;~ _ArrayDisplay($aArray)

ConsoleWrite("LowestNumber:" & LowestNumber() & @CRLF)


;----------------------------------------------------------------------------------------
Func LowestNumber()
    Local $iMax = _ArrayMax($aArray, 1, 0, -1, 1)
    For $n = 1 To $iMax + 1 ; +1 in case doesn't find someone in between
        If _FindThis($n) < 0 Then
            Return $n
        EndIf
    Next
EndFunc   ;==>LowestNumber
;----------------------------------------------------------------------------------------
Func _FindThis($n)
    Local $sIndex
    For $i = 0 To UBound($aArray) - 1
        $sIndex = -1
        If $aArray[$i] = $n Then
            $sIndex = $i
            ExitLoop
        EndIf
    Next
    Return $sIndex
EndFunc   ;==>_FindThis
;----------------------------------------------------------------------------------------

 

Edited May 20, 2023 by ioa747
corection

[Andreik]

3 hours ago, Champak said:

Thanks, I didn't want to implement the database because I want to keep the footprint of the app as small as possible not requiring the install of another app. Also as far as the database doing the search, I'm not aware of the minimum function working in the way I need. I need to find the "minimum" number NOT in the array, as opposed to finding the minimum number present (the way I believe it works). Ex. (1, 2, 4, 5, 6, 7 ) I need to find 3, not 1.

SQLite is more than light and with a basic query you are done.

SELECT MIN(number) + 1 FROM table_name WHERE number + 1 NOT IN (SELECT number FROM table_name)

 

[Andreik]

Or maybe some low level code:

expandcollapse popup

#include <WinAPIDiag.au3>

Global $hListView, $cListView
Global $tData = DllStructCreate('int Data[20000]')

$hMain = GUICreate('Sample code', 400, 400)
$cListView = GUICtrlCreateListView('Numbers', 10, 10, 380, 380, 0x0C, 0x21) ; LVS_SINGLESEL, LVS_SHOWSELALWAYS, LVS_EX_GRIDLINES, LVS_EX_FULLROWSELECT
$hListView = GUICtrlGetHandle($cListView)
GUISetState(@SW_SHOW, $hMain)

FillStruct($tData)
LoadSomeTestNumbers($cListView, $tData)

GUIRegisterMsg(0x004E, 'WM_NOTIFY')

Do
    Sleep(10)
Until GUIGetMsg() = -3 ; GUI_EVENT_CLOSE

Func WM_NOTIFY($hWnd, $iMsg, $wParam, $lParam)
        #forceref $hWnd, $iMsg, $wParam
        Local $tNMHDR = DllStructCreate($tagNMHDR, $lParam)
        Local $iCode = DllStructGetData($tNMHDR, "Code")
        If $hListView = HWnd(DllStructGetData($tNMHDR, "hWndFrom")) And $iCode = -2 Then    ; NM_CLICK
            Local $tNMITEMACTIVATE = DllStructCreate($tagNMITEMACTIVATE, $lParam)
            ; When I click a particular cell (let's say 4th cell of the listview)
            If DllStructGetData($tNMITEMACTIVATE, 'Index') = 3 Then
                Local $Minimum = GetMinimum($tData)
                GUICtrlCreateListViewItem($Minimum, $cListView)
                WriteNumber($tData, $Minimum)
            EndIf
        EndIf
        Return 'GUI_RUNDEFMSG'
EndFunc

Func LoadSomeTestNumbers($cListView, $tStruct)
    Local $aNumbers[10] = [15, 1, 6, 5, 7, 9, 3, 8, 12, 25]
    For $Index = 0 To 9
        GUICtrlCreateListViewItem($aNumbers[$Index], $cListView)
        WriteNumber($tData, $aNumbers[$Index])
    Next
EndFunc

Func FillStruct($tStruct)
    Local $Code = Binary('0x8B7424048B4C2408C706FFFFFFFF83C604E2F5C20800')
    Local $iSize = BinaryLen($Code)
    Local $tCode = DllStructCreate('byte Code[' & $iSize & ']')
    DllStructSetData($tCode, 'Code', $Code)
    Local $aCall = DllCallAddress('int', DllStructGetPtr($tCode), 'ptr', DllStructGetPtr($tStruct), 'int', DllStructGetSize($tStruct) / 4)
EndFunc

Func GetMinimum($tStruct)
    Local $Code = Binary('0x8B7424048B4C240831D2AD39D07404E2F9EB0B8B7424048B4C240842EBEC89D0C20800')
    Local $iSize = BinaryLen($Code)
    Local $tCode = DllStructCreate('byte Code[' & $iSize & ']')
    DllStructSetData($tCode, 'Code', $Code)
    Local $aCall = DllCallAddress('int', DllStructGetPtr($tCode), 'ptr', DllStructGetPtr($tStruct), 'int', DllStructGetSize($tStruct) / 4)
    Return $aCall[0]
EndFunc

Func WriteNumber($tStruct, $Minimum)
    Local $Code = Binary('0x8B7424048B4C24088B54240CAD83F8FF7409E2F8B8FFFFFFFFEB088956FCB800000000C20C00')
    Local $iSize = BinaryLen($Code)
    Local $tCode = DllStructCreate('byte Code[' & $iSize & ']')
    DllStructSetData($tCode, 'Code', $Code)
    Local $aCall = DllCallAddress('int', DllStructGetPtr($tCode), 'ptr', DllStructGetPtr($tStruct), 'int', DllStructGetSize($tStruct) / 4, 'int', $Minimum)
    Return $aCall[0]
EndFunc

On my PC to get (and then write) 10 minimum integers on a reserved memory that holds 20k integers take less then 1 ms. Is that fast enough?

 

Edited May 20, 2023 by Andreik
Updated code with example.

[Champak]

Beautiful, thank you. If it reaches the point where the array ever gets slow, I'll go ahead and switch over to the database, thank you for that...great manipulation there.

[Andreik]

In case you ever want to customize these functions (maybe modifying to start from 1 as minimum, not from 0) here is the code for assembly functions.

expandcollapse popup

[Fill struct]
mov esi, [esp + 4]
mov ecx, [esp + 8]
next:
mov dword[esi], 0FFFFFFFFh
add esi, 4
loop next
ret 8

[Find minimum]
mov esi, [esp + 4]
mov ecx, [esp + 8]
xor edx, edx
next:
lodsd
cmp eax, edx
je increase
loop next
jmp exit
increase:
mov esi, [esp + 4]
mov ecx, [esp + 8]
inc edx
jmp next
exit:
mov eax, edx
ret 8

[Write minimum]
mov esi, [esp + 4]
mov ecx, [esp + 8]
mov edx, [esp + 0Ch]
next:
lodsd
cmp eax, 0FFFFFFFFh
je update
loop next
mov eax, 0FFFFFFFFh
jmp exit
update:
mov dword[esi-4], edx
mov eax, 0
exit:
ret 12

 

[pixelsearch]

@Andreik nicely done, though I don't understand a single word in assembly language

I wanted to make sure that your code really compared each and every element of the [20000] array (as it's so fast !) so this is what I did, on a smaller array (40 elements => structure $tdata is now 160 bytes length)

; Global $tData = DllStructCreate('int Data[20000]') ; structure is 80.000 length (4 * 20000)
Global $tData = DllStructCreate('int Data[40]') ; structure is 160 length (4 * 40)

When we create the structure, it's filled with 0's (normal behavior) then your function FillStruct() immediately replaces all 0's with 0xFF, so far so good.

1) Normal Andreik script (smaller struct for the pics)



Upper part of the pic : the 10 tests numbers have been added to the structure, e.g [15, 1, 6, 5, 7, 9, 3, 8, 12, 25] . First one (15) is 0x0F 00 00 00 and last one (25) is 0x19 00 00 00 . We also notice that 0 and 2 are not part of tests numbers.

Lower part of the pic, left side : 1st clic on 3rd row (e.g. 4th element) in LV and 0x00 00 00 00 is correctly added in the structure

Lower part of the pic, right side : 2nd clic in LV and 0x02 00 00 00 is correctly added in the structure. From now on, it would be the same pattern after each click (I got another pic where 0x04 00 00 00 is correctly added etc...)

To make sure that the script didn't stop the search when the 1st 0xFF FF FF FF is quickly found (and apart from checking the assembly code), this is what I did :

2) Altered Andreik script (added 0 at end of struc)



I added 1 line to the script, at the very end of the LoadSomeTestNumbers function :

DllStructSetData($tData, 'Data', 0, 40) ; write 0x00 in last element [40] replacing 4 last 0xFF with 4 0x00

Which means that before the 1st click in LV, there is now an additional "test number" 0x00 (placed at the very end of the structure). What will be the value displayed in LV after the 1st click (e.g returned from the assembly function GetMinimum), will it be 0 or 2 ?

The answer is 2, as shown in LV and on the right side of the pic. So yes, all elements of the array have been correctly checked (40 in my case, 20.000 in the original script), well done Andreik

[Andreik]

Glad you made the test and you got your answer. It's a naive approach but I will explain anyway how I got this to work.

FillStruct is straight forward and fill the entire structure with 0xFFFFFFFF (or -1 if we talk about signed integers). It's some kind of initialization of the array.

FindMinimum check if a given number is already saved in the structure. How it does that? It starts from 0 and compare each 4 bytes (an integer) if it's equal with zero. If 0 is found somewhere in that array, it means 0 it's not the minimum so will increase the number by one and starts again from the beginning of the struct and go through the same process and check every single integer in the structure. If that number is not found anywhere, it means we got the minimum value.

WriteNumber basically check for the first "empty/unwritten" integer with value 0xFFFFFFFF and write the value at that address.

Edited May 23, 2023 by Andreik

[pixelsearch]

@Andreik you wrote that it was possible to start from 1 as minimum (instead of 0) . I tried it and it seems to work. This is what I did :

1) Here is the original assembly code you indicated in your post, I tried manually to match the binary code as found in the string of your script, so each assembly instruction got its binary code on same line :

[Find minimum]
mov esi, [esp + 4]   8B 74 24 04
mov ecx, [esp + 8]   8B 4C 24 08
xor edx, edx         31 D2
next:
lodsd                AD
cmp eax, edx         39 D0
je increase          74 04
loop next            E2 F9
jmp exit             EB 0B
increase:
mov esi, [esp + 4]   8B 74 24 04
mov ecx, [esp + 8]   8B 4C 24 08
inc edx              42
jmp next             EB EC
exit:
mov eax, edx         89 D0
ret 8                C2 08 00

2) As "xor edx, edx" clears the edx register, if we add immediately after "inc edx" then it should start from 1 :

...
xor edx, edx         31 D2
inc edx              42
next:
lodsd                AD
...

As this byte (0x42) will be gladly placed before the 1st label ("next:") then we shouldn't worry of any jump or loop offsets found in the code. This is the change done in the AutoIt script :

; Local $Code = Binary('0x8B7424048B4C240831D2AD39D07404E2F9EB0B8B7424048B4C240842EBEC89D0C20800') ; original code

; Local $Code = Binary('0x8B7424048B4C240831D2' & _
;   'AD39D07404E2F9EB0B8B7424048B4C240842EBEC89D0C20800') ; original code (splitted on 2 lines)

Local $Code = Binary('0x8B7424048B4C240831D2' & _
    '42' & _
    'AD39D07404E2F9EB0B8B7424048B4C240842EBEC89D0C20800') ; added 1 byte 0x42 (so minimum checked starts on 1 and not on 0)

When we run this altered script, the 1st minimum found is 2 and no more 0 (as displayed in LV after the 1st click) so it seems to work. If you think something is wrong, please be kind to indicate it, thanks
Edited May 24, 2023 by pixelsearch
typo

[Andreik]

Ha ha, it's true but there is not necessary to increase edx with 1, why not simply mov edx, 1? I used xor edx, edx instead of mov edx, 0 to gain (I think) 1 CPU cycle and 3 bytes of code less, which is not much but in old times when CPUs where slower and PCs with less memory available, it was a good practice. This is why I am more accustomed to use this instruction when I want to clear a register. Even if what you tried needs just 3 bytes of code, for readability, I would simply replace xor edx, edx with mov edx, 1, without adding inc edx. Hope this explanation help.

PS: Also if I would start to search from 1, probably it would make much sense to initialize the structure with all integers equals to zero

PSS: your previous statement that you don't know a thing about asm it's a pure lie or your learning curve it's steep

 

Edited May 24, 2023 by Andreik
typo

[pixelsearch]

I can repeat 10 times : I don't know anything about asm

Since yesterday, I went on different web pages to retrieve the meaning of the asm instructions (and their binary code) found in your code. Also the indications you gave in your "bulldozer" thread were useful, as you showed the binary code of some lines of asm code.

For example, for the jump and loop instructions, it's not hard to understand that a count of bytes (to move forward or backward) is indicated near the instruction etc...

This reminds me when, more than a year ago, a guy was here on the Forum with his C code that sorted at the speed of light (that guy isn't here any more as he had bad words concerning AutoIt). As I didn't know anything about C/C++ and I wanted to be able to understand what he did, then I started to learn C++ from scratch. 4 weeks after, with the help of plenty of web pages (I still got the endless list of these web pages !) I was able to script a C++ code found in this post and I use it since then, as a dll, for sorting any AutoIt array (also those used in ArrayDisplay) 10 times faster. That's useful on old computers.

Now I forgot everything about C++ . It was my 1st and last experience with it

[Andreik]

12 minutes ago, pixelsearch said:

I can repeat 10 times : I don't know anything about asm

Just use a loop.

[pixelsearch]

Should it start from 0 or 1 ?

[Andreik]

As long you print the message 10 times, you choose the index.

[RTFC]

A different approach:

expandcollapse popup

#NoTrayIcon
#include ".\Eigen4AutoIt.au3"

_Eigen_StartUp("int")
_Eigen_RanSeed(0)   ; 0 = use current date/time specs to seed the randomiser

Global $verbose=True    ; T: show console messages

Global $listsize=20000
Global $maxValue=30000
Global $bitmaskSize=$maxValue+1 ; to accommodate inclusive range [0,maxValue]
Global $missingValues, $totalMissingValues=-1, $indexMV=-1

; these will be resized later if need be
Global $bitmask =_Eigen_CreateMatrix_Zero($bitmaskSize,1)
Global $bitmask2=_Eigen_CloneMatrix($bitmask)

For $test=1 to 10
    If $verbose Then ConsoleWrite(@CRLF & "Test run: " & $test & @CRLF)

    ; generate some data
    _ImportNewNumbers($test=1)  ; T: initialise

    ; fill gaps / extend range
    For $rc=1 to 100
        $nextMissingValue=_UseNextMissingValue()
    Next
Next

_Eigen_CleanUp()


Func _ImportNewNumbers($init = False)
; process a list of integers
    If $verbose Then ConsoleWrite("Importing " & $listsize & " new values; please stand by..." & @CRLF)

    ; generate some fake data (mimicks importing actual data)
    Local $newlist=_Eigen_CreateMatrix_Random_Integer($listsize,1,0,$maxValue-1)    ; -1 due to minor bug in func (interprets range+1), will be fixed in next release

    ; update 1st/2nd bitmask (in 1st/subsequent call)
    _Eigen_CreateMask_FromOffsets($newlist,$bitmaskSize,1,False,(($init)?($bitmask):($bitmask2)))   ; F: do not invert the mask
    _Eigen_ReleaseMatrix($newlist)  ; done with this

    ; update master bitmask with new arrivals upon subsequent calls only
    If Not $init Then _Eigen_CwiseLogicalOp_InPlace($bitmask,"or",$bitmask2)

    ; create a new list of all remaining missing values
    _UpdateMissingValues(True)

EndFunc


Func _UpdateMissingValues($init = False)
; list all remaining zero entries (= absent in parsed data)

    $missingValues=_Eigen_FindAll($bitmask,0)   ; return all zero cell locations in bitmask
    $totalMissingValues=@extended
    $indexMV=(($init)?(-1):(0)) ; reset pointer

    If $verbose Then ConsoleWrite("Total remaining missing values: " & $totalMissingValues & @CRLF)

EndFunc


Func _UseNextMissingValue()
; use missing values or increase maxvalue; expand masks if needed

    $indexMV+=1
    If $indexMV>=$totalMissingValues Then
        _ExtendBitmasks()
        _UpdateMissingValues(False)
    EndIf

    Local $missingValue=_Eigen_ReadMatrixValue($missingValues,$indexMV,0)
    _Eigen_WriteMatrixValue($bitmask,$missingValue,0,1) ; punch-out

    If $verbose Then ConsoleWrite("Using next missing value: " & $missingValue & @CRLF)
    Return $missingValue
EndFunc


Func _ExtendBitmasks()
; doubles in size each time

    _Eigen_AppendRows_InPlace($bitmask,$bitmaskSize)    ; retain existing data; new rows contain zero
    _Eigen_ReleaseMatrix($bitmask2)         ; it's faster to create a new copy
    $bitmask2=_Eigen_CloneMatrix($bitmask)

    $maxValue=_Eigen_GetLastMatrixRow($bitmask)
    $bitmaskSize=_Eigen_GetMatrixRows($bitmask)

EndFunc

 

[Andreik]

Is there any way to download just Eigen4AutoIt.au3 or it's just a wrapper and I need to install something else?

[RTFC]

Just download and install from here; nothing else is needed. It's definitely not just a wrapper! I wrote the included dll's too, and the utilities,  tutorials, test scripts, and the extensive online Help.

The current installer stores it under C:\Program Files (x86?), but you can move the directory anywhere else after installing (just update the path in any script that includes it).

If upon first run an E4A script cannot find the path to the dll, open the Eigen4AutoIt.ini file in your script's current directory and change the DLLPATH variable to where you placed the main E4A directory (without final backslash).

Edited May 25, 2023 by RTFC
typo