www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Schnell ein paar Zahlen sortieren


Autor: Christian Rötzer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Werner (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Stand letztens in der CT.
http://www.sortieralgorithmen.de/

hier werden einige Sortierverfahren vorgestellt. Zum Teil sogar mit
Quellcodebeispielen

Werner

Autor: Matthias (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi

such dir einen (bevorzugt mit O(n * log(n)) und nicht O(n!) :-) aus:
http://de.wikipedia.org/wiki/Sortieralgorithmus

Matthias

Autor: Dominik (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ich würd nen quicksort nehmen. lässt sich recht schnell auf nem µC
realisieren.

Autor: Hagen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Christian Rötzer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Hagen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Hagen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Christian Rötzer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Michael (ein anderer) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Hagen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Hagen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.