Speeding up array processing

Recommended Posts

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
\$zeros = ""

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

• Replies 77
• Created

Popular Posts

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

...... a little adjustment in the logic, now with 14 bits it runs in about 2 seconds. #include <array.au3> Local \$iTimer = TimerInit() Local \$iBits = 14 ; nr. of bit Loca

hmmm, seems we have the same algorithm Chimp, so nice #include <Array.au3> ;#include <assembleit2_64.au3> #AutoIt3Wrapper_UseX64=n #cs ROL_it&#

• Moderators

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

Open spoiler to see my UDFs:

Spoiler

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

Share 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 on other sites
• Moderators

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

Open spoiler to see my UDFs:

Spoiler

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

Share 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.
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 on other sites
• Moderators

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

Open spoiler to see my UDFs:

Spoiler

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

Share on other sites

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

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
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 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 on other sites
• Moderators

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

Open spoiler to see my UDFs:

Spoiler

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

Share on other sites

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.
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 on other sites
• Moderators

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

Open spoiler to see my UDFs:

Spoiler

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

Share 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 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.
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 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 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.
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 on other sites

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

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

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.
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 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 on other sites
• Moderators

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

Open spoiler to see my UDFs:

Spoiler

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

Share 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.
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)

Create an account

Register a new account

• Similar Content

• Func _Binary(\$Int) ;Uncomment To Only Accept Integers #cs If IsInt(\$Int) = 0 Then Return 0 EndIf #ce If \$Int < 0 Then ;Negative Numbers Will Break The Function Return 0000 EndIf Local \$Integer = \$Int Dim \$Bin[1] = [Mod(\$Integer, 2)] Local \$Counter = 1 Do \$Integer = Floor(\$Integer / 2) _ArrayAdd(\$Bin, Mod(\$Integer, 2)) Until \$Integer = 0 _ArrayReverse(\$Bin) ;Reverses The Array Because As Is, The Product Is Backwards ;A Loop To Remove Any Preceding 0's or Add 0's To Keep At Least Four Digits Select Case \$Int <= 1 \$Integer = "00" & _ArrayToString(\$Bin, "") Case \$Int = 2 Or \$Int = 3 \$Integer = "0" & _ArrayToString(\$Bin, "") Case \$Int >= 8 \$Integer = StringTrimLeft(_ArrayToString(\$Bin, ""), 1) Case Else \$Integer = _ArrayToString(\$Bin, "") EndSelect ;You Can Comment It Out Without Anything Else Having A Problem Return \$Integer EndFunc I made this because I was writing something that I could use to play with Bitwise Operations and using Binary() by itself wasn't helping.
It's very basic and will only take positive integers because that's all I needed but I'm sure with a little tweaking you could make it fit with negative and float types.
It returns a string essentially but doesn't pose a problem when just changing numbers into binary digits.
Example: If you were to do _Binary(5) you would get "0101" and _Binary(8) would return "1000"
Between this last sentence and here I've changed this about a half dozen times to refine it a bit because without it checking if your number is < 0 it would break if a negative number was inserted and it wouldn't even have a problem if you put in Float Values, Regular or Special Characters but that negative value will do the trick lol.
Anyway, I hope someone finds some use of this and thank you for reading!
-Pick

• Hi AutoIt Programmers, i wanna figure out how to use Binary functions in C# like:

BinaryMid
BinaryLen
IsBinary and other basic ones were too ez, but those two were hard to noob like me.

• By Stew
(Edited from original.  Please note that I AM NOT AN AUTOIT EXPERT.  I write code using Autoit frequently but I am no expert, especially when it comes to I/O.  So any remarks that start with "Why did you..." can be answered by referring to the first sentence.  This project was done in Autoit because of an interface I built to display the data.)
Attached is a program and ascii input file I wrote to read stock price data, convert it to binary and then read it back into the program in binary.  The goal was to show increased performance for reading the files in binary and provide a demo on how to read/write binary for int32, int64, double and strings for anyone who might find it helpful.  The results on my PC show the following:
Time to read ascii file only: 456.981951167202
Ascii read & process time: 6061.83075631701
Binary write file time: 14787.9184635239
Time just to read binary file: 42.418867292311
Binary read and process time: 4515.16129830537
A couple things to note:
1) The 32 MB ascii file took 10x longer to read than the 15 MB binary file.  Not entirely sure why.  Both were read into a buffer.
2) The Binary write takes a long time but I made no effort to optimize this because the plan was to write this file one time only so I don't mind if it takes longer to write this file.  I care much more about how long it takes to read the file because I will be reading it many times.
3) There was a modest gain in converting the ascii file to binary in terms of file size and reading speed.
So big picture... not sure it's worth the effort to convert the files to binary even though most of the data is numerical data in the binary file.  That was actually surprising as I expected there would be more of a difference.  Any ideas on how to get the binary data to read at a faster rate would be great.

binary.au3
2019_02_08.zip
• By FMS
Hello,
I'm trying to read a binary file to an array but couln't get it to work.
Also I coul not find any help in the forum around this subject whish was helpfull.
Is there any way it could be done?
I tried a lot of ways but maybe somebody know's the right way?
#AutoIt3Wrapper_Au3Check_Parameters=-d -w 1 -w 2 -w 3 -w 4 -w 5 -w 6 -w 7 #include <File.au3> #include <Array.au3> #include <AutoItConstants.au3> Local \$in=FileOpen("TEST_labels.idx1-ubyte",16) ; 16+0=Read binary Local \$data = FileRead(\$in) Local \$FileArray = BinaryToString(\$data,4) ;~ \$FileArray = StringSplit(\$BinarydData, @CRLF, 1+2) ;~ Local \$FileArray = StringRegExp(\$BinarydData, "[^\r\n]+", 3) FileClose(\$in) _ArrayDisplay(\$FileArray,"\$FileArray","",32) MsgBox(\$MB_SYSTEMMODAL, "", "\$FileArray = " & \$FileArray )
TEST_labels.idx1-ubyte

• I'm searching a way to do xor and shift and if possible also other operations. Thanks in advance for the replies.
×

• Wiki
• AutoIt Resources

• FAQ
×
• Create New...