ROL ROR

Rikudo · 20. August 2016, 15:58

Heyyo

Ich habe ein byte[] mit n Elementen.
Ich möchte nun eine ROL (RotateLeft) bzw ROR (RotateRight) operation durchführen.
Das heißt die element nach rechts bzw lniks verschieben. Das ganze soll aber circular sein, d.h. dass das letzte byte wieder
am anfang drangepackt wird.
Gibt es da evtl eine default Funktion vom Framework oder muss ich es per hand mit einem for loop machen?

wolfi_bayern · 20. August 2016, 16:17

Hallo!
Mach eine list of byte, nimm das letzte element und füge es per insert an position 0 wieder ein bzw. Andersrum je nach schiebewunsch und wandle danach die liste wieder zurück in ein array

nafets · 20. August 2016, 17:03

Mit Linq würde es gehen (erst Skip, dann Concat bzw. Concat & Take).

~blaze~ · 20. August 2016, 17:41

Hi
es gibt zwei Lösungsmöglichkeiten: Mit zusätzlichem Array der Größe k, es wird um k rotiert, oder ohne. Im ersten Fall ist es trivial (hier nur die Linksrotation, rechts ist analog): Kopiere die Einträge 0 bis k-1 in den Puffer, kopiere die Einträge k bis n (= Zahl der Elemente - 1) im Ziel an die Stellen 0 bis n-k und kopiere dann aus dem Puffer zurück an die Stellen n-k+1 bis n.

Ohne Puffer ist's komplizierter: Wähle ein beliebiges l mit 0 <= l < n, n ist hier nicht der maximale Index, sondern die Länge des Arrays.
Wiederhole für m=0..k-1: Merke dir v=l+m. Setze i auf v.
Wiederhole: Merke dir den Wert an j=(-k+n+i)%n (Vorsicht Überlauf möglich) und kopiere den i-ten Wert an j. Setze i auf i-k. Wenn j < v, beende die Schleife (sind übrigens im Durchschnitt n/k Durchläufe)

Jetzt sollte eigentlich alles passen.

Mein Algo ließe sich auch auf den Puffer übertragen. Unter Verwendung des ThreadStaticAttribute-Attributs ließe sich zudem ein solcher Puffer wiederverwenden. Er muss halt hinreichend groß sein (d.h., die Länge des Puffers muss mindestens k sein), ansonsten musst du den Algorithmus auf Puffer anwenden

Edit: Gerade gemerkt, dass es mit dem Algorithmus ohne Puffer gar nicht funktionieren kann, wenn n%k=0. Man muss solange iterieren, bis man ein bereits besuchtes Element erreicht und dann ein nicht besuchtes wählen.
Es muss also gelten, dass (x*n) % k = 0, dann wird im der x-ten Runde abgebrochen und ein nicht verschobenes Element gewählt. Verschoben wurden dann im letzten Durchlauf alle ((v % k)*p)%k=0-Werte, wobei p eine Zahl zwischen 1 und x (oder x-1, ist mir grad zu spät) ist. Also wählt man als nächstes einen Wert für v, für den ((v%k)*p)% 0 für alle bisherigen v nicht zutrifft. Das sollte eigentlich einfach in seiner Bestimmung sein, aber dafür bin ich zu müde.

Viele Grüße
~blaze~

exc-jdbi · 21. August 2016, 00:42

@Rikudo

Für primitive Datentypnen gibt es die buffer.BlockCopy

Sollte Funktioniere ungetestet

VB.NET-Quellcode

Option Strict On
Option Explicit On
Module Module1
Public Function shiftLeft(ByVal b As Byte(), ByVal n As Integer) As Byte()
Dim dst(b.Length - 1) As Byte
Buffer.BlockCopy(b, n, dst, 0, b.Length - n)
Buffer.BlockCopy(b, 0, dst, b.Length - n, n)
Return dst
End Function
Public Function shiftRight(ByVal b As Byte(), ByVal n As Integer) As Byte()
Dim dst(b.Length - 1) As Byte
Buffer.BlockCopy(b, 0, dst, n, b.Length - n)
Buffer.BlockCopy(b, b.Length - n, dst, 0, n)
Return dst
End Function
Sub Main()
Dim b As Byte() = {1, 2, 3, 4, 5, 6, 7, 8}
Dim bResR As Byte() = shiftRight(b, 1)
Dim bResL As Byte() = shiftLeft(b, 1)
End Sub
End Module

Freundliche Grüsse

exc-jdbi

exc-jdbi · 22. August 2016, 18:24

Hallo Community

Hab heute abend noch kurz Zeit gefunden für einen Test. Wollte wissen, wie die Zeiten sind.
Ich vermute mal, dass es bei den String-Varianten sogar noch bessere Methoden gibt. Über den Stringbuilder jedoch nicht .?

Hier meine Zeitergebnisse

Quellcode

Enter für die Zeitmessung Byte - blockCopy vs. array.copy
Zeit für n = 1000000: 387 ms
Zeit für n = 1000000: 452 ms
Differenz: -65 ms
Enter für die Zeitmessung Byte - skip/take Enumerable
Zeit für n = 1000000: 10055 ms
Differenz: -9668 ms
Enter für die Zeitmessung Char vs. String array.copy
Zeit für n = 1000000: 664 ms
Zeit für n = 1000000: 639 ms
Differenz: 25 ms

und hier noch den TestCode

Spoiler anzeigen

VB.NET-Quellcode

Option Strict On
Option Explicit On
Module Module1
Public Function shiftLeft(ByVal b As String, ByVal n As Integer, Optional ByVal _rot As Boolean = True) As String
Dim dst() As Char = (New String("0"c, b.Length)).ToCharArray
If _rot Then
Dim nn As Integer = n Mod b.Length
b.CopyTo(nn, dst, 0, b.Length - nn)
b.CopyTo(0, dst, b.Length - nn, nn)
ElseIf n < b.Length Then
b.CopyTo(n, dst, 0, b.Length - n)
End If
Return dst
End Function
Public Function shiftRight(ByVal b As String, ByVal n As Integer, Optional ByVal _rot As Boolean = True) As String
Dim dst() As Char = (New String("0"c, b.Length)).ToCharArray
If _rot Then
Dim nn As Integer = n Mod b.Length
b.CopyTo(0, dst, nn, b.Length - nn)
b.CopyTo(b.Length - nn, dst, 0, nn)
ElseIf n < b.Length Then
b.CopyTo(0, dst, n, b.Length - n)
End If
Return dst
End Function
Public Function shiftLeft(ByVal b As Char(), ByVal n As Integer, Optional ByVal _rot As Boolean = True) As Char()
Dim dst() As Char = (New String("0"c, b.Length)).ToCharArray
If _rot Then
Dim nn As Integer = n Mod b.Length
Array.Copy(b, nn, dst, 0, b.Length - nn)
Array.Copy(b, 0, dst, b.Length - nn, nn)
ElseIf n < b.Length Then
Array.Copy(b, n, dst, 0, b.Length - n)
End If
Return dst
End Function
Public Function shiftRight(ByVal b As Char(), ByVal n As Integer, Optional ByVal _rot As Boolean = True) As Char()
Dim dst() As Char = (New String("0"c, b.Length)).ToCharArray
If _rot Then
Dim nn As Integer = n Mod b.Length
Array.Copy(b, 0, dst, nn, b.Length - nn)
Array.Copy(b, b.Length - nn, dst, 0, nn)
ElseIf n < b.Length Then
Array.Copy(b, 0, dst, n, b.Length - n)
End If
Return dst
End Function
Public Function shiftLeft(ByVal b As Byte(), ByVal n As Integer, Optional ByVal _rot As Boolean = True) As Byte()
Dim dst(b.Length - 1) As Byte
If _rot Then
Dim nn As Integer = n Mod b.Length
Buffer.BlockCopy(b, nn, dst, 0, b.Length - nn)
Buffer.BlockCopy(b, 0, dst, b.Length - nn, nn)
ElseIf n < b.Length Then
Buffer.BlockCopy(b, n, dst, 0, b.Length - n)
End If
Return dst
End Function
Public Function shiftRight(ByVal b As Byte(), ByVal n As Integer, Optional ByVal _rot As Boolean = True) As Byte()
Dim dst(b.Length - 1) As Byte
If _rot Then
Dim nn As Integer = n Mod b.Length
Buffer.BlockCopy(b, 0, dst, nn, b.Length - nn)
Buffer.BlockCopy(b, b.Length - nn, dst, 0, nn)
ElseIf n < b.Length Then
Buffer.BlockCopy(b, 0, dst, n, b.Length - n)
End If
Return dst
End Function
Public Function shiftL(ByVal b As Byte(), ByVal n As Integer, Optional ByVal _rot As Boolean = True) As Byte()
Dim dst(b.Length - 1) As Byte
If _rot Then
Dim nn As Integer = n Mod b.Length
Array.Copy(b, nn, dst, 0, b.Length - nn)
Array.Copy(b, 0, dst, b.Length - nn, nn)
ElseIf n < b.Length Then
Array.Copy(b, n, dst, 0, b.Length - n)
End If
Return dst
End Function
Public Function shiftR(ByVal b As Byte(), ByVal n As Integer, Optional ByVal _rot As Boolean = True) As Byte()
Dim dst(b.Length - 1) As Byte
If _rot Then
Dim nn As Integer = n Mod b.Length
Array.Copy(b, 0, dst, nn, b.Length - nn)
Array.Copy(b, b.Length - nn, dst, 0, nn)
ElseIf n < b.Length Then
Array.Copy(b, 0, dst, n, b.Length - n)
End If
Return dst
End Function
Public Function shiftR2(ByVal b As Byte(), ByVal n As Integer, Optional ByVal _rot As Boolean = True) As Byte()
Dim dst(b.Length - 1) As Byte
If _rot Then
Dim list = b.ToList()
Dim nn As Integer = n Mod b.Length
Return list.Skip(b.Length - nn).Concat(list.Take(b.Length - nn)).ToArray()
ElseIf n < b.Length Then
Buffer.BlockCopy(b, 0, dst, n, b.Length - n)'Gib's da ev. andere Möglichkeit über Enumerable
End If
Return Nothing
End Function
Public Function shiftL2(ByVal b As Byte(), ByVal n As Integer, Optional ByVal _rot As Boolean = True) As Byte()
Dim dst(b.Length - 1) As Byte
If _rot Then
Dim list = b.ToList()
Dim nn As Integer = n Mod b.Length
Return list.Skip(nn).Concat(list.Take(nn)).ToArray()
ElseIf n < b.Length Then
Buffer.BlockCopy(b, n, dst, 0, b.Length - n)'Gib's da ev. andere Möglichkeit über Enumerable
End If
Return dst
End Function
Sub Main()
Dim cnt As Integer = 5
'Dim b = New Byte() {1, 2, 3, 4, 5, 6, 7, 8}
Dim b(62 - 1) As Byte
For i As Byte = 0 To 62 - 1 : b(i) = i : Next
Console.WriteLine("Enter für die Zeitmessung Byte - blockCopy vs. array.copy")
Console.ReadKey()
Dim nn As Integer = 1000000
Dim bResR() As Byte, bResL() As Byte
Dim StartZeit As Date = System.DateTime.Now
For i As Integer = 0 To nn
bResR = shiftRight(b, cnt)
bResL = shiftLeft(bResR, cnt)
Next
Dim EndZeit As Integer = CInt(System.DateTime.Now.Subtract(StartZeit).TotalMilliseconds)
Console.WriteLine("Zeit für n = " & nn & ": " & EndZeit.ToString & " ms")
StartZeit = System.DateTime.Now
For i As Integer = 0 To nn
bResR = shiftR(b, cnt)
bResL = shiftL(bResR, cnt)
Next
Dim EndZeit2 As Integer = CInt(System.DateTime.Now.Subtract(StartZeit).TotalMilliseconds)
Console.WriteLine("Zeit für n = " & nn & ": " & EndZeit2.ToString & " ms")
Console.WriteLine("Differenz: " & EndZeit - EndZeit2 & " ms")
Console.WriteLine() : Console.WriteLine()
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Console.WriteLine("Enter für die Zeitmessung Byte - skip/take Enumerable")
Console.ReadKey()
StartZeit = System.DateTime.Now
For i As Integer = 0 To nn
bResR = shiftR2(b, cnt)
bResL = shiftL2(bResR, cnt)
Next
EndZeit2 = CInt(System.DateTime.Now.Subtract(StartZeit).TotalMilliseconds)
Console.WriteLine("Zeit für n = " & nn & ": " & EndZeit2.ToString & " ms")
Console.WriteLine("Differenz: " & EndZeit - EndZeit2 & " ms")
Console.WriteLine() : Console.WriteLine()
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Console.WriteLine("Enter für die Zeitmessung Char vs. String array.copy")
Console.ReadKey()
'Dim s As String = "abcdefgh"
Dim s As String = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
Dim c() As Char = s.ToCharArray
Dim cR() As Char = shiftRight(c, cnt)
Dim cL() As Char = shiftLeft(cR, cnt)
Dim cRO() As Char = shiftRight(c, cnt, False)
Dim cLO() As Char = shiftLeft(c, cnt, False)
StartZeit = System.DateTime.Now
For i As Integer = 0 To nn
cR = shiftRight(c, cnt)
cL = shiftLeft(cR, cnt)
Next
EndZeit = CInt(System.DateTime.Now.Subtract(StartZeit).TotalMilliseconds)
Console.WriteLine("Zeit für n = " & nn & ": " & EndZeit.ToString & " ms")
Dim sR As String = shiftRight(s, cnt)
Dim sL As String = shiftLeft(sR, cnt)
Dim sRO As String = shiftRight(s, cnt, False)
Dim sLO As String = shiftLeft(s, cnt, False)
StartZeit = System.DateTime.Now
For i As Integer = 0 To nn
sR = shiftRight(s, cnt)
sL = shiftLeft(sR, cnt)
Next
EndZeit2 = CInt(System.DateTime.Now.Subtract(StartZeit).TotalMilliseconds)
Console.WriteLine("Zeit für n = " & nn & ": " & EndZeit2.ToString & " ms")
Console.WriteLine("Differenz: " & EndZeit - EndZeit2 & " ms")
Console.WriteLine() : Console.WriteLine()
Console.ReadKey()
End Sub
End Module

Freundliche Grüsse

exc-jdbi

wolfi_bayern · 23. August 2016, 07:44

Moin!

ich hätts so gemacht:

VB.NET-Quellcode

Public Function shiftLeft(array As Byte()) As Byte()
Dim arraylist As New List(Of Byte)(array.ToList)
Dim temp As Byte = arraylist.First
arraylist.RemoveAt(0)
arraylist.Add(temp)
Return arraylist.ToArray
End Function
Public Function shiftright(array As Byte()) As Byte()
Dim arraylist As New List(Of Byte)(array.ToList)
Dim temp As Byte = arraylist.Last
arraylist.RemoveAt(arraylist.Count - 1)
arraylist.Insert(0, temp)
Return arraylist.ToArray
End Function

ROL ROR

ROL ROR

VB.NET-Quellcode

Quellcode

VB.NET-Quellcode

VB.NET-Quellcode

Benutzer online 1

5 Benutzer haben hier geschrieben