Hallo Gemeinde, Nachdem "die Anwendung" auf einem µController laufen soll, frage ich mal hier: Für ein Hobbyprojekt brauche ich aus bestimmten Gründen einen Algorithmus, mit dem ich 16 zufällige Zahlen, die Werte von 0 bis 15 annehmen können, sortieren kann. Die Anforderung ist aber, daß es schnell gehen muß, da dieser Vorgang ca. 1000 mal pro Sekunde abläuft. Dabei habe ich aber keine Lust nur dafür die gesamte Rechenkapazität zu opfern. Zwei Methoden habe ich schon: Die Langsame: Bubblesort, der 120 Vergleichsoperationen (n*(n-1))/2 benötigen würde. Der Schnelle: Alle 16 Nibble zu einem 64-Bit-Vektor packen, diesen als Index für eine Tabelle nehmen, die direkt das Ergebnis liefert. Offensichtlicher Nachteil: Die Tabelle hat 2^64 Einträge :-) Gibt's da einen Kompromiss? Grüße Christian P.S. Die Plattform soll ein MSP430 werden, d.h. ein paar Byte RAM und ROM stehen für eine Beschleunigung schon zur Verfügung...
Stand letztens in der CT. http://www.sortieralgorithmen.de/ hier werden einige Sortierverfahren vorgestellt. Zum Teil sogar mit Quellcodebeispielen Werner
Hi such dir einen (bevorzugt mit O(n * log(n)) und nicht O(n!) :-) aus: http://de.wikipedia.org/wiki/Sortieralgorithmus Matthias
ich würd nen quicksort nehmen. lässt sich recht schnell auf nem µC realisieren.
bei 16 Zahlen im Bereich 0 bis 15 kannst du aber schneller als O(n *
ln(n)) sortieren. Du benötigst nur ein Array[] mit 16 Einträgen und
zählst das Vorkommen jeder der 16 möglichen Zahlen.
uint8_t Data[16];
void Insert(uint8_t Value) {
Data[Value]++;
}
void PrintSorted(void) {
for (uint8_t i = 0; i < 15; i++) {
for (uint8_t j = Data[i]; j > 0; j--) {
printf( i );
}
}
}
Einfacher gehts schon nicht mehr :-)
Gruß Hagen
Mal ein bisschen konkreter gesprochen, möchte ich einen Timer laufen lassen, der 16 Ereignisse auslösen sollen. Nach dem dieser einfach hochzählt. Muß das passende Ereignis zum passenden Zählerstand ausgeführt werden. Ich könnte natürlich auch immer die Liste aller 16 Ereignisse durchsuchen, aber das dauert mir zu lange. @Hagen: Deine Methode inspiriert mich in der Weise, daß ich 16 Arrays aufmache, in die ich die zugehörigen Werte "reinfülle". Also Array 0 mit den 0-Werten, Array 1 mit den 1-Werten. Ja, so könnte das rasch funktionieren. Danke schon mal für die vielen Antworten. Grüße Christian
Warum willst du 16 array nehmen ? Das kann ich nicht nachvollziehen. In dem Array für die 0 würden dann alles immer nur Nullen stehen, im Array für die 1 immer nur einsen usw. usw. Der einzigste Unterschied zwischen all diesen Arrays wäre die Anzahl der Nullen, Einsen, Zweien usw. Also kannst du doch gleich einfach wie in meinem Beispiel die Anzahl der eingefügten Nullen, Einsen, Zweien usw. zählen. So benötigst du gerade mal 16 Bytes um alle Zahlen zwischen 0 bis 15 einsortieren == zählen zu können. Sind die Zähler im Array zb. vom Typ Byte so kannst du in dieses 16 Bytes array maximal sogar 255 deiner Zahlen einsortieren. Bei der Auswertung dieses Arrays[] hast du wiederum einen Vorteil. Es ist nämlich einfacher die Variable i und j in Registern zu halten. i gibt die aktuelle Zahl an und j die Anzahl die beim Einsortieren aufgetretenen Zahlen i. Diese Auswertung ist also sehr gut auf MCU's zu optimieren. Beispiel: 1,5,10,5,2,2,3,7,5 werden mit Insert eingefügt/gezählt. Data[1] = 1 Data[2] = 2 Data[3] = 1 Data[5] = 3 Data[7] = 1 Data[10] = 1 alle anderen Data[] Elemente sind auf 0. Gehst du nun Data[] von 0 nach 15 durch so hast du die Anzahl der aufgetretenen Zahlen. Die Sortierung entsteht einfach nur dadurch wie du Data[] iterierst. Willst du nun wie oben die tatsächlichen Zahlen ausgeben entsteht folgendes Bild: 1,2,2,3,5,5,5,7,10 Also alles bestens und absolut easy. Ich kann beim besten Willen nicht verstehen warum du nun ein zweidimensionales Array[0..15, 0..15] benutzen möchtest. Das würde quadratisch mehr Speicher benötigen, statt 16 Bytes eben 16 * 16 Bytes, und wäre genauso, wenn nicht noch aufwändiger auswertbar. Gruß Hagen
Willst du nun die äußere Schleife i beschleunigen so gibts auch dafür
eine Möglichkeit.
uint8_t Data[16];
uint8_t Min = 255;
uint8_t Max = 0;
void Insert(uint8_t Value) {
Data[Value]++;
if (Value < Min) {Min = Value;}
if (Value > Max) {Max = Value;}
}
void PrintSorted(void) {
for (uint8_t i = Min; i < Max; i++) {
for (uint8_t j = Data[i]; j > 0; j--) {
printf( i );
}
}
Min = 255;
Max = 0;
}
Das sollte mit wenig Aufwand besonders sparse Events beschleunigen,
also die Fällen wenn sehr häufig nacheinander immer nur wenige der
möglichen Zahlen zwischen 0 bis 15 auftreten.
Ich wüsste jetzt nicht wie man das ohne größeren Aufwand noch weiter
beschleunigen könnte. Es bliebe meiner Meinung nach nur noch eine
verlinkte Liste übrig, allerdings wäre der Aufwand diese Verlinkung,
bei 16 möglichen Werten, aufzubauen und zu verwalten viel größer als
der Aufwand der jetzt bei der Auswertung zb. wie im obigen Print()
entsteht.
Gruß Hagen
Hallo Hagen,
Mein Idee von vorhin führt wirklich ein bischen ins Leere...
Fakt ist, und das ist mir mittlerweile klar geworden, daß zum Ereignis
ja auch noch die zugehörige Aktion gehört. Das ist das Setzen eines
Portpins.
Wir nähern uns der Anwendung:
Ich habe 16 Ereignisse. Jedem Ereignis ist fest ein Portpin zugeordnet
(Also Ereignis 0 Pin 0 usw...), und ein Zeitpunkt, wann dieses gesetzt
werden soll. Der ist zufällig und besitzt Werte von 0..15.
Mittlerweile würde ich's so machen:
// In Events steht der Zeitpunkt eines Ereignisses.
// Der Index ist die Portnummer, wo was passieren soll.
int Events[16];
// Actions beinhaltet alle Bits eines Ports, die zum
// jeweiligen Zeitpunkt gesetzt werden. Der Index
// Gibt den Zeitpunkt an. D.h., der Timer erhöht mit jedem
// Durchlauf einen Zähler für den Index, nimmt die Maske,
// und setzt die entsprechenden Bits.
int Actions[16];
// Und hier werden die "Actions" berechnet:
memset(Actions,0,sizeof(Actions));
// Wir schicken ein Bit auf die Reise von rechts nach links
int Mask = 0x0001;
for (int PortBit=0; PortBit<16; PortBit++)
{
Action[Events[PortBit]] |= Mask;
Mask <<= 1;
}
Das ist Deinem ersten Vorschlag nicht unähnlich, nur daß das Ergebnis,
die Anzahl der "Treffer" pro Ereignis halt kein Zähler ist, sondern
gleich eine Bitmaske entsteht. Die Anzahl der gesetzten Bits
entsprechen Deinem Zähler.
Irgendwie schreit das mittlerweile nach dem MSP...
Grüße
Christian
Also, wenn Du primär nicht sortieren möchtest, sondern eine möglichst effiziente Multi-Timer-Lösung suchst, dann schau mal in: "Computer Networks" von Andrew S. Tanenbaum Dort wird das Thema bezüglich Timer in Netzwerkprotokollen angesprochen. Im Prinzip genau Dein Problemgebiet. Es gibt da einige sehr nette und effiziente Algorithmen die darin vorgestellt werden. (Wenn ich mich nicht irre... Ist aber erst ca. 24 Monate her, als ich das Buch in der Hand hielt. Müsste also noch stimmen.) Da gibt's dann natürlich auch ein Literaturverzeichnis mit weiteren Infos zu diesem Themengebiet.
Aha, alles klar, du benötigst eine 16 fach PWM mit einer
Dutycycle-Auflösung von 16 Schritten. Das hat ja primär nichts mit
Sortierungen zu tuen, da stimme ich Michael zu.
Deine jetzige Lösung ist schon optimal, wenn man das aus Sicht der
Ausführungsgeschwindigkeit betrachtet. In deinem Timer wird ein Zähle
hochgezählt und dieser kann nur von 0 bis 15 gehen und beginnt dann von
neuem. Zu jedem Zählerwert hast du in Action[] den nötigen Status des 16
Bit Ausgabe-ports gespeichert. D.h. deine TimerISR sähe so aus
SIGNAL_TIMER1() {
Port = Action[Index & 0x0F];
Index++;
}
Das ist sehr effizient. Du könntest jetzt noch das Array[] Events
wegrationalisieren da ich vermute das das aktivieren einer Action nicht
so zeitkritisch sein dürfte.
void ResetAction(void) {
memset(Actions,0,sizeof(Actions));
}
void AddAction(int PortPins, int Delay) {
for (; Delay < 16; Delay++) {
Action[Delay] |= PortPins;
}
}
PortPins enthält den hinzuzufügenden Status der zum Zaitpunkt Delay zu
aktivierenden Pins. Willst du zb. ab dem zeitpunkt 7 die Pins 2,5,10
setzen dann sähe dies so aus
AddAction( 1 << 2 | 1 << 5 | 1 << 10, 7 );
Gruß Hagen
Vorteil, du köntest auch eine SubAction() bauen die dann aus Action[] ab
einem Zeitpunkt wieder bestimmt Bits löschen kann, zb. so
void SubAction(int PortPins, int Delay) {
for (; Delay < 16; Delay++) {
Action &= ~PortPins;
}
}
damit könntest du dann die PWM's Phasenverschieben.
Gruß Hagen
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.