Hallo zusammen, ich habe eine Frage bzgl. Algorithmus zum Zerschneiden vom Array. Ich habe ein Byte-Array und soll aus dem Array bestimmte Informationen rauslesen. Die Informationen sind in dem Byte Array grupiert und ich kenne das StartBit und die Länge in Bits. Die extrahierte Bytes/Bits soll ich in ein anderes Byte-Array hinkopieren (dsa für die extrahierte Länge passt). Was ist der beste (schnell und optimiert) Algorithmus Eure Meinung nach, um diese Aufgabe zu erledigen? Danke im Voraus für die Antworten
lepper03 schrieb: > Was ist der beste (schnell und optimiert) Algorithmus Eure Meinung nach, > um diese Aufgabe zu erledigen? Was hast du denn bist jetzt für einen 'schlechten' Algorithmus? Da kann man bestimmt darauf aufbauen. (Des besseren Verständnisses wegen.)
eben bis jetzt fällt mir nichts vernünftiges ein ;( habe so gedacht: startbyte = startbit / 8 startBit = startbit % 8 endbyte = (startbit + length) / 8 endBit = (startbit + length) % 8 und dann die grenzeden Byte(s) (start/end) bearbeiten/extrahieren und die dazwischen liegende einfach kopieren. Eigentlich, das ist Randproblem. Die Rand-Byte(s) müsste ich mit Shift-Operationen rausholen.....hmmmm....Ws meint Ihr?
Also ohne weitere Informationen wirst du wohl jedes Bit anfassen müssen und schauen ob es ein Startbit ist. Bei dieser Ausgangslage vom ersten bis zum (letzten-Wortlänge). Schneller geht es wenn du dein System kennst. - Kommt das Startbit nur am Anfang eines Bytes (Nur noch jedes 8. Bit anfassen) [Wobei sich mir da beim drüber nachdenken gerade die Frage aufdrängt wie in einem digitalen System ein StartBIT aussieht] - Ist es wahrscheinlicher dass es später kommt als direkt am Anfang (Startwert der Suche) - Gibt es andere Muster? Kommt eventuell immer etwas identisches davor? ... grüße
mehr Informationen würden mir nicht weiterhelfen. StartBit und Länge sind schon ausreichend. Hier ein Beispiel: Byte myArray[256] Gruppe1: StartBit: 0, Länge 20 Bits Gruppe2: StartBit: 20, Länge 50 Bits Gruppe3: StartBit: 70, Länge: 100 Bits .... etc....
lepper03 schrieb: > Die extrahierte Bytes/Bits soll ich in ein anderes Byte-Array hinkopieren > (dsa für die extrahierte Länge passt). Kann es ja ohnehin nicht, wenn die Gesamtlänge an "Nutzbits" nicht durch 8 teilbar ist. D.h. wer auch immer die Daten weiterverarbeitet, wird auch wieder darauf schauen müssen und braucht die Zusatzinformation, wieviele Bits denn genutzt werden sollen. > Was ist der beste (schnell und optimiert) Algorithmus Eure Meinung nach, > um diese Aufgabe zu erledigen? Ich wüsste nicht, was man da viel optimieren kann. Zumal es vorrangig auf die Korrektheit der Ergebnisse ankommt. Wenn es gerade mal um 256 Bytes geht, die insgesamt zu verarbeiten sind, dann dürfte damit so ziemlich jeder Mikrocontroller fix fertig sein. Es sei denn die Aufgabe muss Millionen Male pro Sekunde durchgeführt werden.
:
Bearbeitet durch User
@OP: Ohne semantische Zusatzinformationen kann man da konkret kaum was zu sagen, wie ein schneller Algorithmus aussehen kann / soll. Mark Brandis direkt über mir hat schon darauf hingewiesen, dass selbst ein verschlafener ATtiny 25 über ein paar paarhundert Bits nur schmunzeln würde. Wenn Du hingegen einen riesigen Datenberg durchzuschaufeln hast, geht es, wie auch andere schon geschrieben haben, um Muster, Bedeutung -- also Semantik. Wenn die Informationsblöcke immer gleich lang sind und nicht 2^(8n) lang sind, also keine n Bytes, sondern irgendwas krummes, von mir aus 777 Bits, könnte es allgemein je nach verfügbarem RAM sogar angebracht sein, in Assembler oder Low-Level-C über den Speicher zu rumpeln, ein Byte/Word/DWord etc. auszulesen, den Inhalt zu kopieren, mit Shift-Operationen das Paket rauszuholen (mitlaufender Zähler) und aus jedem Bit ein neues Byte(!) zu machen. Warum? Damit Du danach in einer "vernünftigen" Sprache Deiner Wahl (Java(script), C#, Python...) den Verarbeitungsprozess pro Datenblock (die angenommenen 777 Bits) auf vielen, vielen Prozessorkernen parallel ablaufen lassen kannst. Hier reden wir dann aber schon über echt große Datenmengen, die schnell abgearbeitet werden müssen, also von irgendeiner Hardware vom Raspi 3 an aufwärts bis zu einem ausgewachsenen, massiv-parallelen Cluster. Und sowas ist sogar in C++ schon eine ausgesprochen hässliche Angelegenheit, geschweige denn in C oder ASM. Als alter "Microsoftie" würde ich das ganze in der DotNet-Umgebung laufen lassen (Mono), weil man dort ein echtes Schlaraffenland in Sachen Thread-Verwaltung findet, aber ähnliche Bibliotheken gibt es bestimmt auch für Java und andere neuere Sprachen.
Ok, die "Nutzbits" müssen nicht unbedingt durch 8 teilbar ist. Die unbenützte Bits wird man reseten. Die Bytes kommen via CAN-Bus als Botschaften. Die Botschaften beinhalten Signale, welche zu Signalgruppen zusmmengefasst werden können: https://www.autosar.org/fileadmin/files/releases/4-2/software-architecture/communication-stack/standard/AUTOSAR_SWS_COM.pdf
Je nachdem wie schlecht dein Compiler ist kann man bei den Divisionen und Modulo Operationen schon optimieren --> Shift Operator und logisches AND (&). Das bring aber nur etwas, wenn diese Operationen vergleichsweise oft aufgerufen werden, z.B. die Länge der zu extrahierenden Daten kurz ist. Division und Modulo auf einem Microcontroller ohne Divisions-Einheit brauchen da schon mal xx Befehle, um das umzusetzen... einen schlechten Compiler vorausgesetzt. Außerdem könnte man auch Sonderfälle (z.B. Startbit ist durch 8 Teilbar) gesondert optimieren. Wie immer hängt aber die optimale Umsetzung von der Zielplattform ab... i7, ARM Cortex, Attiny?? Linux/Windows/C/C++/C#/Java ... Und die wichtigste Frage ist, ob dieser Algorithmus überhaupt optimiert werden muss, oder ob deine Performance eh ganz wo anders verloren geht ;)
Und du bist du sicher, dass dieser Algorithmus optimiert werden muss? Bei CAN-Baudraten bis 1Mbps und max. 8 Bytes pro Nachricht wird deinem Controller eh langweilig ;)
na ja, wir haben jetzt schon 70% CPU auslastung, dort müssen kritische Funktionen berechnet werden. Meine Funktionen sind vielleicht 1% von dem ganzen und das Alg. ein sehr kleines Teil von der Funktion, was sagen wir 200 mal alle 5 msec aufgerufen wird ;)
ich habe nicht nur CAN aber auch Flexray, CANFD und Ethernet ;)
lepper03 schrieb: > die dazwischen liegende einfach kopieren. Eigentlich, das ist Und was machst Du, wenn Du ein Byte, bestehend aus 8 Bit von Quellposition 0 an Zielposition 1 kopieren sollst? Dann kannst Du das Byte nicht einfach kopieren. Lauf durch die Quellbits und kopiere sie einzeln. Vielleicht reicht Dir die Geschwindigkeit schon. Geschwindigkeit gewinnen durch das Kopieren von ganzen Bytes kannst Du nur dann, wenn Quellposition und Zielposition bei der Division durch 8 mit Rest im Rest übereinstimmen. Anstelle über Optimierungen zu sinnen, solltest Du einfach den naiven Kopieralorithmus, bzw. die primitive Bitkopierschleife realisieren. Die Experten hier haben dann bestimmt noch Ideen, wie sich der Kopiervorgang des einzelnen Bits beschleunigen lässt.
:
Bearbeitet durch User
Zielposition ist eigentlich einfach, Quellposition 0 an Zielposition 0 usw. d.h. Byte myArray[256] Gruppe1: StartBit: 0, Länge 20 Bits Gruppe2: StartBit: 20, Länge 50 Bits Gruppe3: StartBit: 70, Länge: 100 Bits Gruppe1 wird einfach an ZielArray1 geschrieben: ZielArray1[0] = StartBit: 0, Länge 8 Bits ZielArray1[1] = StartBit: 8, Länge 8 Bits ZielArray1[2] = StartBit: 16, Länge 4 Bits .... ok, danke Euch, ich werde mir es jetzt am WE überlegen und mein Ergebnis hier posten.
Achtung: An welcher Position im Ziel landet denn Startbit 20? Bei Bitposition Null oder anderswo?
@Peter M: Startbit 20 gehört schon zur neuen Gruppe d.h. neues Array => an der Stelle 0.
lepper03 schrieb: > ok, danke Euch, ich werde mir es jetzt am WE überlegen und mein Ergebnis > hier posten. Die anderen Verfahren mögen zwar in C Programm schöner und kürzer aussehen aber Bitschifterei ist immer die schnellste Art.
Mir fällt nichts vernünftiges ein, alles scheint hoch kompliziert zu sein :( jemand hat über BitCopyLoop geschrieben, aber wird immer kompliziert da man ständig berechnen muss wann neues Byte/Bit im QuelleArray endet und wann das neue Byte/Bit im ZielArray anfängt bzw. wenn im ZielArray Platz vorhanden ist muss genutzt werden. Was ich noch machen kann, anstatt es dynamisch zu berechnen, einfach den Code zu generieren und im Vorfeld d.h. im Generator schon einige Berechnugen vorzubereiten... Am Anfang habe ich mir gedacht, dass es nicht so schwierig sein kann...
lepper03 schrieb: > Mir fällt nichts vernünftiges ein, alles scheint hoch kompliziert zu > sein :( Was ist hoch kompliziert? Das was Du hier beschrieben hast: > startbyte = startbit / 8 > startBit = startbit % 8 > endbyte = (startbit + length) / 8 > endBit = (startbit + length) % 8 klingt doch nach einem Ansatz der funktionieren kann, wenn man ihn richtig ausprogrammiert. Ansonsten gilt wie immer: Teile das zu lösende Problem in kleinere Teilprobleme auf.
lepper03 schrieb: > und dann die grenzeden Byte(s) (start/end) bearbeiten/extrahieren und > die dazwischen liegende einfach kopieren. Eigentlich, das ist > Randproblem. Das geht nur in Spezialfällen und klappt im Allgemeinen nicht. Quelle: Startbit Nr. 4 (die 1!) Länge: 16 0000 1011 0011 1110 1111 Dann muss das Ziel so aussehen: 1011 0011 1110 1111 Wie Du siehst, kannst Du das das zweite Byte nicht einfach kopieren. => Probiere den naiven Algorithmus: Bit für Bit kopieren, also "Bit einlesen, Bit schreiben"
lepper03 schrieb: > Es geht um ANSI C und TC1797(Infineon) Der hat doch genug RAM, nimm einfach uint8_t oder bool pro bit und nutze normale Arrays.
Danke Euch allen, Ich werde den Code (zumindes diesen Anteil) doch spezifisch generieren.
Fa bin ich ganz bei dir. Wir sind nicht mehr in den Zeiten von Mycro-Supra-Nenno-Prozessoren, die nur 64 Bytes zur Verfügung haben. Nicht umsonst übersetzt die GCC in der Regel bool in int.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.