dejhost

Speeding up array processing

78 posts in this topic

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 

Share this post


Link to post
Share on other sites



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


Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______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

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.

Share this post


Link to post
Share on other sites

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


Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______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 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.

 


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

jchd,

Well, that is certainly "focused"!

M23


Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______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

#7 ·  Posted (edited)

Should work :lol:

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 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
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".

 

 

 

Share this post


Link to post
Share on other sites

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


Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______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

@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.


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

jchd,

Quote

the problem is a bit trickier than it sounds

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

M23


Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______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

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

 


,-. .--. ________ .-. .-. ,---. ,-. .-. .-. .-.
|(| / /\ \ |\ /| |__ __||| | | || .-' | |/ / \ \_/ )/
(_) / /__\ \ |(\ / | )| | | `-' | | `-. | | / __ \ (_)
| | | __ | (_)\/ | (_) | | .-. | | .-' | | \ |__| ) (
| | | | |)| | \ / | | | | | |)| | `--. | |) \ | |
`-' |_| (_) | |\/| | `-' /( (_)/( __.' |((_)-' /(_|
'-' '-' (__) (__) (_) (__)

Share this post


Link to post
Share on other sites

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


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
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


,-. .--. ________ .-. .-. ,---. ,-. .-. .-. .-.
|(| / /\ \ |\ /| |__ __||| | | || .-' | |/ / \ \_/ )/
(_) / /__\ \ |(\ / | )| | | `-' | | `-. | | / __ \ (_)
| | | __ | (_)\/ | (_) | | .-. | | .-' | | \ |__| ) (
| | | | |)| | \ / | | | | | |)| | `--. | |) \ | |
`-' |_| (_) | |\/| | `-' /( (_)/( __.' |((_)-' /(_|
'-' '-' (__) (__) (_) (__)

Share this post


Link to post
Share on other sites

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


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

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


,-. .--. ________ .-. .-. ,---. ,-. .-. .-. .-.
|(| / /\ \ |\ /| |__ __||| | | || .-' | |/ / \ \_/ )/
(_) / /__\ \ |(\ / | )| | | `-' | | `-. | | / __ \ (_)
| | | __ | (_)\/ | (_) | | .-. | | .-' | | \ |__| ) (
| | | | |)| | \ / | | | | | |)| | `--. | |) \ | |
`-' |_| (_) | |\/| | `-' /( (_)/( __.' |((_)-' /(_|
'-' '-' (__) (__) (_) (__)

Share this post


Link to post
Share on other sites

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.


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

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.

 

Share this post


Link to post
Share on other sites

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


Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______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

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.


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

    • Dragonfighter
      By Dragonfighter
      I'm searching a way to do xor and shift and if possible also other operations. Thanks in advance for the replies.
    • rudi
      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
    • ur
      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?
    • wakillon
      By wakillon
      BinaryToAu3Kompressor v1.0.5.4
       

       
      It's now possible to see the best compression ratio using LZMA, LZNT and Base64 compressions with differents combinations.
      Nothing too complicate, you drag'n drop a file on the picture and script Test all compression types and return the ratios.
      ( Test duration depends of file size, slowest compression is LZNT, but all decompressions are fast  )
      Free to you after, to choose the compression(s) you want...
      Yes, LZMA needs a dll ( embedded & compressed in script ) but brings a powerfull compression. 
      It opens scite with your file compressed to an au3 script with or without decompression function as you want.
      Hold Left Shift key when clicking button for just copy script to clipboard.
      Use the 3 compressions at a time works but doesn't give a good ratio, that's why i don't display it.
      Usefull for little files you want include in your scripts !
      No externals files needed, they are already in script.
      Previous downloads : 1103
      Source and Executable
      BinaryToAu3Kompressor will be added to the next version of >SciTEHopper
      Thanks to Ward for his >Base64.au3 and LZMA.au3, and trancexx for his >LZNT functions and his >Base64Decode function.
    • WoodGrain
      By WoodGrain
      Hi All,
      Trying to convert a number to binary zeros and ones but I'm getting a result I don't understand and looks more like hex than binary.
      Here's my basic code:
      $myNum = 11 $myNumBin = Binary($myNum) MsgBox(0, "Binary result", $myNumBin) What I want is "1011", what I get is 0x0B000000.
      Thanks!