Reversing orders of arrays/strings/lists

[MindCaged]

I was just wondering what the most efficient way of reversing string, array, and list order would be.
I define a "list" as a delimited string like "1,2,3" or "A|B|C" or even "The quick brown fox..."(space is the delimiter", etc.

For a string the best I can think of is this:(Only really tested with ANSI, but should work since the offset is 0-based.) (Not the best function, look at LinearSpoon below.)

Code: Select all

reverse_string(ByRef p_In) { ; Byref is more efficient with larger strings.
	iLen := StrLen(p_In) ; Get the number of characters.
	; ANSI is 1 byte characters, Unicode is 2-byte
	dType := A_IsUnicode?"UShort":"UChar"
	dLen := A_IsUnicode?2:1
	; Set the capacity of the output string.
	VarSetCapacity(sOut, (iLen + 1) * dLen, 0) ; Add 1 to allocate a null terminator.
	while (A_Index <= iLen) ; Loop through each character.
	{	V := NumGet(p_In, (iLen - A_Index) * dLen, dType) ; Get each character from memory.
		NumPut(V, sOut, (A_Index-1)*dLen, dType) ; Write to the opposite end of the output string.
	}
	return sOut
}

(I could also put the NumGet and NumPut on the same line and skip the V variable all together.)

Anyway, I'm also looking for code to do that but for delimited lists and enumerating backwards through array/objects, etc. But for those all I can think of is creating another array and writing all the keys in reverse order then using that to enumerate.

Edit: Here's a function I came up with for reversing a delimited list, if anybody can come up with a better/faster function let me know.

Code: Select all

reverse_list(ByRef p_In, p_Delim=" ", p_Case=1) {
	VarSetCapacity(sOut, VarSetCapacity(p_In))
	i2 := StrLen(p_In) + 1
	dLen := StrLen(p_Delim)
	while (i1:=Instr(p_In, p_Delim, p_Case, 0, A_Index))>0
	{	sOut .= ((A_Index > 1)?p_Delim:"") . SubStr(p_In, i1+dLen, (i2-i1)-1)
		i2 := i1
	}
	sOut .= ((sOut = "")?"":p_Delim) . SubStr(p_In, 1, i2-1)
	return sOut
}

Edit: Some mentioned problems hopefully fixed about the null terminator and delimiter length, but LinearSpoon apparently gives a much better function below.
Although I'm still looking for the best way to enumerate backwards through an object. The only thing I can think of would be to enumerate forwards, add the keys to another array in reverse order, then enumerate that for the keys.

[LinearSpoon]

Your reverse_string can fail quite spectacularly in the right situation because you don't copy the null terminator.
Your reverse_list also seems to have a problem with delimiters longer than one character where parts of the delimiter are copied more than once.

This solution averages about twice the speed of your functions, and serves the purpose of both reverse_string and reverse_list. The speed difference can most likely be attributed to overhead in the expression parser and numget/numput calls.

Code: Select all

;pass "" or omit p_Delim for character by character string reverse
;Pass any other string for p_Delim to use that as a delimiter for a list reverse
StrReverse(input, p_Delim="") ;byref here would destroy the input string
{
  VarSetCapacity(output, Strlen(input)*(A_IsUnicode ? 2 : 1))
  if (StrLen(p_Delim) > 1)  ;Loop, Parse does not handle multi character delimiters
    StringReplace, input, input, %p_Delim%, % chr(2), All  ;chr(2) is very unlikely to be found in any string
  Loop, Parse, input, % StrLen(p_Delim) > 1 ? chr(2) : p_Delim
    output := A_LoopField p_Delim output
  return StrLen(p_Delim) ? RegexReplace(output, p_Delim "$") : output ;trim delimiter if necessary
}

[just me]

VarSetCapacity():
RequestedCapacity

...does not include the internal zero terminator. For example, specifying 1 would allow the variable to hold up to one byte in addition to its internal terminator.

[LinearSpoon]

Edited. The first problem remains.

[just me]

You don't need to copy the null terminator, it's already there. But you will need VarSetCapacity(sOut, -1) in very most cases to udate the internal variable length.

[LinearSpoon]

You don't need to copy the null terminator, it's already there.

Not after overwriting it with numput.

[just me]

Hmmm, I cannot see where this should happen:

Code: Select all

    while (A_Index <= iLen) ; Loop through each character.
    {   V := NumGet(p_In, (iLen - A_Index) * dLen, dType) ; Get each character from memory.
        NumPut(V, sOut, (A_Index-1)*dLen, dType) ; Write to the opposite end of the output string.
    }

[MindCaged]

Yeah, I only wrote the first function that way since I wasn't sure how efficient the append operation was, but I guess it's not too bad if you allocate the memory first with VarSetCapacity. I know that in the past I've had trouble where appending characters onto a string repeatedly constantly reallocates more memory with each operation. I was writing a script in Lua to transform all the characters in a string to an escaped version, but I was appending the resulting values one character at a time to the output string which was constantly allocating more memory. It really lagged out. I finally found the solution online by adding all the characters to a table then doing a table.join() at the end. Again, I guess this is overly engineered. Because I can set the capacity here, and it only needs to reallocate if the capacity changes. I suppose without the VarSetCapacity, just using the append operation over and over with a large string would really slow down.

And the list function, yeah, I forgot to figure in delimiter length, I've had that problem in the past, but I literally wrote that function off the top of my head last night. It's a really easy fix, just store the delimiter length in a variable like dLen at the start(I assume it's faster than calling StrLen over and over like most languages, haven't tested.) and change i1+1 on the one line to i1+dLen. Anyway, if append works just fine then that simplifies things greatly. Like I said, in some languages it's actually faster/more efficient to go a somewhat roundabout method, so sorry if it was needlessly complicated as I kinda skipped over the simpler solution.

LinearSpoon gives a much better function it looks like. I guess more complicated isn't better in this situation.

Edit: Just ran my own benchmarks, and while for a delimited list my reverse_list function seems comparable to LinearSpoon's StrReverse(probably since it's almost the same, I get conflicting info on which is faster with each try), my attempt to make a faster string version failed miserably as it consistently takes much longer.

[just me]

Edit: Just ran my own benchmarks, and while for a delimited list my reverse_list function seems comparable to LinearSpoon's StrReverse(probably since it's almost the same, I get conflicting info on which is faster with each try), my attempt to make a faster string version failed miserably as it consistently takes much longer.

Did you run it with longer strings (e.g. 16 KB):

Code: Select all

#NoEnv
SetBatchLines, -1
Test := "12345678"
MsgBox, 0, Functional Test, % "Test = " Test "`n`nOutputs:"
                            . "`nreverse_string(Test): " reverse_string(Test)
                            . "`nStrReverse(Test): " StrReverse(Test)
Loop, 11
   Test .= Test
MsgBox, 0, Test with Length, % "StrLen(Test) = " StrLen(Test)
Loop, 3 {
   S := A_TickCount
   R1 := reverse_string(Test)
   T1 := A_TickCount - S
   S := A_TickCount
   R2 := StrReverse(Test)
   T2 := A_TickCount - S
   MsgBox, 0, Results, % "reverse_string() = " T1 " ms`n" "StrReverse() = " T2 " ms`n"
                       . "(R1 == R2) = " (R1 == R2 ? "True" : "False")
}
ExitApp
; ----------------------------------------------------------------------------------------------------------------------
; by MindCaged
reverse_string(ByRef p_In) { ; Byref is more efficient with larger strings.
    iLen := StrLen(p_In) ; Get the number of characters.
    ; ANSI is 1 byte characters, Unicode is 2-byte
    dType := A_IsUnicode?"UShort":"UChar"
    dLen := A_IsUnicode?2:1
    ; Set the capacity of the output string.
    VarSetCapacity(sOut, iLen  * dLen, 0) ; <<<<< changed, you don't need to add space for the terminator
    while (A_Index <= iLen) ; Loop through each character.
    {   V := NumGet(p_In, (iLen - A_Index) * dLen, dType) ; Get each character from memory.
        NumPut(V, sOut, (A_Index-1)*dLen, dType) ; Write to the opposite end of the output string.
    }
    VarSetCapacity(sOut, -1) ; <<<<< added!
    return sOut
}
; ----------------------------------------------------------------------------------------------------------------------
; by LinearSpoon (reduced for plain string test)
StrReverse(ByRef Input)
{
  VarSetCapacity(Output, Strlen(Input) * (A_IsUnicode ? 2 : 1), 0)
  Loop, Parse, Input
    Output := A_LoopField Output
  Return Output
}

reverse_string() is about 10 times faster here.

[LinearSpoon]

I concede this. StrReverse is faster for short strings, but much slower for long strings. The cost of rebuilding output for each character catches up to it.

[MindCaged]

Hmm, I just tested that. I created a really huge string(16000 characters) and ran it through each function 10 times and averaged it out. I also used Critical as that's been giving me better results. StrReverse took between 6 to 16 times longer for me with a 16000 character string than my reverse_string did, interesting. Not sure how often you'd need to reverse a string that long, but it's interesting.

I just made an upgraded function that seems even slightly faster.

Code: Select all

reverse_string2(p_S) {
	; Figure out ansi or unicode
	dType := A_IsUnicode?"UShort":"UChar"
	dLen := A_IsUnicode?2:1
	; Record the beginning and ending character offsets.
	i1 := 0
	i2 := (StrLen(p_S) - 1) * dLen
	while (i1 < i2) ; Swap beginning and end until you meet in the middle.
	{	V := NumGet(p_S, i2, dType)
		NumPut(NumGet(p_S, i1, dType), p_S, i2, dType)
		NumPut(V, p_S, i1, dType)
		i1 += dLen ; Update offsets.
		i2 -= dLen
	}
	return p_S
}

This is actually how I've seen it done in a C++ example as well as others. In my comparison testing, between StrReplace() and string_replace(), string_replace starts overtaking StrReplace() at around 1K characters, string_replace2() starts overtaking it at around 800. And consistently runs faster than string_replace().

Edit: Err, oops. I made a mistake.
Edit again: Fixed it now, I didn't actually check the output to see it was actually reversed... *facepalm*

At this point I don't think it can be improved anymore inside AHK, the only way I can see it getting any faster is if it's written in C/C++ and maybe called with DllCall or directly into assembly.

[LinearSpoon]

Try this.

Code: Select all

MCodeStrReverse(byref input)
{
  static reverse ;static avoids need to recompile mcode each call
  if (!reverse)
  {
    if A_IsUnicode
      reverse := MCode("
      (LTrim Join
      1,x86:8b4c240c568b742408498d0c4e3bce721c8b54240c668b018d520283e902668942fe3bce73ef33c06689025ec38b44
      240c33c95e668908c3,x64:418bc048ffc8488d0441483bc1721790440fb7004883e802488d520266448942fe483bc173ea3
      3c0668902c3
      )")
    else
      reverse := MCode("
      (LTrim Join
      1,x86:8b44240c48568b74240803c63bc672168b54240c8a088d520148884aff3bc673f3c602005ec38b44240c5ec60000c3
      )")
  }
  VarSetCapacity(output, 2*strlen(input))
  DllCall(reverse, "str", input, "str", output, "uint", strlen(input), "Cdecl")
  return output
}

;Credit: Bentschi @ http://www.autohotkey.com/board/topic/89283-mcode-function-onlinegenerator-x86-and-x64/
MCode(mcode)
{
  static e := {1:4, 2:1}, c := (A_PtrSize=8) ? "x64" : "x86"
  if (!regexmatch(mcode, "^([0-9]+),(" c ":|.*?," c ":)([^,]+)", m))
    return
  if (!DllCall("crypt32\CryptStringToBinary", "str", m3, "uint", 0, "uint", e[m1], "ptr", 0, "uint*", s, "ptr", 0, "ptr", 0))
    return
  p := DllCall("GlobalAlloc", "uint", 0, "ptr", s, "ptr")
  if (c="x64")
    DllCall("VirtualProtect", "ptr", p, "ptr", s, "uint", 0x40, "uint*", op)
  if (DllCall("crypt32\CryptStringToBinary", "str", m3, "uint", 0, "uint", e[m1], "ptr", p, "uint*", s, "ptr", 0, "ptr", 0))
    return p
  DllCall("GlobalFree", "ptr", p)
}

C++ source:

Code: Select all

//reverseW is the same except wchar_t type
void reverseA(const char* input, char* output, unsigned int len)
{
	for (const char* ip = input + len - 1; ip >= input; ip--, output++)
	{
		*output = *ip;
	}
	*(output++) = 0;
}

[trismarck]

The following will get nowhere near LinearSpoon's version, but anyway, just for the reference, as the idea of assigning to other variable (vs using VarSetCapacity() + StrLen() ) might be a little faster.

Code: Select all

str := "abcdefghij"
str_reverse(str)
MsgBox, % str
str_reverse(ByRef in){
	if A_IsUnicode
	{
		tmp:=in,i:=StrLen(in)<<1,j:=-2
		while(i) 
			i-=2,j+=2,NumPut(NumGet(tmp,i,"UShort"),in,j,"UShort")
		return in
	}
	else
	{
		tmp:=in,i:=StrLen(in),j:=-1
		while(i)
			i--,j++,NumPut(NumGet(tmp,i,"UChar"),in,j,"UChar")
		return in
	}
}

[jNizM]

Just fyi
shortest version (not fastest)

Code: Select all

reverse(s)
{
    l := StrLen(s)
    return l < 2 ? s : (SubStr(s, l, 1) reverse(SubStr(s, 1, l-1)))
}

Msgbox % reverse("abcdefg")

[just me]

The recursive calls will crash AHK (stack overflow) for strings longer than 373 (U64), 587 (U32), and 758 (A32) characters (at least on my system).

But the good old SubStr() is pretty fast compared to other plain AHK versions:

Code: Select all

ReverseStr(ByRef Input) {
   VarSetCapacity(Output, (L := StrLen(Input)) << !!A_IsUnicode)
   While (L)
      Output .= SubStr(Input, L--, 1)
   Return Output
}

[jNizM]

and this one?

Code: Select all

StringReverse(str)
{
    static rev := A_IsUnicode ? "_wcsrev" : "_strrev"
    DllCall("msvcrt.dll\" rev, "UInt", &str, "CDECL")
    return str
}

MsgBox % StringReverse("01234 56789")        ; ==> 98765 43210

MSDN: _strrev, _wcsrev, _mbsrev, _mbsrev_l

[just me]

Nice, but don't you think that the type of &str should be "Ptr"?

[jNizM]

Is there a difference in the result?

I think this is an ahk problem (just ja few snippets from main)

Code: Select all

DllCall("msvcrt.dll\_strrev", Str, "autohotkey", UInt, 0, Str)
DllCall("msvcrt.dll\_strrev", "UInt", &Str, "CDecl")
DllCall("msvcrt.dll\_strrev", "str", "autohotkey", "cdecl str")
DllCall("msvcrt.dll\_strrev", "str", "autohotkey", "cdecl")

We need more informations in the docs like Bentschis try Windows_Data_Types

[just me]

"Ptr" <> "Str" -> Types of Arguments and Return Values
The address of a variable (&str) is a pointer and might be truncated on U64 if the value exceeds 32 bit and the type is specified as "UInt".

[jNizM]

ok..
DllCall("msvcrt.dll\" rev, "Str", str, "CDECL") works
DllCall("msvcrt.dll\" rev, "Ptr", &str, "CDECL") works
Both works. Which one should I use or prefer?