Jump to content
dejhost

Speeding up array processing

Recommended Posts

I start programming (not as a profession) 35 years ago, using an PC1401 Sharp calculator with 3534 BYTES (yes Bytes) RAM for BASIC-Programs. Fortunately, this machine is programmable with machinecode (not Assembler, "assembling" the code is to be made by Brain1.0 :D)

BASIC for User-interaction, ASM for speed...

Today i like to speedup some calculations with ASM, and i still have the habit to optimize and "count clockticks".:whistle:

1 hour ago, czardas said:

My first version was capable of up to 27 bits, but I estimate it would have taken about 6 hours

I have measured a full "rotation" of a 32-Bit number in ASM takes about 100 clockticks, including "deleting not uniques", and the precalculation of bitcount and so on...

32 Bit is equal to 4,3e9 (numbers), lets say a Computer has 2Ghz, which is 2e9 clockticks per second. 

So the calculation of all 32 Bit numbers should take: 100 clockticks * 4.3e9 / 2e9 clockticks / second = 215 seconds :shocked:

The "array" is a bytearray, the "numbers" are represented by their index. AutoIt can only allocate 1GIG of RAM, which reduces the maximum number to 30 bit which should take 60seconds for the calculation. The using of SIMD and SSE could speed up the calculation by 2 , we are at 30 Seconds for 30Bit. (I dont think that multithreading is worth the time)

On CPU, so far, so good.

My experience with OpenCl shows, that with a good to parallelize algorithm, a GPU could make the calculation in some milliseconds. Normally it takes more time to transfer the data ( all "numbers") from RAM to the GPU and get back the result, than do the whole calculation.

I will try both ways.....

Edited by AndyG

Share this post


Link to post
Share on other sites
4 minutes ago, Melba23 said:

(although it is still lamentably slow when compared to ones you and czardas have been posting).

I would not say it is lamentably slow. Comparing to the OP´s script is is very fast. I think, he (the OP) would be very proud if he could write such a beautiful piece of code! 

Share this post


Link to post
Share on other sites

AndyG,

Thanks for the compliment - looking at your code, I return it with interest.

M23


Public_Domain.png.2d871819fcb9957cf44f4514551a2935.png Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind

Open spoiler to see my UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

 

Share this post


Link to post
Share on other sites

With the help of AssembleIt(), the runtime of ASM-code to calculate all 14Bit  numbers  takes something around 1 (one) millisecond. Unoptimized code, "oldschool" ASM...no SSE/SIMD. 

A 27Bit calculation takes 30 Seconds,

20Bit calculation takes 80 milliseconds with 52487 "unique" numbers. Time to fill an AutoIt-Array from dllstruct(bytearray) takes some seconds...._arrayunique() is overloaded too. I must write the unique numbers/bitstrings  into memory as an ASCII-string, so that this string can be read via dllstructgetdata(). That should be fast enough, 1-2ms i think...

The script uses ASM code mixed with AutoIt-variables, i prefer this method to develop quick´n´dirty :lol:,  A "standalone"-code could be created by AssembleIt() if necessary.

//EDIT if you take a look at my code, you can see that i use my debugger :lmao:

AssembleIt2_64.zip

#include <Array.au3>           ;aligncomment=30
#include <assembleit2_64.au3>
#AutoIt3Wrapper_UseX64=n



$bits = 20
$ar = 2 ^ ($bits) - 1          ;all numbers


;the "array", every byte is 0 (valid number) or set to 1 by the code to "delete" it
$bytestruct = DllStructCreate("byte[" & $ar + 1 & "]")
$ptr = DllStructGetPtr($bytestruct) ;pointer to the data


$msb = 2 ^ ($bits - 1)         ;msb
$mask = 2 ^ $bits - 1          ;mask


#cs PhotoMarker
    use32


    mov edi, $ptr              ;pointer to the bytestruct
    mov ebx,-1                 ;start: for $i=1 to $ar step 2

    label1:
    add ebx,2                  ;...step 2
    cmp ebx,$ar
    jae Label_end              ;if all numbers calculated, exit
    cmp dword[edi+ebx],1       ;If $a[$i] = 0 Then
    je label1                  ;if not, next $i

    ;bitcount calculation
    ;we shift left, until the carryflag is set to 1
    mov edx,ebx                ;save $i
    xor eax,eax                ;=0, number of shifts
    clc                        ;clear carry-flag CF
    bitcount:                  ;loop until CF=1
    inc eax                    ;shiftcounter+=1
    shl edx,1                  ;shift left...
    ;~      _asmdbg_()
    jnc bitcount               ;jump if not carry
    dec eax                    ;shiftcount-=1,
    sub eax,32                 ;we need bitcount
    neg eax                    ;=bitcount

    ;$t = BitShift($i, $bitcount - $bits) ;shift to the left border
    mov edx,ebx
    mov ecx,$bits
    sub ecx,eax
    shl edx,cl

    ;~      _asmdbg_()
    mov byte[edi+edx],1        ;delete rotated number, $a[$t] = 1

    ;now, lets rotate
    xor esi,esi                ;$x=0
    Label2:                    ;for $x=1 to $bitcount
    ;~     _asmdbg_()
    inc esi                    ;$x+=1
    cmp esi,eax                ;is bitcount reached?
    ja label1                  ;if above, next number

    cmp edx,$msb               ;If $t > $msb Then ;only if msb =1
    jl Label3                  ;jump if less
    mov byte[edi+edx],1        ;delete rotated number, $a[$t] = 1

    ;~      _asmdbg_()
    shl edx,1                  ;$t=$t*2
    sub edx,$mask              ;$t=$t-$mask

    cmp edx,ebx                ;If $t > $i Then $a[$t] = 1
    jle Label2                 ;jump if less or equal
    mov byte[edi+edx],1        ;delete rotated number, $a[$t] = 1
    ;~      _asmdbg_()
    jmp Label2                 ;next $x
    Label3:
    shl edx,1                  ;$t=$t*2
    ;~     _asmdbg_()
    jmp Label2                 ;next $x


    Label_end:                 ;exit

    mov eax,ebx


    ret                        ;eax is returned
#ce


$timer = TimerInit()

$ret = _AssembleIt2("uint", "PhotoMarker")

ConsoleWrite("! time=" & TimerDiff($timer) & "ms" & @CRLF)

ConsoleWrite("wait for filling the array..." & @CRLF)

Dim $a[$ar + 1]

For $i = 2 To $ar Step 2       ;all odd numbers (dllstruct is 1-based but memory is 0-based)
    If DllStructGetData($bytestruct, 1, $i) = 0 Then $a[$i - 1] = $i - 1 ;only if not "deleted"=1
Next

;~ _ArrayDisplay($a)

ConsoleWrite("wait for ArrayUnique()..." & @CRLF)

$r = _ArrayUnique($a)

ConsoleWrite($bits & "bits :  " & UBound($r) & " uniques were found" & @CRLF)

Dim $c[UBound($r) + 1][2]

ConsoleWrite("wait for ArrayDisplay()..." & @CRLF)
For $i = 1 To UBound($r) - 1
    $c[$i][0] = $r[$i]
    $c[$i][1] = Dec2Bin($r[$i])
Next


$z = _ArrayDisplay($c)

Func Dec2Bin($D)
    Return (BitShift($D, 1) ? Dec2Bin(BitShift($D, 1)) : "") & BitAND($D, 1) ;
EndFunc                        ;==>Dec2Bin

 

Edited by AndyG

Share this post


Link to post
Share on other sites

@AndyG That Assembly code runs blindingly fast.

I had another go to see what improvements I could make in my own code (pure AutoIt). There were a few improvements to be made. After trying everything I could think of, I still wasn't getting the same speed as your version in post #55. I couldn't figure out why there was such a difference until all of a sudden it dawned on me. You write the time taken before calling _ArrayUnique(). That doesn't make for a fair comparison: the job was unfinished. :P 

Although you don't really need to call _ArrayUnique(). :drinks:

~ 110 milliseconds without any formatting [2 GB RAM].

#include <Array.au3>

Local $iBits = 14

Local $aArray, $iTimer
$iTimer = TimerInit()
$aArray = BitLoopPermute($iBits)

ConsoleWrite(TimerDiff($iTimer) / 1000 & " seconds" & @LF)
ConsoleWrite(UBound($aArray) & " variants" & @LF)

_ArrayDisplay($aArray)

Func BitLoopPermute($iBinLen) ; limit = 24 bits
    $iBinLen = Int($iBinLen)
    If $iBinLen < 1 Then Return SetError(1) ; lowest loop size = 1
    If $iBinLen > 24 Then Return SetError(2) ; to remain within array size limits

    Local $iBound = 2^$iBinLen, $aArray[$iBound]
    For $i = 1 To 2^($iBinLen -1) Step 2
        $aArray[$i] = $i
    Next

    Local $iInversion, $iCount = 1
    For $i = 1 To 2^($iBinLen -1) Step 2
        If $aArray[$i] Then
            $iInversion = $i
            Do
                $iInversion = FirstInversion($iInversion, $iBinLen)
                If $iInversion > $i Then $aArray[$iInversion] = ''
            Until $iInversion = $i ; recursion either due to symmetry or a complete cycle
            $aArray[$iCount] = $i
            $iCount += 1
        EndIf
    Next

    $aArray[0] = 0
    $aArray[$iCount] = $iBound -1
    ReDim $aArray[$iCount +1]

    Return $aArray
EndFunc ;==> BitLoopPermute

Func FirstInversion($iInteger, $iLoopSize) ; skips all even numbers
    Local $iPosition = Floor(Log($iInteger) / Log(2)) ; the position of the first set bit [AndyG]
    $iInteger -= 2^($iPosition) ; remove MSB
    Return BitShift($iInteger, $iPosition -$iLoopSize) +1 ; shift the bits right [+1 MSB becomes the LSB]
EndFunc ;==> FirstInversion

Func DecToBase($iInt, $iBase) ; for bases 2 to 9
    Local $iRem, $sRet = ''
    While $iInt > $iBase -1
        $iRem = Mod($iInt, $iBase)
        $sRet = $iRem & $sRet
        $iInt = Int(($iInt - $iRem) /$iBase)
    WEnd
    Return $iInt & $sRet
EndFunc ;==> DecToBase


~ 180 milliseconds with formatted binary strings [2 GB RAM].

Func BitLoopPermute($iBinLen) ; limit = 24 bits
    $iBinLen = Int($iBinLen)
    If $iBinLen < 1 Then Return SetError(1) ; lowest loop size = 1
    If $iBinLen > 24 Then Return SetError(2) ; to remain within array size limits

    Local $iBound = 2^$iBinLen, $aArray[$iBound]
    For $i = 1 To 2^($iBinLen -1) Step 2
        $aArray[$i] = $i
    Next

    Local $iInversion, $iCount = 1, $sZeros = StringRight('000000000000000000000000', $iBinLen)
    For $i = 1 To 2^($iBinLen -1) Step 2
        If $aArray[$i] Then
            $iInversion = $i
            Do
                $iInversion = FirstInversion($iInversion, $iBinLen)
                If $iInversion > $i Then $aArray[$iInversion] = ''
            Until $iInversion = $i ; recursion either due to symmetry or a complete cycle
            $aArray[$iCount] = StringRight($sZeros & DecToBase($i, 2), $iBinLen)
            $iCount += 1
        EndIf
    Next

    $aArray[0] = $sZeros
    $aArray[$iCount] = DecToBase($iBound -1, 2)
    ReDim $aArray[$iCount +1]

    Return $aArray
EndFunc ;==> BitLoopPermute

 

Edited by czardas
Optimized FirstInversion() code

Share this post


Link to post
Share on other sites
1 hour ago, czardas said:

You write the time taken before calling _ArrayUnique().

:muttley:this is, because there is absolutely no need to use ArrayUnique. What is the intention to use ArrayUnique? There is NO other justification to use it than "lazyness".

Because every "valid" unique number is already known long before the ArrayUnique is called!

instead of 

For $i = 1 To $ar Step 2            ;all odd numbers
    If $a[$i] = 0 Then              ;only if not deleted
        $bitcount = Floor(Log($i) / Log(2)) + 1 ;number of bits of the actual number
        blaaaahhhh
    endif
next

you could write:

dim $valids[$ar]
$validcounter=0

For $i = 1 To $ar Step 2            ;all odd numbers
    If $a[$i] = 0 Then              ;only if not deleted
        ;we definitely caught a "valid" number
        $validcounter=$validcounter+1
        $valids[$validcounter]=$i
        
        ;all the rest is only to delete numbers GREATER than the valid one we had caught
        $bitcount = Floor(Log($i) / Log(2)) + 1 ;number of bits of the actual number
        blaaaahhhh
    endif
next

 

//EDIT if you are a "hardcore" Programmer, you could use the $a-array to store all the valids...uniques...

For $i = 1 To $ar Step 2            ;all odd numbers
    If $a[$i] = 0 Then              ;only if not deleted
        $a[$validcounter]=$i
        $validcounter=$validcounter+1
        
        $bitcount = Floor(Log($i) / Log(2)) + 1 ;number of bits of the actual number
        blahhh
    endif
next    

redim $a[$validcounter]  ;only valids

 

Edited by AndyG

Share this post


Link to post
Share on other sites

I'm not going to test it: I'll take your word for it. I don't need it to run faster because 12 bits in 30 ms is all I need. :D

I think we've just about exhausted what can be done here, unless someone else has something interesting to add. You never know!

Edited by czardas

Share this post


Link to post
Share on other sites

another doublepost:whistle:

No "Arrayunique", only stringfunctions needed

#include <Array.au3>           ;aligncomment=30
#include <assembleit2_64.au3>
#AutoIt3Wrapper_UseX64=n



$bits = 15
$ar = 2 ^ ($bits) - 1          ;all numbers


;the "array", every byte is 0 (valid number) or set to 1 by the code to "delete" it
$bytestruct = DllStructCreate("byte[" & $ar + 1 & "]")
$asciistruct = DllStructCreate("char[" & $bits * $ar & "]")

$ptr_bytestruct = DllStructGetPtr($bytestruct) ;pointer to the data
$ptr_asciistruct = DllStructGetPtr($asciistruct) ;pointer to the string

$msb = 2 ^ ($bits - 1)         ;msb
$mask = 2 ^ $bits - 1          ;mask


#cs PhotoMarker
    use32

    mov edi,$ptr_asciistruct   ;our "string"pointer

    mov esi, $ptr_bytestruct   ;pointer to the bytestruct
    mov ebx,-1                 ;start: for $i=1 to $ar step 2

    label1:
    add ebx,2                  ;...step 2
    cmp ebx,$ar
    jae Label_end              ;if all numbers calculated, exit
    cmp byte[esi+ebx],1        ;If $a[$i] = 0 Then
    je label1                  ;if not, next $i

    ;we caught an unique number, write it into the string
    ;we use a char-array to store the ascii-string
    ;ebx is now the "integer" to convert, edi the adress of the next "letter"

    ;Convert 32Bit-integer into ascii-"number" at EDI
    ;************************************************************
    ;wird dieser Bereich auskommentiert, wird ein String aus nullen und einsen zurückgegeben 0=keine Prim 1=Prim
    ;dann können mit den AutoIt-Stringbefehlen die Primzahlen und deren Anzahl ausgelesen werden
    push   ebx                 ;alle benötigten Register sichern
    push   edx
    mov eax, ebx               ;Zahl laden
    mov ebx, 10                ; Divisor
    xor ecx, ecx               ;ECX=0 (Anzahl der Ziffern)
    Schleife_1:
    xor edx, edx
    div ebx                    ; EDX:EAX / EBX = EAX Rest EDX
    push dx                    ; LIFO
    add cl,1                   ; ADD soll schneller sein als INC
    or  eax, eax               ; AX = 0?
    jnz Schleife_1             ; nein: nochmal
    Schleife_2:
    pop ax                     ; gepushte Ziffern zurückholen
    or al, 00110000b           ; Umwandlung in ASCII
    stosb                      ; Nur AL nach [EDI] (EDI ist ein Zeiger auf den String)
    loop Schleife_2            ; bis keine Ziffern mehr da sind
    mov byte [edi],0Dh         ;CR  CarriageReturn, man könnte auch ein Komma (ascii=2C) einsetzen, dazu noch ein nullbyte als EndOfString
    add edi,1                  ;ein Byte weiter
    pop   edx
    pop   ebx                  ;Register wiederherstellen
    ;************************************************************Ende Ziffer aus Register




    ;bitcount calculation
    ;we shift left, until the carryflag is set to 1
    mov edx,ebx                ;save $i
    xor eax,eax                ;=0, number of shifts
    clc                        ;clear carry-flag CF
    bitcount:                  ;loop until CF=1
    inc eax                    ;shiftcounter+=1
    shl edx,1                  ;shift left...
    ;~      _asmdbg_()
    jnc bitcount               ;jump if not carry
    dec eax                    ;shiftcount-=1,
    sub eax,32                 ;we need bitcount
    neg eax                    ;=bitcount

    ;$t = BitShift($i, $bitcount - $bits) ;shift to the left border
    mov edx,ebx
    mov ecx,$bits
    sub ecx,eax
    shl edx,cl

    ;~      _asmdbg_()
    mov byte[esi+edx],1        ;delete rotated number, $a[$t] = 1

    ;now, lets rotate
    xor ecx,ecx                ;$x=0
    Label2:                    ;for $x=1 to $bitcount
    ;~     _asmdbg_()
    inc ecx                    ;$x+=1
    cmp ecx,eax                ;is bitcount reached?
    ja label1                  ;if above, next number

    cmp edx,$msb               ;If $t > $msb Then ;only if msb =1
    jl Label3                  ;jump if less
    mov byte[esi+edx],1        ;delete rotated number, $a[$t] = 1

    ;~      _asmdbg_()
    shl edx,1                  ;$t=$t*2
    sub edx,$mask              ;$t=$t-$mask

    cmp edx,ebx                ;If $t > $i Then $a[$t] = 1
    jle Label2                 ;jump if less or equal
    mov byte[esi+edx],1        ;delete rotated number, $a[$t] = 1
    ;~      _asmdbg_()
    jmp Label2                 ;next $x
    Label3:
    shl edx,1                  ;$t=$t*2
    ;~     _asmdbg_()
    jmp Label2                 ;next $x


    Label_end:                 ;calculation is done, now we have to build the ascii-list


    ret                        ;eax is returned
#ce


$timer = TimerInit()

$ret = _AssembleIt2("uint", "PhotoMarker") ;calculate the valid numbers
$string = DllStructGetData($asciistruct, 1) ; we get the string

ConsoleWrite("! time=" & TimerDiff($timer) & "ms" & @CRLF)

;no good idea to "show" this long string via msgbox
;MsgBox(262144, 'Debug line ~' & @ScriptLineNumber, 'Selection:' & @CRLF & '$string' & @CRLF & @CRLF & 'Return:' & @CRLF & $string) ;### Debug MSGBOX

;we better write it into a file
$filename = "valid_numbers_up_to_" & $ar & ".dat"
FileDelete($filename)
FileWrite($filename, $string)
ShellExecute($filename)



ConsoleWrite("wait for filling the array..." & @CRLF)

StringReplace($string, @CR, @CR) ;count uniques
$uniques = @extended
ConsoleWrite($bits & "bits :  " & $uniques & " uniques were found" & @CRLF)

$r = StringSplit($string, @CR) ;into an array^^

Dim $c[UBound($r) + 1][2]

ConsoleWrite("wait for ArrayDisplay()..." & @CRLF)
For $i = 1 To UBound($r) - 1
    $c[$i][0] = $r[$i]
    $c[$i][1] = Dec2Bin($r[$i])
Next


$z = _ArrayDisplay($c)

Func Dec2Bin($D)
    Return (BitShift($D, 1) ? Dec2Bin(BitShift($D, 1)) : "") & BitAND($D, 1) ;
EndFunc                        ;==>Dec2Bin

next one is the "standalone"-version....

Share this post


Link to post
Share on other sites

last "evolution"...

20 bits takes only some (milli)seconds to calculate. The most time goes by "showing" the calculated numbers (which is not needed i think!)

#include <Array.au3>                                   ;aligncomment=30
;~ #include <assembleit2_64.au3>
#AutoIt3Wrapper_UseX64=n



$bits = 20
ConsoleWrite("#Bits = " & $bits & @CRLF)
$ar = 2 ^ ($bits) - 1                                  ;all numbers

;the "array", every byte is 0 (valid number) or set to 1 by the code to "delete" it
$bytestruct = DllStructCreate("byte[" & $ar + 1 & "]")
$asciistruct = DllStructCreate("char[" & $bits * $ar & "]") ;should be enough...

$ptr_bytestruct = DllStructGetPtr($bytestruct)         ;pointer to the data
$ptr_asciistruct = DllStructGetPtr($asciistruct)       ;pointer to the string

$msb = 2 ^ ($bits - 1)                                 ;msb
$mask = 2 ^ $bits - 1                                  ;mask


$timer = TimerInit()

;~ $asm_code = _AssembleIt2("retBinary", "PhotoMarker")
Local $asm_code = "0x8B7C24048B742408BBFFFFFFFF83C3023B5C240C7770803C1E0174F1535289D8BB0A00000031C931D2F7F3665280C10109C075F366580C30AAE2F9C6070D83C7015A5B89DA31C0F840D1E273FB4883E820F7D889DA8B4C241829C1D3E2C604160131C94139C177A53B5424147C14C6041601D1E22B54241039DA7EE7C6041601EBE1D1E2EBDD89D8C3"
Local $asm_struct = DllStructCreate("byte[" & StringLen($asm_code) / 2 - 1 & "]") ;speicher für asm-code bereitstellen...
DllStructSetData($asm_struct, 1, $asm_code)            ;...und mit code beschreiben


DllCallAddress("none:cdecl", DllStructGetPtr($asm_struct), "ptr", $ptr_asciistruct, "ptr", $ptr_bytestruct, "uint", $ar, "uint", $mask,"uint",$msb,"uint",$bits);$ret = _AssembleIt2("uint", "PhotoMarker", "ptr", $ptr_asciistruct, "ptr", $ptr_bytestruct, "uint", $ar, "uint", $mask) ;calculate the valid numbers
$string = DllStructGetData($asciistruct, 1)            ; we get the string

ConsoleWrite("! time=" & Int(TimerDiff($timer)) & "ms  since start calculating the numbers and write them into a string" & @CRLF)

;no good idea to "show" this long string via msgbox
;MsgBox(262144, 'Debug line ~' & @ScriptLineNumber, 'Selection:' & @CRLF & '$string' & @CRLF & @CRLF & 'Return:' & @CRLF & $string) ;### Debug MSGBOX

;we better write it into a file
$filename = "valid_numbers_up_to_" & $ar & ".dat"
FileDelete($filename)
FileWrite($filename, $string)
ShellExecute($filename)

ConsoleWrite("! time=" & Int(TimerDiff($timer)) & "ms  since start including writing/showing the file" & @CRLF)


ConsoleWrite("wait for StringSplit()..." & @CRLF)

StringReplace($string, @CR, @CR) ;count uniques
$uniques = @extended
ConsoleWrite($bits & "bits :  " & $uniques & " uniques were found" & @CRLF)

$r = StringSplit($string, @CR) ;into an array^^

ConsoleWrite("! time=" & Int(TimerDiff($timer)) & "ms  since start including stringsplit the string, wait for filling the array" & @CRLF)

Dim $c[UBound($r)][2]
For $i = 1 To UBound($r) - 1
    $c[$i][0] = $r[$i]
    $c[$i][1] = Dec2Bin($r[$i])
Next

ConsoleWrite("! time=" & Int(TimerDiff($timer)) & "ms  since start, now wait for ArrayDisplay()..." & @CRLF)
$z = _ArrayDisplay($c)

Func Dec2Bin($D)
    Return (BitShift($D, 1) ? Dec2Bin(BitShift($D, 1)) : "") & BitAND($D, 1) ;
EndFunc                        ;==>Dec2Bin

 

Share this post


Link to post
Share on other sites

Hi,

I have been looking at how to generate the patterns directly rather then using brute-force - just for fun.  But although the required patterns seem to be fairly simple when examined:

8-bit pattern with 3 1s

          length of 0 runs before each 1
00000111  5 0 0

00001011  4 1 0
00001101  4 0 1

00011001  3 0 2
00010101  3 1 1
00010011  3 2 0

00100101  2 2 1

--------------------------------

8-bit pattern with 4 1s

          length of 0 runs before each 1
00001111  4 0 0 0

00010111  3 1 0 0
00011011  3 0 1 0
00011101  3 0 0 1


00100111  2 2 0 0
00110011  2 0 2 0

00101011  2 1 1 0
00101101  2 1 0 1
00110101  2 0 1 1


01010101  1 1 1 1

trying to get an algorithm to generate them is proving far more difficult - although I am sure one must exist.  The problem I am wresting with at the moment is how to realise that 2002 is equivalent to 2200 and not generate it automatically.

M23


Public_Domain.png.2d871819fcb9957cf44f4514551a2935.png Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind

Open spoiler to see my UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

 

Share this post


Link to post
Share on other sites

I'm glad to see that my "back of enveloppe" note somehow contributed to make you guys think about the true nature of the problem.

I currently have very little free time to devote to digging further into this. Yet curiosity led me to ask OEIS about the sequence of number of results with increasing bitsize. Unsurprinsingly, this sequence is well-know: https://oeis.org/A000031

The references given there may shed some interesting light on how to tackle the problem in an opimal way. The numbering of this sequence (31) shows that it has been one of the first entered into OEIS when Sloane started his project. I really should have looked there first.

At the very least, this easily gives the exact number of entries that the resulting array will have. The fact that these numbers can also be defined by "number of binary irreducible polynomials whose degree divides n" leads to believe there could exist a fruitful theoretical approach to generating the results with a less computationally-intensive algorithm.

EDIT: the site may be off at times but the link given is correct " The OEIS may be off the air the weekends of August 13/14 and August 20/21 so that we can upgrade the server. There may be further interruptions later. "

Edited by jchd

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites

This is far too important for the back of an envelope. Having said that, I worked 12 bits out manually about 10 years back. It took a while - ouch! :whistle: Mind you, each pattern needed analysis: to identify the variants which are relevant to my project, so it wasn't time spent in vain.

Edited by czardas

Share this post


Link to post
Share on other sites

I was refering to my note in post

 


This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites

Hi,

I went looking for an algorithm and I found one thanks to jchd's links to OEIS. It is blindingly fast - I get the 14-bit result in ~150ms on my machine. Anyway, here it is for completion:

#include "Array.au3"

$nBegin = TimerInit()

; Set number of bits
$iMax = 14

; Create array to hold unique patterns
$iArraySizeFactor = 500
Global $aUnique[$iArraySizeFactor] =[0]

; Find factors for the bit value
$sFactors = "|1|"
For $i = Ceiling($iMax / 2) To 2 Step -1
    $nDiv = $iMax / $i
    If IsInt($nDiv) Then
        $sFactors &= $nDiv & "|"
    EndIf
Next
$sFactors &= $iMax & "|"
;ConsoleWrite($sFactors & @CRLF)

; Create initial pattern of all 1s
Local $aBits[$iMax + 1]
For $i = 1 To $iMax
    $aBits[$i] = 1
Next
_SavePattern($aBits)

; Start algorithm
While 1
    ; Find rightmost 1
    For $iIndex= $iMax To 1 Step -1
        If $aBits[$iIndex] = 1 Then ExitLoop
    Next

    ; Set found 1 to 0
    $aBits[$iIndex] = 0

    ; Fill rest of pattern with repeats of the pattern up to the found index
    $iFiller = 0
    For $i = $iIndex + 1 To $iMax
        $iFiller= Mod($iFiller, $iIndex) + 1
        $aBits[$i] = $aBits[$iFiller]
    Next

    ; If the found index is a factor of the bit value - valid pattern
    If StringInStr($sFactors, "|" & $iIndex & "|") Then
        _SavePattern($aBits)
    EndIf

    ; If leftmost 1 changed to 0 then pattern must be all 0s so end
    If $iIndex = 1 Then
        ExitLoop
    EndIf

WEnd

ReDim $aUnique[$aUnique[0] + 1]

ConsoleWrite(TimerDiff($nBegin) & @CRLF)

_ArrayDisplay($aUnique, "", "", 8)

Func _SavePattern($aArray)

    ; Convert pattern to string
    $sPattern = ""
    For $i = 1 to UBound($aArray) - 1
        $sPattern &= $aArray[$i]
    Next
    ; Resize array if required
    $aUnique[0] += 1
    If $aUnique[0] > UBound($aUnique) - 1 Then
        ReDim $aUnique[UBound($aUnique) + $iArraySizeFactor]
    EndIf
    ; Add pattern to array
    $aUnique[$aUnique[0]] = $sPattern

EndFunc

And please do not ask me to explain why it works - it took me long enough to work out how to get it to run!

M23


Public_Domain.png.2d871819fcb9957cf44f4514551a2935.png Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind

Open spoiler to see my UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

 

Share this post


Link to post
Share on other sites

Good. I didn't look at it but maybe you can even squeeze a little bit out of it by allocating the exact final size of the resultset. Well, that's a bit cheating because you have to store known "magic" values of the series up to some reasonnable bitsize. But as those values are correct, published and not some copyrighted secret sauce recipe, why not benefit of the knowledge. All this of course provided it helps avoiding repetitive ReDims.


This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Similar Content

    • By Stew
      (Edited from original.  Please note that I AM NOT AN AUTOIT EXPERT.  I write code using Autoit frequently but I am no expert, especially when it comes to I/O.  So any remarks that start with "Why did you..." can be answered by referring to the first sentence.  This project was done in Autoit because of an interface I built to display the data.)
      Attached is a program and ascii input file I wrote to read stock price data, convert it to binary and then read it back into the program in binary.  The goal was to show increased performance for reading the files in binary and provide a demo on how to read/write binary for int32, int64, double and strings for anyone who might find it helpful.  The results on my PC show the following:
      Time to read ascii file only: 456.981951167202
      Ascii read & process time: 6061.83075631701
      Binary write file time: 14787.9184635239
      Time just to read binary file: 42.418867292311
      Binary read and process time: 4515.16129830537
      A couple things to note:
      1) The 32 MB ascii file took 10x longer to read than the 15 MB binary file.  Not entirely sure why.  Both were read into a buffer.
      2) The Binary write takes a long time but I made no effort to optimize this because the plan was to write this file one time only so I don't mind if it takes longer to write this file.  I care much more about how long it takes to read the file because I will be reading it many times.
      3) There was a modest gain in converting the ascii file to binary in terms of file size and reading speed.
      So big picture... not sure it's worth the effort to convert the files to binary even though most of the data is numerical data in the binary file.  That was actually surprising as I expected there would be more of a difference.  Any ideas on how to get the binary data to read at a faster rate would be great.
       
      binary.au3
      2019_02_08.zip
    • By FMS
      Hello,
      I'm trying to read a binary file to an array but couln't get it to work.
      Also I coul not find any help in the forum around this subject whish was helpfull.
      Is there any way it could be done?
      I tried a lot of ways but maybe somebody know's the right way?
      #AutoIt3Wrapper_Au3Check_Parameters=-d -w 1 -w 2 -w 3 -w 4 -w 5 -w 6 -w 7 #include <File.au3> #include <Array.au3> #include <AutoItConstants.au3> Local $in=FileOpen("TEST_labels.idx1-ubyte",16) ; 16+0=Read binary Local $data = FileRead($in) Local $FileArray = BinaryToString($data,4) ;~ $FileArray = StringSplit($BinarydData, @CRLF, 1+2) ;~ Local $FileArray = StringRegExp($BinarydData, "[^\r\n]+", 3) FileClose($in) _ArrayDisplay($FileArray,"$FileArray","",32) MsgBox($MB_SYSTEMMODAL, "", "$FileArray = " & $FileArray )  
      TEST_labels.idx1-ubyte
    • By Dragonfighter
      I'm searching a way to do xor and shift and if possible also other operations. Thanks in advance for the replies.
    • By rudi
      Hello.
      I'm too stupid to see my mistake:
      To investigate the internal "dictionary" of TIFF files I'd like to read in the files in binary mode and to check, if there are more than one pages "in" this TIFF.
      Notepad++, "View as Hex" is presenting the first bytes as "49 49 2a 20 08 20 20 20 12" for the TIF attached to this posting
      The "TIFF Header Format" is easy:
      Offset 00h, 2 Byte = Byte Order, "II"=intel, "MM"=motorola. (I = 0x49)
      --> II
      Offset 02h, 2 Byte = Version Nr.
      Offset 04h, 4 Byte = pointer to first IFD entry
      Description of TIFF header: https://www.awaresystems.be/imaging/tiff/faq.html#q3
       

      Howto read and analyse the binary content correctly? This is my messy, not operational code:
       
      $sampleTiff="H:\daten\tif\11\11\111111.TIF" $h=FileOpen($sampleTiff,16) $content=FileRead($h) ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $content = ' & $content & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console FileClose($h) $type=VarGetType($content) ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $type = ' & $type & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console $ToString=BinaryToString($content) ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $ToString = ' & $ToString & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console ConsoleWrite(@CRLF & @CRLF) $content=StringTrimLeft($content,2) ; cut off the leading "0x" ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $content = ' & $content & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console for $i = 1 to 8 step 8 $next=StringMid($content,$i,2) ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $next = ' & $next & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console $Chr=BinaryToString($next) ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $Chr = ' & $Chr & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console ConsoleWrite(@CRLF & "---" & @CRLF) Next Regards, Rudi.
      111111.TIF
    • By ur
      When I am trying to compile the autoit files with aut2exe.
      I am getting below error.
      There is no issue in code as the same code is getting compiled on different machine.
      I tried reinstalling the AUtoIT, but the issue replicates.

      Any suggestions?
×
×
  • Create New...