Entwickler-Ecke
Algorithmen, Optimierung und Assembler - 8x8 Matrix um jeweils 90 Grad drehen
rotalosi - Mi 16.12.15 15:43
Titel: 8x8 Matrix um jeweils 90 Grad drehen
Hallo,
ich habe eine Matrix mit 8 Spalten und 8 Zeilen. Diese Matrix ist in einem Array aus 8 Bytes gespeichert. Jedes Byte repräsentiert eine Zeile und jedes Bit darin eine Spalte. Nun zu meinem Problem:
Ich möchte die Matrix um jeweils 90 Grad in die ein oder andere Richtung drehen. Hat jemand eine Idee wie ich das ganze Umsetzen kann? Wichtig ist, das der Code möglichst schnell ausgeführt wird.
Wäre schön wenn jemand eine Idee hätte.
Gruß Frank
Moderiert von 
Martok: Topic aus Delphi Language (Object-Pascal) / CLX verschoben am Mi 16.12.2015 um 15:17
Fiete - Mi 16.12.15 18:22
Moin rotalosi,
habe in meinem Archiv etwas gefunden, das Dir helfen könnte,
Stichwort Koordinatentransformation, Mathematik kann so schön sein!
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
| procedure TSchablonenCode.RechtsDrehen(var Neu:TFeld;Alt:TFeld;BG:Integer);
var X,Y:Integer;
begin
SetLength(Neu,BG+1,BG+1);
for X:=1 to BG do
for Y:=1 to BG do Neu[BG+1-Y,X]:=Alt[X,Y]
end;
procedure TSchablonenCode.LinksDrehen(var Neu:TFeld;Alt:TFeld;BG:Integer);
var X,Y:Integer;
begin
SetLength(Neu,BG+1,BG+1);
for X:=1 to BG do
for Y:=1 to BG do Neu[Y,BG+1-X]:=Alt[X,Y]
end;
Warum soll der Code möglichst schnell ausgeführt werden? |
Gib doch mal die Aufgabenstellung und Deine Lösungsansätze hier an, könnte ja von allgemeinem Interesse sein.
Gruß Fiete
C# - Mi 16.12.15 18:53
Nabend,
da mich das Problem interessiert habe ich mich gleich selbst mal dran gesetzt und einen kleinen Algorithmus geschrieben (kann leider kein Delphi, daher in C#), der sowohl im als auch gegen den Uhrzeigersinn drehen kann. Im Prinzip funktioniert er für alle ganzzahligen Datentypen (sprich byte, short, int, long), die Matrix muss nur quadratisch sein. Den Code habe ich noch ein wenig kommentiert, ich hoffe dass es dir hilft.
C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
| static void Main(string[] args)
{
byte[] matrix = {14, 125, 127, 204, 232, 136, 56, 200};
Console.WriteLine("Initial Matrix:");
PrintMatrix(matrix);
Console.WriteLine("\nRotate 90° clockwise:");
matrix = RotateMatrix(matrix);
PrintMatrix(matrix);
Console.WriteLine("\nRotate 90° clockwise:");
matrix = RotateMatrix(matrix);
PrintMatrix(matrix);
Console.WriteLine("\nRotate 90° counter-clockwise:");
matrix = RotateMatrix(matrix, false);
PrintMatrix(matrix);
Console.WriteLine("\nRotate 90° counter-clockwise:");
matrix = RotateMatrix(matrix, false);
PrintMatrix(matrix);
Console.ReadLine();
}
static void PrintMatrix(byte[] matrix)
{
foreach (byte b in matrix)
Console.WriteLine(Convert.ToString(b, 2).PadLeft(8, '0').Aggregate("", (t, s) => t + s + " "));
}
static byte[] RotateMatrix(byte[] matrix, bool clockwise = true)
{
int columnSize = sizeof (byte) * 8;
byte[] buffer = new byte[matrix.Length];
for (int i = 0; i < matrix.Length; i++)
{
for (int j = 0; j < columnSize; j++)
{
if (((1 << j) & matrix[i]) != 0)
{
if (clockwise) buffer[columnSize - j - 1] |= (byte) (1 << i);
else buffer[j] |= (byte)(1 << (columnSize - i - 1));
}
}
}
return buffer;
} |
Die Ausgabe davon ist:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
| Initial Matrix:
0 0 0 0 1 1 1 0
0 1 1 1 1 1 0 1
0 1 1 1 1 1 1 1
1 1 0 0 1 1 0 0
1 1 1 0 1 0 0 0
1 0 0 0 1 0 0 0
0 0 1 1 1 0 0 0
1 1 0 0 1 0 0 0
Rotate 90° clockwise:
1 0 1 1 1 0 0 0
1 0 0 1 1 1 1 0
0 1 0 1 0 1 1 0
0 1 0 0 0 1 1 0
1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1
0 0 0 0 0 1 0 1
0 0 0 0 0 1 1 0
Rotate 90° clockwise:
0 0 0 1 0 0 1 1
0 0 0 1 1 1 0 0
0 0 0 1 0 0 0 1
0 0 0 1 0 1 1 1
0 0 1 1 0 0 1 1
1 1 1 1 1 1 1 0
1 0 1 1 1 1 1 0
0 1 1 1 0 0 0 0
Rotate 90° counter-clockwise:
1 0 1 1 1 0 0 0
1 0 0 1 1 1 1 0
0 1 0 1 0 1 1 0
0 1 0 0 0 1 1 0
1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1
0 0 0 0 0 1 0 1
0 0 0 0 0 1 1 0
Rotate 90° counter-clockwise:
0 0 0 0 1 1 1 0
0 1 1 1 1 1 0 1
0 1 1 1 1 1 1 1
1 1 0 0 1 1 0 0
1 1 1 0 1 0 0 0
1 0 0 0 1 0 0 0
0 0 1 1 1 0 0 0
1 1 0 0 1 0 0 0 |
Hier mal noch ein Bild wie der Algorithmus funktioniert, wenn er im Uhrzeigersinn dreht. Reihenfolge: rot, blau, grün, pink
Ralf Jansen - Mi 16.12.15 20:21
Mal quer gedacht. Ist es überhaupt notwendig die Matrix tatsächlich im Speicher zu rotieren (Nebenbei soll das Ergebnis im gleichen Array liegen oder in einem neuen rotierten)? Man könnte doch einfach den Zugriff auf das Array umrechnen. Ist ja letztlich nicht viel mehr als Spalten, Zeilen tauschen bei der Zelladressierung.
Nersgatt - Mi 16.12.15 22:24
Das würde ich davon abhängig machen, wie oft auf das gedrehte Array zugegriffen werden muss. Wenn es eine einmalige Sache ist, könnte man das beim Zugriff umrechnen.
Bei mehrfachem Zugriff ist es sicher effektiver, einmal das Array zu drehen und damit ist dann beim Zugriff keine Umrechnung mehr nötig.
jfheins - Mi 16.12.15 23:35
rotalosi hat folgendes geschrieben  : |
| Wichtig ist, das der Code möglichst schnell ausgeführt wird. |
Es wäre etwas praktischer, wenn du da eine konkrete Vorstellung hättest. in Stackoverflow gibt eine
ähnliche Frage [
http://stackoverflow.com/q/6930667] der Code muss aber evtl. angepast werden.
Falls es sehr schnell sein muss, würde ich C oder Assembler empfehlen; die SSE-Anweisung movemask sollte deinem Problem sehr gelegen kommen:
https://mischasan.wordpress.com/2011/07/24/what-is-sse-good-for-transposing-a-bit-matrix/
Aber vielleicht lässt sich da auch was mit shifts und Multiplikationen zusammenbasteln ... ich schaue mal
Sooo ... etwas müde, aber diese Version ist 3-4 Mal so schnell wie die aus Beitrag 3 auf meiner 64bit CPU. Zugegeben, auch etwas spezialisierter und kryptischer. Die Schleife könnte man sicher noch ausschreiben. (Ich hoffe jedoch, der compiler macht das bereits)
C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
| static byte[] RotateMatrix2(byte[] matrix)
{
unchecked
{
ulong input1 = BitConverter.ToUInt32(matrix, 0); ulong input2 = BitConverter.ToUInt32(matrix, 4);
for (int bit = 0; bit < 8; bit++)
{
uint mask = 0x80808080u >> bit;
uint factor = (1u << (0 + bit)) | (1u << (7 + bit)) | (1u << (14 + bit)) | (1u << (21 + bit));
uint tmp1 = (uint)(((input1 & mask) * factor) >> 28) & 0xFF;
uint tmp2 = (uint)(((input2 & mask) * factor) >> 24) & 0xFF;
matrix[bit] = (byte)(tmp1 | tmp2);
}
return matrix;
}
} |
Idee ist von hier:
http://wm.ite.pl/articles/scalar-sse-movmask.html
rotalosi - Do 17.12.15 11:03
Hallo,
vielen Dank für eure Hilfe. Das bringt mich schon mal deutlich weiter. Selbst die erste c# Variante ist für meine Anwendung schnell genug. Ich denke bei Geschwindigkeit immer in den Dimensionen eines µC. In diesem Fall an einem Mega324A mit 8 Mhz Takt.
Zum Hintergrund falls es jemanden interessiert. Ich habe für unseren Verein vor einiger Zeit eine kleine Matrixanzeige gebaut. Die besteht aus 3 x 5 (8x8) Matrixelementen. Alle Module sind per SPI miteinander verbunden. Bisher wurde nur Text angezeigt. Das hat der kleine Atmel problemlos geschafft. Nun möchte ich aber auch animierte Grafiken anzeigen. Das schafft der kleine nur wenn er die Grafiken vorausberechnet serviert bekommt, sonnst flimmert es.
Da ich mich hauptsächlich mit Mikrocontrollern beschäftige, vergesse ich manchmal um wie viel schneller ein PC rechnet. Selbst die langsamste Variante auf jeden Fall schneller als ich die Daten an dem Atmel überragen kann. Vielen Dank für eure Hilfe. Ich melde mich nochmal ob es geklappt hat.
Gruß Frank
OlafSt - Do 17.12.15 12:38
Außerdem kann man sicher einfach den Quarz gegen einen 16MHz-Typen austauschen und so die Rechenleistung des kleinen Atmel um 100% steigern ;)
Nersgatt - Do 17.12.15 12:40
Der AVR wird ja noch andere Aufgaben haben, als Arrays zu rotieren. Wenn die Möglichkeit da ist, würde ich dem AVR die Daten soweit wie möglich auf dem PC vorkauen, um ihn nicht mehr arbeiten zu lassen als irgend nötig.
Horst_H - Do 17.12.15 13:14
Hallo,
wenn der AVR das in etwa 25 µs ~ 200 Takten rotiert, ist doch die Frage, ob das Versenden von 8 Byte vom PC nicht etwas länger dauert.
Bei 115200 Bd etwa 700 µs.OK, könnte Interupt gesteuert sein., aber das dauert wohl auch um >10 Takte pro Byte.
Man kann ja auch vorberechnete Muster im Flash oder Eeprom haben oder eine Externe Eeprom per SPI nutzen.
Meist quält man die AVR mit Däumchendrehen...
Gruß Horst
GuaAck - Do 17.12.15 23:35
Hallo alle,
wenn man von einer externen Bearbeitung absieht, dann laufen alle Algorithmen auf eine geschachtelte Schleife 0..7 hinaus, also 64 Schritte. Da gibt es drei Ansatzpunkte:
a) Jeden Schritt optimieren: "Bit lesen, Bit in einem anderen Byte an bestimmter Stelle setzen". Da könnte auch die Einführung eines Zwischenschrittes helfen. Beispiel: Man legt das Ergebnis zunächt in einem Array 1..256 ab, nutzt aber nur nur 1,2,4,8,..., 256, dann wäre die Shiftmaske zur Abfrage des Bits im Byte gleich dem Index im Ausgabefeld. Zum Abschluss muss man noch 7 Bytes umkopieren. Könnte Vorteile bringen.
b) Schleifenverwaltung minimieren, ideal den Code 64 x hintereinander im Quelltext, man spart die if-Abfragen und das Inkrementieren des Zählers und die Feldadressen müssen auch nicht zur Laufzeit berechnet werden; schon für die innere Schleife hilft das, weil der eigentliche Schritt ja kurz ist, ein paar ORs, ANDs und SHIFTs o.ä.
c) Statistik: Wenn das Array typisch nur wenige "1" enthält, dann muss man nicht jedes der 64 Bits setzen, sondern man initialisiert das Ausgangsfeld mit 0 und muss dann nur die seltene "1" setzen. (umgekehrt bei wenigen "0" entsprechend.)
Also:
a) Das muss man probieren, es hängt sehr vom Prozessor und vom Compiler ab, was geht. Und evtl. auch vom RAM oder anderen Resourcen.
b) Der Vorteil ist unstrittig. Nachteil: Man braucht Programmspeicher und es ist extrem änderungsunfreundlich. (Ich würde unbedingt ein kleines Programm (Delphi, C o.ä.) machen, das mir die 64 Dinger automatisch als Textdatei zum Einfügen in den Quellcode erzeugt.)
c) Der Vorteil ist unstrittig, hängt von der Anwendung ab.
Nun bin ich gespannt auf die schnellste Version,
Gruß´GuaAck
rotalosi - Di 22.12.15 11:41
Hallo,
vielen Dank an alle. Besonders C#. Ich habe das Ganze nun in Delphi umgesetzt und es funktioniert nun einwandfrei.
Ich gehe hier nochmal kurz auf andere Antworten ein. Der Atmel läuft nicht mit einem externen Quarz sondern mit seinem internen RC Generator. Einfach den Quarz tauschen funktioniert also nicht. (Es gibt aber auch noch andere Gründe warum man nicht einfach die Frequenz ändern kann)
Der Atmel in meiner Anwendung ist quasi bis zum Anschlag ausgelastet. Die Anzeige ist nicht statisch, sondern in Zonen aufgeteilt. Während eine nur den Punktestand anzeigt, werden in den anderen Laufschriften mit Informationen angezeigt. Was angezeigt werden soll, holt sich der Atmel an seinem Port A ab (Interrupt). Dort werden die Daten von der PC-Anwendung über ein USB Interface bereitgestellt. Es ist natürlich kein Problem die Matrix im Atmel zu drehen oder gar im EEProm zu speichern. Aber es sollen ja Animationen übertragen werden, die vom Anwender des Programms beliebig erzeugt werden können.
Vielen Dank nochmal und allen ein schönes Weihnachtsfest und einen guten Rutsch.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!