Rotating values within an array [SOLVED]

[TimRude]

Suppose I have a 1-D array with a number of values in it such as

Local $aArray[] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Then I want to select one of the values that should become the new first element, with the other elements rotating into new positions while keeping the array size the same.

For example, if I wanted $aArray[4] to become $aArray[0] and end up with an array that looks like this: 4 5 6 7 8 9 0 1 2 3

What would be the most efficient way to accomplish this, keeping in mind that the actual arrays I want to do this with will be much larger than this little sample one.

Here's a working method I've come up with using _ArrayExtract and _ArrayConcatenate but I'm not sure if there's a better way.

#include <Array.au3>

Local $aArray[] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
_ArrayDisplay($aArray, "BEFORE rotation")
_ArrayRotate($aArray, 4)
_ArrayDisplay($aArray, "AFTER rotation")

Exit

Func _ArrayRotate(ByRef $aArray, $iMakeFirst)

    ; $aArray = array to be rotated
    ; $iMakeFirst = element number to be rotated into position [0]
    ; Returns True if successful, False if not

    If Not IsArray($aArray) Then Return False ; invalid array
    If ($iMakeFirst < 0) Or ($iMakeFirst > UBound($aArray) - 1) Then Return False ; $iMakeFirst parameter is out of bounds
    If $iMakeFirst = 0 Then Return True ; no rotation needed, it's already the first element

    Local $aFirst = _ArrayExtract($aArray, $iMakeFirst)
    Local $aLast = _ArrayExtract($aArray, 0, $iMakeFirst - 1)
    Local $iResult = _ArrayConcatenate($aFirst, $aLast)
    If $iResult <> -1 Then
        $aArray = $aFirst
        Return True
    Else
        Return False
    EndIf

EndFunc   ;==>_ArrayRotate

 

Edited December 25, 2022 by TimRude

[Danp2]

Here's an alternative using _ArrayPush --

#include <Array.au3>

Local $avArrayTarget[] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
_ArrayDisplay($avArrayTarget, "BEFORE rotation")
_ArrayRotate($avArrayTarget, 4)
_ArrayDisplay($avArrayTarget, "AFTER rotation")


Func _ArrayRotate(ByRef $aArray, $iMakeFirst)
    ; $aArray = array to be rotated
    ; $iMakeFirst = element number to be rotated into position [0]
    ; Returns True if successful, False if not

    If Not IsArray($aArray) Then Return False ; invalid array
    If ($iMakeFirst < 0) Or ($iMakeFirst > UBound($aArray) - 1) Then Return False ; $iMakeFirst parameter is out of bounds
    If $iMakeFirst = 0 Then Return True ; no rotation needed, it's already the first element

    Local $aFirst = _ArrayExtract($aArray, 0, $iMakeFirst - 1)  
    Local $iResult = _ArrayPush($aArray, $aFirst)

    Return ($iResult = 1)
EndFunc

 

[pixelsearch]

@TimRude to do that, I scripted recently a function named _ArrayRowMove in this post.
Hope it helps

[Nine]

Maybe this one liner ? 

#include <Array.au3>

Local $avArrayTarget[] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
$arr = StringSplit(StringRegExpReplace(_ArrayToString($avArrayTarget), "(.*)\|(.+)", "$2\|$1"), "|", $STR_NOCOUNT)
_ArrayDisplay($arr)

 

[TimRude]

3 minutes ago, Nine said:

Maybe this one liner ? 

#include <Array.au3>

Local $avArrayTarget[] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
$arr = StringSplit(StringRegExpReplace(_ArrayToString($avArrayTarget), "(.*)\|(.+)", "$2\|$1"), "|", $STR_NOCOUNT)
_ArrayDisplay($arr)

 

This moves the last element to the beginning, but I don't know how you would use it to move an entire chunk of the array around. Perhaps in a loop? But then you end up doing a whole lot of converting array ==> string ==> array over and over again.

[TimRude]

I took my method, Danp2's method, and pixelsearch's method and ran each of them on an array consisting of a list of all of the filenames (including paths) in the @SystemDir folder. On my Win10 machine, that ended up being an array with 2891 entries. With each method, I asked it to take the bottom half of the array and move it to the top, and then to do it again so that it ended up back where it began. (Well almost, since I had an odd number of entries it ends up with the originally last entry as the first entry when finished, but that's just due to rounding and it ends up exactly the same with each of the methods.)

For each method, I timed how long it took to do these 2 iterations using TimerInit and TimerDiff. I ran each test 5 times, but each run was in a new instance of the test app. In other words, after running each test, the script Exited. I then ran the script again for a fresh run each time. The times listed do not include the time populating the array with the filenames. They're only the time taken to actually move the elements around.

Results:

My method with _ArrayExtract and _ArrayConcatenate: Average 28.5886 ms -- the slowest of the three

@Danp2 Your method with _ArrayExtract and _ArrayPush: Average 25.5905 ms -- marginally faster than mine

@pixelsearch Your method using none of the _Array UDF functions: Average 12.4234 ms -- you blew our doors off 😁

 

[Nine]

Then this one liner :

#include <Array.au3>
#include <String.au3>

Local $avArrayTarget[] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Local $iShift = 4
$arr = StringSplit(StringTrimRight(StringRegExpReplace(_ArrayToString($avArrayTarget, ","), "(" & _StringRepeat(".+?,", $iShift) & ")(.+)", "$2,$1"), 1), ",", $STR_NOCOUNT)
_ArrayDisplay($arr)

 

[TimRude]

@Nine Your method using RegExp averages 26.1187 ms, Faster than mine but slower than the other 2.

But I have to admit, yours looks the most like some kind of black magic out of all of the methods. I have no clue how yours works! 😵

[Nine]

I'll see if I can optimize it when I have some more time.  But it was fun thinking it differently.

[TimRude]

@Nine One other slight glitch with your RegExp method: If any of the array elements contain a comma, it messes everything up since you're using a comma as your delimiter. I may have thrown you off with my simplified example of just digits, but in actual practice the array will contain text that very well might have commas in it. For example, maybe a list of names (Last, First), or address information.

It's probably possible to switch to a different (less common) delimiter, but even then there's no way to be positive that any character used as a delimiter would never possibly be part of the array contents. So I'm not sure there is a 100% safe way to do it using RegExp since the data in the array has to live as delimited text as part of the process.

But as you say, definitely a different way to approach the task. Certainly some clever outside the box thinking. 🧠

[pixelsearch]

6 hours ago, TimRude said:

@Nine One other slight glitch with your RegExp method: If any of the array elements contain a comma, it messes everything up since you're using a comma as your delimiter. [...)but in actual practice the array will contain text that very well might have commas in it. For example, maybe a list of names (Last, First), or address information.

If we think of it that way, then the array may also contain the pipe character "|" which is also a delimiter in plenty of functions and will mess everything when a script uses it as delimiter, in case the pipe character is found inside strings.

Below are Nine's scripts (both editions he posted above), splitted to experiment and try to understand better the logic of his one-liner scripts. You can uncomment the #cs #ce parts in the scripts to run only the desired part (be lazy when you uncomment each block of #cs #ce, not greedy) 

At the very end of the scripts, a delimiter such as ChrW(63743) has been added, not sure you'll find it in usual strings. I think the only way to make sure a delimiter isn't part of the strings wouid be to check several characters (for example starting with ChrW(65535) then descending) so you'll make sure this "delimiter character" won't be found in the strings, but it may take some time if the array is huge.

1st edition (one part is already uncommented)

#cs
; Nine's original (1st edition) | delimiter
; =========================================
#include <Array.au3>

Local $avArrayTarget[] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
$arr = StringSplit(StringRegExpReplace( _
    _ArrayToString($avArrayTarget), "(.*)\|(.+)", "$2\|$1"), _
    "|", $STR_NOCOUNT)
_ArrayDisplay($arr)
#ce



; #cs
; 1st edition detailed: | delimiter
; ==================================
#include <Array.au3>

Local $avArrayTarget[] = ["100", "200", "300", "400", "500", "600", "700", "800", "900"]
_ArrayDisplay($avArrayTarget, "Array before")

Local $sString1 = _ArrayToString($avArrayTarget) ; default delimiter is |
ConsoleWrite("$sString1 = " & $sString1 & @crlf) ; "100|200|300|400|500|600|700|800|900"

Local $sString2 = StringRegExpReplace($sString1, "(.*)\|(.+)", "$2\|$1") ; as greedy, then (.+) or (.*)
ConsoleWrite("$sString2 = " & $sString2 & @crlf) ; "900|100|200|300|400|500|600|700|800"

Local $arr = StringSplit($sString2, "|", $STR_NOCOUNT)
_ArrayDisplay($arr, "Array after")
; #ce

2nd edition below (one part is already uncommented)

expandcollapse popup

#cs
; Nine's original (2nd edition) comma delimiter
; =============================================
#include <Array.au3>
#include <String.au3>

Local $avArrayTarget[] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Local $iShift = 4
$arr = StringSplit(StringTrimRight(StringRegExpReplace( _
    _ArrayToString($avArrayTarget, ","), "(" & _StringRepeat(".*?,", $iShift) & ")(.+)", "$2,$1"), _
    1), _
    ",", $STR_NOCOUNT)
_ArrayDisplay($arr)
#ce



#cs
; 2nd edition detailed: comma delimiter
; =====================================
#include <Array.au3>
#include <String.au3>

Local $avArrayTarget[] = ["100", "200", "300", "400", "500", "600", "700", "800", "900"]
_ArrayDisplay($avArrayTarget, "Array before")

Local $iShift = 4
Local $sShift = _StringRepeat(".*?,", $iShift)
ConsoleWrite("$sShift = " & $sShift & @crlf) ; ".*?,.*?,.*?,.*?,"

Local $sString1 = _ArrayToString($avArrayTarget, ",")
ConsoleWrite("$sString1 = " & $sString1 & @crlf) ; "100,200,300,400,500,600,700,800,900"

Local $sString2 = StringRegExpReplace($sString1, "(" & $sShift & ")(.+)", "$2,$1") ; as greedy, then (.+) or (.*)
ConsoleWrite("$sString2 = " & $sString2 & @crlf) ; "500,600,700,800,900,100,200,300,400,"

Local $sString3 = StringTrimRight($sString2, 1)
ConsoleWrite("$sString3 = " & $sString3 & @crlf) ; "500,600,700,800,900,100,200,300,400"

Local $arr = StringSplit($sString3, ",", $STR_NOCOUNT)
_ArrayDisplay($arr, "Array after")
#ce



#cs
; 2nd edition detailed: | delimiter
; =================================
#include <Array.au3>
#include <String.au3>

Local $avArrayTarget[] = ["100", "200", "300", "400", "500", "600", "700", "800", "900"]
_ArrayDisplay($avArrayTarget, "Array before")

Local $iShift = 4
Local $sShift = _StringRepeat(".*?\|", $iShift)
ConsoleWrite("$sShift = " & $sShift & @crlf) ; ".*?\|.*?\|.*?\|.*?\|"

Local $sString1 = _ArrayToString($avArrayTarget) ; default delimiter is |
ConsoleWrite("$sString1 = " & $sString1 & @crlf) ; "100|200|300|400|500|600|700|800|900"

Local $sString2 = StringRegExpReplace($sString1, "(" & $sShift & ")(.+)", "$2\|$1") ; as greedy, then (.+) or (.*)
ConsoleWrite("$sString2 = " & $sString2 & @crlf) ; "500|600|700|800|900|100|200|300|400|"

Local $sString3 = StringTrimRight($sString2, 1)
ConsoleWrite("$sString3 = " & $sString3 & @crlf) ; "500|600|700|800|900|100|200|300|400"

Local $arr = StringSplit($sString3, "|", $STR_NOCOUNT)
_ArrayDisplay($arr, "Array after")
#ce



; #cs
; 2nd edition detailed: | delimiter without _StringRepeat but using RegEx {...} quantifier
; ========================================================================================
#include <Array.au3>

Local $iShift = 4

Local $avArrayTarget[] = ["100", "200", "300", "400", "500", "600", "700", "800", "900"]
_ArrayDisplay($avArrayTarget, "Array before")

Local $sString1 = _ArrayToString($avArrayTarget) ; default delimiter is |
ConsoleWrite("$sString1 = " & $sString1 & @crlf) ; "100|200|300|400|500|600|700|800|900"

Local $sString2 = StringRegExpReplace($sString1, "((?:.*?\|){" & $iShift & "})(.+)", "$2\|$1") ; as greedy, then (.+) or (.*)
ConsoleWrite("$sString2 = " & $sString2 & @crlf) ; "500|600|700|800|900|100|200|300|400|"

Local $sString3 = StringTrimRight($sString2, 1)
ConsoleWrite("$sString3 = " & $sString3 & @crlf) ; "500|600|700|800|900|100|200|300|400"

Local $arr = StringSplit($sString3, "|", $STR_NOCOUNT)
_ArrayDisplay($arr, "Array after")
; #ce



#cs
; 2nd edition detailed: ChrW(63743) delimiter without _StringRepeat but using RegEx {...} quantifier
; ==================================================================================================
#include <Array.au3>

Local $iShift = 4, $sSeparator = ChrW(63743)

Local $avArrayTarget[] = ["100", "200", "300", "400", "500", "600", "700", "800", "900"]
_ArrayDisplay($avArrayTarget, "Array before")

Local $sString1 = _ArrayToString($avArrayTarget, $sSeparator)
ConsoleWrite("$sString1 = " & $sString1 & @crlf)

Local $sString2 = StringRegExpReplace($sString1, "((?:.*?" &$sSeparator & "){" & $iShift & "})(.+)", "$2" & $sSeparator & "$1")
ConsoleWrite("$sString2 = " & $sString2 & @crlf)

Local $sString3 = StringTrimRight($sString2, 1)
ConsoleWrite("$sString3 = " & $sString3 & @crlf)

Local $arr = StringSplit($sString3, $sSeparator, $STR_NOCOUNT)
_ArrayDisplay($arr, "Array after")
#ce

 

9 hours ago, TimRude said:

@pixelsearch Your method using none of the _Array UDF functions: Average 12.4234 ms -- you blew our doors off

"to blow doors off" : thanks for teaching me this expression as english isn't my native language. Always great to learn something new 

Edited December 24, 2022 by pixelsearch
typo

[jchd]

13 hours ago, TimRude said:

For example, if I wanted $aArray[4] to become $aArray[0] and end up with an array that looks like this: 4 5 6 7 8 9 0 1 2 3

What would be the most efficient way to accomplish this

Leave the array alone and access its elements using an offset and Mod() the array size.

Local $aOrig = [0,1,2,3,4,5,6,7,8,9]

Func ArrOfs(ByRef $a, $iOfs, $iIdx)
    Return($a[Mod($iOfs + $iIdx, UBound($a))])
EndFunc

ConsoleWrite("New element of $aOrig at index 0 is " & ArrOfs($aOrig, 4, 0) & @LF)
ConsoleWrite("New element of $aOrig at index 7 is " & ArrOfs($aOrig, 4, 7) & @LF)

; if you really need to permanently change the array, elements index offset by $n:
Func ArrMove(ByRef $a, $n)
    Local $iSize = UBound($a)
    Local $b[$iSize]
    For $i = 0 To $iSize - 1
        $b[$i] = $a[Mod($i + $n, $iSize)]
    Next
    $a = $b
EndFunc

ArrMove($aOrig, 4)
_ArrayDisplay($aOrig)

 

[OJBakker]

My version uses only ArrayToString, ArrayFromString and string functions. It won't rotate if the default delimiter is found in the array.

#include <Array.au3>

Local $aArray[] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
_ArrayDisplay($aArray, "BEFORE rotation")
If _ArrayRotate($aArray, 4) Then
    _ArrayDisplay($aArray, "AFTER rotation")
Else
    MsgBox(Default, Default, "Array did not rotate!")
EndIf

Exit

Func _ArrayRotate(ByRef $aArray, $iMakeFirst)

    ; $aArray = array to be rotated
    ; $iMakeFirst = element number to be rotated into position [0]
    ; Returns True if successful, False if not

    If Not IsArray($aArray) Then Return False ; invalid array
    If ($iMakeFirst < 0) Or ($iMakeFirst > UBound($aArray) - 1) Then Return False ; $iMakeFirst parameter is out of bounds
    If $iMakeFirst = 0 Then Return True ; no rotation needed, it's already the first element

    If StringInStr(_ArrayToString($aArray, ""), "|") Then Return False ; default delimiter found in array

    Local $sArray = _ArrayToString($aArray)
    Local $iPos = StringInStr($sArray, "|", $STR_NOCASESENSE, $iMakeFirst)
    Local $sFirst = StringLeft($sArray, $iPos - 1)
    Local $sLast = StringRight($sArray, StringLen($sArray) - $iPos)
    $aArray = _ArrayFromString($sLast & "|" & $sFirst)
    Return True

EndFunc   ;==>_ArrayRotate

 

[jugador]

Local $aArray[] = ["000", "100", "200", "300", "400", "500", "600", "700", "800", "900"]
_ArrayDisplay(__ArrayRotate($aArray, 4))

Func __ArrayRotate(ByRef $aArray, $iIndex, $sSeparator = '|')
    Return StringRegExp(StringRegExpReplace(_ArrayToString($aArray, $sSeparator), '(.*?)\'& $sSeparator  &'(?=' & $aArray[$iIndex] & ')(.*)', _
                                            '$2\' & $sSeparator & '$1'), '([^\' & $sSeparator & ']+)', 3)
EndFunc

 

[Werty]

Doubling the array...

#Include <Array.au3>

Local $aArray[] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

_ArrayRotate($aArray, 4)

Func _ArrayRotate(ByRef $aArray, $iShift)
   Local $aArray2[] = $aArray
   _ArrayAdd($aArray2, $aArray)
   For $i = 0 To UBound($aArray) - 1
      $aArray[$i] = $aArray2[$i + $iShift]
   Next
EndFunc

_ArrayDisplay($aArray)

 

[TimRude]

To complete the results:

@jchd Your ArrMove method averaged 24.3164 ms

@Werty Your method averaged 73.2607 ms - thanks for pulling me out of last place! 😁

The other methods that convert the array to a delimited string I'm going to rule out (for me) because of the danger of scrambled results due to a delimiter character possibly being within the array data. Those methods have certainly presented some interesting approaches, but I don't think they're 100% reliable.

So in order of speed, with the fastest at the top, we've ended up with:

pixelsearch

jchd

Danp2

TimRude

Werty

Also, it may be worth noting for posterity's sake that while I asked about doing this for a 1D array, the methods used by pixelsearch and myself will also handle 2D arrays, whereas the others work on 1D arrays only.

Thanks everyone for your examples!

Edited December 25, 2022 by TimRude

[pixelsearch]

Incredible that we got so many different solutions in this thread, well done guys !

It makes me realize that my way of thinking is a bit odd... for example when OP got nearly the same question in the other thread (where I scripted _ArrayRowMove), I didn't script it for him only, having in mind that maybe the array could be 1D or 2D, maybe the block of rows to move should be placed at bottom of the array and not always on top etc...

Well, I guess we all got a different way of thinking, it's a bit too late to change it 

Edit: didn't realize TimRude just answered before me !

Edited December 25, 2022 by pixelsearch

[RTFC]

10 hours ago, TimRude said:

handle 2D arrays

Instead of moving large data chunks around, you could just operate on a 1D numeric index array with which to access your 2D data.

EDIT: in this case, E4A would do this in a fraction of the time (about 3 ms on my machines):

Spoiler

#include "Eigen4AutoIt.au3"

_Eigen_StartUp()

$rows=2891
$newtop=int($rows/2)

$matData = _Eigen_CreateMatrix_LinSpaced_Rowwise ( $rows, 1, 0, $rows-1 )
;_MatrixDisplay ( $matA, "matrix A" )

$timer=TimerInit()
$matA = _Eigen_Remap_MatrixRows ( $matData, $newtop, $rows-$newtop )
$matB = _Eigen_Remap_MatrixRows ( $matData, 0, $newtop )
$matR = _Eigen_CreateMatrix_FromABrows ( $matA, $matB )
$diff=TimerDiff($timer)
_MatrixDisplay ( $matR, $diff & " ms")

_Eigen_CleanUp()

; NB _Eigen_Remap_MatrixRows is unfortunately absent from current release, but looks like this (copy & paste it into Eigen4Autoit.au3):

Func _Eigen_Remap_MatrixRows($matA, $firstrow, $rows, $E4Asln = @ScriptLineNumber)
    ; returns new index to $matrixList (matID)

    Local $procname = "_Eigen_Remap_MatrixRows"
    _Eigen_Callstack_Push($procname, $E4Asln)

    If Not IsInt($firstrow) Or $firstrow < 0 Then Return SetError(_Eigen_Callstack_ErrorHandler(-2, "invalid matrix row coordinate (firstrow = " & $firstrow & ")", $procname, Default, $E4Asln), 0, False)
    If Not IsInt($rows) Or $rows <= 0 Then Return SetError(_Eigen_Callstack_ErrorHandler(-2, "invalid matrix rows dimension (rows = " & $rows & ")", $procname, Default, $E4Asln), 0, False)

    Local $matA_ptr = _Eigen_GetPtr($matA, "A", Default, Default, $E4Asln)
    If @error Or $matA_ptr = 0 Then Return SetError(_Eigen_Callstack_ErrorHandler(-3, "unable to retrieve valid matrix pointer", $procname, Default, $E4Asln), 0, False)
    If _Eigen_Check_Row($matA, $firstrow, $E4Asln) = False Then Return SetError(_Eigen_Callstack_ErrorHandler(-2, "invalid matrix row coordinate (firstrow = " & $firstrow & ")", $procname, Default, $E4Asln), 0, False)
    If _Eigen_IsVector($matA, $E4Asln) = False Then Return SetError(_Eigen_Callstack_ErrorHandler(-2, "source matrix should be a vector", $procname, Default, $E4Asln), 0, False)

    Local $offset = 0
    If $firstrow > 0 Then
        $offset = $firstrow * _Eigen_MatrixTypeID_ToBytes($matrixList[$matA][3])
        If @error Then Return SetError(_Eigen_Callstack_ErrorHandler(-2, "invalid matrix type definition", $procname, Default, $E4Asln), 0, False)
    EndIf

    ; update MatrixList entry
    Local $newmatID = _Eigen_GetNewMatrixID($E4Asln)

    $matrixList[$newmatID][1] = $rows
    $matrixList[$newmatID][2] = 1
    $matrixList[$newmatID][3] = $matrixList[$matA][3]
    $matrixList[$newmatID][4] = Ptr($matA_ptr + $offset)
    $matrixList[$newmatID][5] = StringTrimLeft($procname, 7) & ":" & $matA
    $matrixList[$newmatID][6] = False
    $matrixList[$newmatID][7] = True
    $matrixList[0][0] = $newmatID

    ; flag source matrix as remapped
    $matrixList[$matA][6] = True

    Switch @AutoItX64
        Case False
            $matrixList[$newmatID][0] = DllStructCreate(_Eigen_MatrixTypeID_ToTypeLabel($matrixList[$matA][3]) & "[" & $rows * (1 + _Eigen_IsComplex($matA, $E4Asln)) & "]", Ptr($matA_ptr + $offset))
    EndSwitch
    If $EIGEN_VERBOSE = True Then ConsoleWrite("E4A Remapping (" & $matrixList[$matA][1] & "," & $rows & ") from row " & $firstrow & " of existing matrix ID " & $matA & " with new matrix ID: " & $matA & @CRLF)

    $EIGEN_ML_HASCHANGED = True
    If $EIGEN_ML_HASCHANGED_UDF <> "" Then Call($EIGEN_ML_HASCHANGED_UDF)

    _Eigen_Callstack_Pop($procname)
    Return $newmatID
EndFunc   ;==>_Eigen_Remap_MatrixRows

 

 

Edited December 25, 2022 by RTFC
shameless bragging

[TimRude]

11 hours ago, RTFC said:

Instead of moving large data chunks around, you could just operate on a 1D numeric index array with which to access your 2D data

I'm not actually working with a 2D array. But I have ended up creating a second array that holds just the index numbers of the first array that holds the actual data. Then I do my rotating on the index-array.

As such, pretty much any of the suggested methods then become fast enough.

Edited December 25, 2022 by TimRude