Speeding up array processing

dejhost · August 9, 2016

Hello ,

Here are three stepts that I would like to speed up - if possible:

STEP 1: I am generating an array, containing binary numbers up to a certain amount of digits. My script adds leading zeros, so that each number has equal amount of digits.

Example: 14 digit Binary array:

Quote

00000000000001

00000000000010

00000000000011

00000000000100

...

11111111111111

I am using the code

For $i = 0 to 2^$bit-1                              ; $bit amount of digits. for example: 14 
    $binary = ( Dec2Bin($i) )                       ; Check length of binary string
    $adig = $bit - StringLen($binary)               ; Determine how many leading 0 have to be added
    $zeros = ""

    For $j = 1 To $adig                             ; add leading "0"s
        $zeros =  $zeros & "0"
    Next

    $BinArray[$i] = $zeros & $binary                ;Write binary-number to file, leading "0"
Next

Func Dec2Bin($D)
    Return (BitShift($D, 1) ? Dec2Bin(BitShift($D, 1)) : "") & BitAnd($D, 1)
EndFunc    ;==> Dec2Bin() AutoIt v3.3.12.0

to generate the binary number.

STEP 2: I reduce the array to unique values. In my application, the binary-numbers do not have a start-bit or end-bit. This means, that

Quote

00000000000001 and

10000000000000 and

01000000000000 and

00100000000000

....

are actually the same numbers, and only one of them is to remain in the array. All alterations aren't unique and shall be removed. Here is my code:

For $i = 0 to Ubound($BinArray)-1                   ; shift through all rows

        For $j = 1 to $bit                              ; shift through all the bits
            If $i = Ubound($BinArray) Then          ; exit before exceeding the arrays boundries
                ExitLoop 2
            EndIf
            $BinArray[$i]  = StringRight ( $BinArray[$i], 1 ) & StringLeft ( $BinArray[$i], $bit-1 )
            $BinArray = _ArrayUnique($BinArray, 0, 0, 0, 0, $ARRAYUNIQUE_AUTO)
            If @error <> 0 Then
                 Msgbox(0, "Error in _ArrayUnique", "The Error Code is " &  @error & "   Abort.")
                 Exit
            EndIf
        Next
    Next

STEP 3: Finally, I write the remaining array into a text-file.

For $i = 0 to Ubound($BinArray)-1
    FileWrite($hFileOpen, $i & @TAB & $BinArray[$i] & @CRLF)
Next

So my question is: any idea how to speed up this procedure? There certainly is a way to do this smarter. Btw.: Step 2 is optional.

Thanks for helping,

dejhost

Melba23 · August 9, 2016

dejhost,

This works pretty fast for me:

#include <Array.au3>

Local $iBit = 14

Local $aBinArray[2 ^ $iBit]

For $i = 0 to (2 ^ $iBit) - 1
    $sBinary = (Dec2Bin($i))                                        ; Create binary string
    ;ConsoleWrite($sBinary & @TAB)
    $sBinary = StringFormat("%0" & $iBit & "s", $sBinary)           ; Pad with leading zeros if needed
    ;ConsoleWrite($sBinary & @TAB)
    $sBinary = StringTrimLeft(StringTrimRight($sBinary, 1), 1)      ; Trim first and last digits
    ;ConsoleWrite($sBinary & @CRLF)
    $aBinArray[$i] = $sBinary                                       ; Store
Next

;_ArrayDisplay($aBinArray, "Full", Default, 8)
ConsoleWrite("Full array:  " & UBound($aBinArray) & " elements" & @CRLF)

$aBinArray = _ArrayUnique($aBinArray)

;_ArrayDisplay($aBinArray, "Unique", Default, 8)
ConsoleWrite("Unique array: " & UBound($aBinArray) & " elements" & @CRLF)

Func Dec2Bin($iD)
    Return (BitShift($iD, 1) ? Dec2Bin(BitShift($iD, 1)) : "") & BitAnd($iD, 1)
EndFunc

How does it compare on your machine?

M23

dejhost · August 9, 2016

Melba23,

great input, thanks! StringFormat works certainly much faster!

But STEP2 is (to my understanding) not doing what I want it to do:

Quote

$sBinary = StringTrimLeft(StringTrimRight($sBinary, 1), 1)      ; Trim first and last digits

You are deleting the first and the last digit, right? But I need to have a kind of rotation here, since any digit of the binary number can be the first digit. This is why I cut of the last digit, add it as first digit. Then I check if the resulting number is unique:

$sBinary = StringRight ( $BinArray[$i], 1 ) & StringLeft ( $BinArray[$i], $bit-1 ) ; Cut off last digit, and add as first digit.
 $BinArray = _ArrayUnique($BinArray, 0, 0, 0, 0, $ARRAYUNIQUE_AUTO); check if this number is unique.

This process is to be repeated for the amount of digits.

Melba23 · August 9, 2016

dejhost,

Quote

since any digit of the binary number can be the first digit

I have no idea what you mean by that.

Quote

This is why I cut of the last digit, add it as first digit

That is at least understandable, although in my opinion you will find that each of the items in the array will still be unique and so there is no need to do any comparison. And it most certainly will not make the elements you specified in the OP the "same", as you suggested you required- look at this:

00000000000001 ---> 10000000000000
10000000000000 ---> 01000000000000
01000000000000 ---> 00100000000000
00100000000000 ---> 00010000000000

Perhaps if you explained why you need to do this all this manipulation of the binary representations of these values we might be able to offer some more focused advice. Just what is the purpose of the script?

M23

jchd · August 9, 2016

I found the question to be an uncommon and interesting problem in non-trivial combinatorics.
Here's how I would approach it. I use fixed-pitch font for readability of alignments.

I'll first list how to tackle small value of bit size, then deduce rules that can prune the tree.
Say you consider binary values in natural increasing order.
Say you call a value acceptable when it is the smallest value resulting from bit rotation of binary string of a given size.
Remark that values consisting of a number of leading zeroes followed by trailing ones are all acceptable. A value has to end with a one, else we could rotate it into a lower value already considered.
These acceptable values are written as heads of columns.
Now let's list in those columns (under each acceptable value) the other values that can be derived by inserting some zeroes in the middle of the string of trailing ones.
The values we have to consider consist of a string of leading zeroes followed by a one and ending by a trailing one.
The model is ...???1 where ... is a string of zeroes and ??? a binary string, both possibly empty. The value 0 is exceptional and always OK.
Remark that ??? cannot contain substring(s) of zeroes longer that the leading ... else it would have been considered under a previous column (on its left).

This will become clearer as examples grow in size.

#bits     Acceptable binary                                                          Accepted decimal values
1         0, 1                 there is nothing we change do here                    0, 1

2         00, 01, 11           the string of trailing ones can be broken             0, 1, 3

3         000, 001, 011, 111   here we have to consider the possibility that the median 1 in 111 could be turned into a 0
                               but we can't, since by rotation the value would has been already covered by a previous
                               column (101 can be rotated into 011)

4         0000, 0001, 0011, 0111, 1111      the decimal values are                   0, 1, 3, 7, 15
                                            things become interesting as the previous remark doesn't hold
                            0101            is also acceptable, giving                        5

5         00000, 00001, 00011, 00111, 01111, 11111                                   0, 1, 3, 7, 15, 31
                               00101, 01011                                                   5, 11
Note that we can't consider           01001 because it contains a string of two zeroes which is already covered under the column on its left (under 00111).

6         000000, 000001, 000011, 000111, 001111, 011111, 111111                     0, 1, 3, 7, 15, 31, 63
                                  000101, 001011, 010101                                      5, 11, 21
                                          001101, 010111                                         13, 23

7         0000000, 0000001, 0000011, 0000111, 0001111, 0011111, 0111111, 1111111     0, 1, 3, 7, 15, 31, 63, 127
                                     0000101, 0001001, 0010011, 0101011                       5,  9, 19, 43 
                                              0001011, 0010101, 0101111                          11, 21, 47
                                              0001101, 0010111, 0110111                          13, 23, 55
                                                       0011011, 0111011                              27, 59
                                                       0011101                                       29

We start to see an algorithm emerge, with minimal number of comparison of possible rotations.
Let's call K the number of bits considered.
For every N < K, accept values 2^N - 1. This gives the list 0, 1, 3, 7, 15, 31, 63, ...
For each accepted value > 3 (smaller values have too few bits to consider), let X be the number of leading zeroes and Y the number K-X-2

Doing so we are considering binary numbers written as:
0...0 1 ??? 1
^^^^^   ^^^
  |      |________ Y binary digits. Let's call this value V, with 0 <= V < 2^Y - 1
  |_______________ X binary zeroes.

By enumerating binary values of V in increasing binary order, we have a number of candidates for acceptance.
We can safely discard values of V which contains substrings of more than X consecutive zeroes. Reason (again): else they would fall by rotation in a column to the left.
Now all we have to do is to discard duplicates under rotation in the number thusly formed.
This minimizes the number of comparisons that need to be made.

This approach is clearly heavy for small values of K but should prove beneficial when K increases significantly.
I hope I didn't made errors in the above, but you should understand the idea.

Melba23 · August 9, 2016

jchd,

Well, that is certainly "focused"!

M23

jchd · August 9, 2016

Should work

I still can't place the problem in a well-known computational framework, so a back-of-enveloppe sketchy approach is good enough, povided my prose is understandable.

Edited August 9, 2016 by jchd

dejhost · August 9, 2016

16 minutes ago, Melba23 said:
dejhost,

I have no idea what you mean by that.

That is at least understandable, although in my opinion you will find that each of the items in the array will still be unique and so there is no need to do any comparison. And it most certainly will not make the elements you specified in the OP the "same", as you suggested you required- look at this:
00000000000001 ---> 10000000000000
10000000000000 ---> 01000000000000
01000000000000 ---> 00100000000000
00100000000000 ---> 00010000000000
Perhaps if you explained why you need to do this all this manipulation of the binary representations of these values we might be able to offer some more focused advice. Just what is the purpose of the script?

M23

Sorry for the confusion. The purpose of the script:

I am generating a lookup table for photogrammetric markers. This is a binary code (bits can be set to white or to black), arranged in a radial way. The markers have no orientation; which means, that there is no "first bit", and no "last bit": "10000" = "01000" = "00100" = "00010" = "00001".

Melba23 · August 9, 2016

dejhost,

This looks as if it might do the trick:

#include <Array.au3>

Local $iBit = 14

Local $aBinArray[2 ^ $iBit] = [StringFormat("%0" & $iBit & "s", "0")]   ; All zeroes is always valid

For $i = 1 to (2 ^ $iBit) - 1
    $sBinary = (Dec2Bin($i))                                            ; Create binary string
    ConsoleWrite($sBinary & @TAB)
    $sBinary = StringRegExpReplace($sBinary, "(?U)^(.*)0*$", "$1")      ; Strip any trailing zeros
    ConsoleWrite($sBinary & @TAB)
    $sBinary = StringFormat("%0" & $iBit & "s", $sBinary)               ; Pad with leading zeros as required
    ConsoleWrite($sBinary & @CRLF)
    $aBinArray[$i] = $sBinary                                           ; Store
Next

_ArrayDisplay($aBinArray, "Full", Default, 8)
;ConsoleWrite("Full array:  " & UBound($aBinArray) & " elements" & @CRLF)

$aBinArray = _ArrayUnique($aBinArray)

_ArrayDisplay($aBinArray, "Unique", Default, 8)
;ConsoleWrite("Unique array: " & UBound($aBinArray) & " elements" & @CRLF)

Func Dec2Bin($iD)
    Return (BitShift($iD, 1) ? Dec2Bin(BitShift($iD, 1)) : "") & BitAnd($iD, 1)
EndFunc

I do not lay claim to jchd's mathematical rigour, so I cannot vouch for its accuracy - but looking at the final array, the unique values seem reasonably valid.

M23

jchd · August 9, 2016

@Melba23

There is a problem with this script. An example of error (duplicate by rotation) appears at entry #130 of the unique array: the value there is 00000100000001 (5 leading 0s then a 1 then a substring of 7 zeroes and a final 1) which can be rotated as 00000001000001 and is already listed at entry #34 (00000001000001).

Yes the problem is a bit trickier than it sounds.

Melba23 · August 9, 2016

jchd,

Quote

the problem is a bit trickier than it sounds

Too right! Thinking cap back on......

M23

iamtheky · August 9, 2016

what about just eliminating by sums?

#include<array.au3>

 local $aArr = ["00000000000001" , "10000000000000" , "10010000000000" , "0111111000000" , "01000000001100" ,"00100110000000" , "00100000000001" ,"00010000000100" , "00001111111000"]

_ArrayDisplay( _ArrUniqueBySum($aArr) , "UniqueBySum")


 Func _ArrUniqueBySum($aArray)

    local $aUnique[0][2]

    For $i = 0 to ubound($aArray) - 1
       If _ArraySearch($aUnique , Execute(_ArrayToString(stringsplit($aArray[$i], "" , 2) , "+")) , 0 , 0 ,0 ,0 ,1 , 0) = -1 Then
          _ArrayAdd($aUnique , Execute(_ArrayToString(stringsplit($aArray[$i], "" , 2) , "+")))
          $aUnique[ubound($aUnique) - 1][1] = $aArray[$i]
          EndIf
       Next


Return _ArrayExtract($aUnique , -1 , -1 , 1 , 1)

EndFunc

jchd · August 9, 2016

That would eliminate values that have the same number of 0s and 1s but are not equivalent (rotation-wise).

iamtheky · August 9, 2016

7 hours ago, dejhost said:

Quote

00000000000001 and

10000000000000 and

01000000000000 and

00100000000000

....

are actually the same numbers, and only one of them is to remain in the array. All alterations aren't unique and shall be removed.

isnt that the same thing as

3 minutes ago, jchd said:

That would eliminate values that have the same number of 0s and 1s but are not equivalent (rotation-wise).

?

apologies if i over simplified

jchd · August 9, 2016

I mean: 01001 is equivalent (rotation-wise) to 00101, but its a distinct pattern as 00011. So just counting bits isn't enough.

iamtheky · August 9, 2016

even with the criteria at the end of post #8?

jchd · August 9, 2016

It's a simple example. Imagine strings of K bits written on band aids, with no indication of start point. The problem at hand is to enumerate all distinct band aids of K bits.

AndyG · August 9, 2016

Ok, lets see if i understand this thing...and bruteforce it like the "Sieve of Eratosthenes"

There are 14 bit numbers, from 0 to 16383.

Starting with the first number, ROL 1, and AND it with every other number in the array. If they are equal, set them to 0. ROL 13 times, then next number. Process the whole array.

Every number in the array which is not 0 is valid and unique in case of the task setting.

Melba23 · August 9, 2016

AndyG,

I have been working along those lines - with this script as the result:

#include <Array.au3>

Local $iBit = 8

Local $aBinArray[2 ^ $iBit] = [StringFormat("%0" & $iBit & "s", "0")]

ConsoleWrite("Filling array" & @CRLF)

For $i = 1 to (2 ^ $iBit) - 1
    $sBinary = (Dec2Bin($i))                                            ; Create binary string
    ;ConsoleWrite($sBinary & @TAB)
    $sBinary = StringRegExpReplace($sBinary, "(?U)^(.*)0*$", "$1")      ; Strip any trailing zeros
    ;ConsoleWrite($sBinary & @TAB)
    $sBinary = StringFormat("%0" & $iBit & "s", $sBinary)               ; Pad with leading zeros as required
    ;ConsoleWrite($sBinary & @CRLF)
    $aBinArray[$i] = $sBinary                                           ; Store
Next
;_ArrayDisplay($aBinArray, "Full", Default, 8)
;ConsoleWrite("Full array:  " & UBound($aBinArray) & " elements" & @CRLF)

ConsoleWrite("Checking rotations" & @CRLF)
; Now loop through the array checking all rotations against all other values
For $i = 1 To UBound($aBinArray) - 2 ; First and last are all 0s or 1s

    ConsoleWrite("Element: " & $i & @CRLF)

    ; Check string
    $sRotated = $aBinArray[$i]
    ; If this element has not already been deleted
    If $sRotated Then
        ; Loop through all possible rotations
        For $j = 1 To $iBit
            ; Compare to elements in array - only need to look below the current element
            For $k = $i + 1 To UBound($aBinArray) - 2
                If $aBinArray[$k] = $sRotated Then
                    ; If there is a match then delete the element
                    $aBinArray[$k] = ""
                EndIf
            Next
            $sRotated = _Rotate($sRotated)
        Next
    EndIf
Next

ConsoleWrite("Deleting blanks" & @CRLF)
; Clear all the deleted elements
For $i = UBound($aBinArray) - 1 To 0 Step -1
    If $aBinArray[$i] = "" Then
        _ArrayDelete($aBinArray, $i)
    EndIf
Next

_ArrayDisplay($aBinArray, "Unique binaries", Default, 8)
;ConsoleWrite("Unique array: " & UBound($aBinArray) & " elements" & @CRLF)

Func _Rotate($sString)
    Return StringRight($sString, 1) & StringLeft($sString, $iBit - 1)
EndFunc


Func Dec2Bin($iD)
    Return (BitShift($iD, 1) ? Dec2Bin(BitShift($iD, 1)) : "") & BitAnd($iD, 1)
EndFunc

I have optimised it as much as I think I can but it is still phenomenally slow - I have limited it to 8-bits for the example as I got bored waiting for the 14-bit one to finish!

Over to the maths gurus to tell me where this one fails.....

M23

jchd · August 9, 2016

Correct, as far I understand the OP's problem. Brute force is already a large number of comparisons, but the killer catch is that ROL (and AND) can't be done in binary here, due to the bitstring size not being forcibly a multiple of 8 which doesn't allow to use processor rotate instructions and derivatives, slowing the comparisons down to snail speed.

I don't know if the OP would have to process much larger bitstrings but if that's the case as I suspect, then we have to devise a more subtle approach.

Speeding up array processing

Recommended Posts

Top Posters In This Topic

Top Posters In This Topic

Popular Posts

Melba23

Gianni

AndyG

Create an account or sign in to comment

Create an account

Sign in

Similar Content