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

    • 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!
    • am632
      By am632
      Hi,
      I have a binary string that I want to convert to octal, The string I want to convert is,
      10001001010100000100111001000111000011010000101000011010
       
      The String is read from a .txt file
      Once its converted it should read this,
      4   2   2   5   0   1   1   6   2   1   6   0   6   4   1   2   0   6   10
      which I want written to the .txt file to overwrite the original binary string.
      The 10 at the end should be ignored as there are not 3 digits to convert.
      I'm thinking it should read the string from left to right to get the next 3 digits before converting them to its oct value. would this be the best way to do this or is there a better way?
      If i'm on the right track can anyone give me an example of how to write this script please?
      I've looked at the StringLeft function & StringReplace but I'm not sure how to use them the correct way to accomplish what I'm trying to do.
      Thanks
       
    • toasterking
      By toasterking
      I was just working on a project that involved decoding a stream of binary data from a serial port in AutoIt.  It took me a few hours to figure out how to process the data efficiently in AutoIt and I did not find any helpful examples on how to do so, so I thought I would share my core example and maybe save someone else some time.  There may be a more efficient way to do this, but this works well for me.
       
      #cs Author: ToasterKing This is an example of a way to parse streaming binary data that follows a strict format with a header and footer. In this example, each frame is 5 bytes with a 2-byte header of 0xD5AA and a 1-byte footer of 0xAD. The _BinaryParse() function accumulates incoming data in a buffer. Once a footer is found, it searches backward for the header, and if it is in the right position, it extracts the remaining 2 bytes in the middle, then moves on to looking for the next frame. #ce ; The data source might be something asynchronous like serial or TCP, but since this is just an example, I'm just putting the data in a variable. Local $fSomeData $fSomeData = Binary("0xD5AA24B1") ; Binary data constituting almost a complete frame. _BinaryParse($fSomeData) ; Call the function with the received data. It isn't a complete frame, so it is just stored in the buffer until more data is received. $fSomeData = Binary("0xAD62D5AA92E7AD") ; Remainder of the previous frame, one garbage byte (0x62) which should be skipped, and a complete additional frame. _BinaryParse($fSomeData) ; The function should be able to parse both frames now. Func _BinaryParse($fNewData) Local Static $fBinaryReceived = Binary("") ; Buffer for received data ConsoleWrite("Hey, the function is called!" & @CRLF) ; Add new data to the buffer. ; This ridiculous monstrosity is the only way I could find to append binary data to binary data in AutoIt. It must be converted to strings first. ; Both, one, or no substrings will begin with "0x" depending on whether they contained binary data. To be converted back to binary properly, only one instance ; of "0x" must exist at the beginning of the string. $fBinaryReceived = Binary("0x" & StringReplace(String($fBinaryReceived) & String($fNewData),"0x","")) ConsoleWrite("Data in the buffer: " & String($fBinaryReceived) & @CRLF) Local $iLength = BinaryLen($fBinaryReceived) ; Count the bytes in the data If $iLength > 0 Then Local $fBinaryReceivedTemp = $fBinaryReceived ; Create temporary copy to work on Local $fByte1,$fByte2 For $i = 1 To $iLength If BinaryMid($fBinaryReceivedTemp,$i,1) = 0xAD Then ; If the 1-byte footer found ConsoleWrite("Footer found at end of " & $i & " of " & $iLength & " bytes!" & @CRLF) If BinaryMid($fBinaryReceivedTemp,$i - 4,1) = 0xD5 And BinaryMid($fBinaryReceivedTemp,$i - 3,1) = 0xAA Then ; and the 2-byte header is found 4 bytes before that ConsoleWrite("Header found before the footer!" & @CRLF) $fByte1 = BinaryMid($fBinaryReceivedTemp,$i - 2,1) ; Get 1st byte in the body (between header and footer) $fByte2 = BinaryMid($fBinaryReceivedTemp,$i - 1,1) ; Get 2nd byte in the body (between header and footer) ConsoleWrite("Here is the critical data: " & String($fByte1) & " " & String($fByte2) & @CRLF) ; Just display the 2 bytes for demonstration purposes. Normally, you'd do something more useful with it here. EndIf $fBinaryReceived = BinaryMid($fBinaryReceivedTemp,$i + 1) ; Truncate the original data to remove all of the bytes just processed, then continue processing $fBinaryReceivedTemp EndIf Next EndIf EndFunc  
    • CSL
      By CSL
      I want to take a binary data from any source (string,number,files,etc..) and iterate over each X bits of it in a loop, say take bits 1-5, then 6-10, etc.. Then I want to convert these bits to their corresponding decimal value.
      but all the binary functions I found in autoit only work with full bytes, and do not let me get smaller sections of bits, like "BinaryMid()" that "Extracts a number of bytes from a binary variant"
      Can anyone tell me if this is possible to do and how? and also if there is a function to convert those bits to/from decimals?
      I'm not that familiar with dealing directly with binary, so any help or tips will be very appreciated
      Context:
      I'm trying to make a function to encode/decode any given binary data into/from a given array of characters. just like Base64 but using different bases then [a-z A-Z 0-9 +/= ]. My approach currently is to figure out how many bits of binary I can encode with each character, read those bits and convert them to a decimal number, then I will use that number as an index and take the character at that index from the character array and add it to the result string.
      I'm aware that there may be some padding needed.