Zu blöd ein struct zu sortieren

[Ernst B. (puravida)]

Hi!

Ich bin irgendwie zu blöd ein struct zu sortieren. :-(

Den ganzen Code habe ich angehängt. Hier ein bisl zur Erklärung:

struct serv{
  volatile uint8_t servo;
  volatile int open;
  volatile int closed;
  volatile int position;
  volatile uint8_t *port;      //Adresse des Ports
  volatile uint8_t portbin;
} servos[SERVOANZAHL];

Bei volatile uint8_t *port; möchte ich gerne die Adresse des Ports 
einlesen. Initialisiert wird das dann mit servos[0].port = &PORTD zum 
Beispiel. Damit ich später mal mittels

*(servos[k].port) &= ~(servos[k].portbin);

den Entsprechenden Portbin auf High oder Low schalten kann.

Wenn ich jetzt das struct sortieren möchte nach dem Wert der bei 
servos[k].position angegeben ist stellt es mich irgendwie auf. 
Wahrscheinlich komme ich irgendwie mit den Pointern durcheinander oder 
so?

Könnt ihr mir bitte helfen, ich komme einfach nicht drauf.

Danke

LG
Ernst

[AVerr (Gast)]

Ernst B. schrieb:
> Wenn ich jetzt das struct sortieren möchte nach dem Wert der bei
> servos[k].position angegeben ist stellt es mich irgendwie auf.

Wie sortierst du das Ganze denn ?
Verschiebst du die Informationen im Array herum ?

Wenn du noch genügend Platz hast, könntest du ein Pointer-Array 
erstellen, dass auf diese serv-Elemente zeigt und nur die Pointer 
sortieren. Das sollte auch wesentlich flotter von der Hand gehen.

[AVerr (Gast)]

Ach, hatte deinen Anhang übersehen.

Struct-Zuweisungen funktionieren nicht immer so, wie du das erwartest.

sort[k] = sort[k-1];

wird dir also nicht den struct im Array verschieben. Du müsstest schon 
jedes einzelne Feld im struct kopieren, also

sort[k].open = sort[k-1].open;

etc...

Daher solltest du das lieber über Pointer machen wie oben erwähnt.

[Rufus Τ. F. (rufus)]

Ernst B. schrieb:
> Wenn ich jetzt das struct sortieren möchte

Meinst Du nicht vielleicht eher das Array? Eine Struktur kann man 
ebensowenig sortieren wie man einen anderen Datentyp sortieren kann.

Dein Versuch über ein Bubblesort schlägt fehl, weil Du in "temp" nicht 
ein Element des Arrays aufhebst, sondern nur einen Pointer darauf.

AVerr schrieb:
> Struct-Zuweisungen funktionieren nicht immer so, wie du das
> erwartest.
>
>   sort[k] = sort[k-1];
>
> wird dir also nicht den struct im Array verschieben.

Seit C89 sind Strukturzuweisungen zulässig.

[Karl H. (kbuchegg)]

AVerr schrieb:
> Ach, hatte deinen Anhang übersehen.
>
> Struct-Zuweisungen funktionieren nicht immer so, wie du das erwartest.

Doch das tun sie.


> wird dir also nicht den struct im Array verschieben. Du müsstest schon
> jedes einzelne Feld im struct kopieren, also

Bloss nicht.



Dein Code:

void Bubble(struct serv *sort, int elemente)
{
  uint8_t k; 
  struct serv *temp;
  
  while (elemente--)
  {
    for (k=1; k<=elemente; k++)
    {
      if (sort[k-1].position > sort[k].position)
      {
        *temp = sort[k];
        sort[k] = sort[k-1];
        sort[k-1]= *temp; 
        
      }
    }
  }

Kurze schmerzlose Frage.
Wo genau ist denn der Speicher, auf den du hier einen Pointer erzeugt 
hast

  struct serv *temp;

und auf den du hier

        *temp = sort[k];

eine komplette Struktur zwecks Zwischenspeicherung ablegen möchtest?

Nur weil du einen Pointer hast, heißt das noch lange nicht, dass du auch 
den entsprechenden Speicher für die Daten hast, auf die ein Pointer 
zeigen könnte.

[Εrnst B. (ernst)]

Wie groß ist denn deine SERVOANZAHL ? Wird die noch wesentlich größer 
als 8?

Lohnt es sich überhaupt, das vorzusortieren, bzw. für was brauchst du 
die definierte Reihenfolge in dem Array?

[Udo S. (urschmitt)]

Εrnst B✶ schrieb:
> Wie groß ist denn deine SERVOANZAHL ? Wird die noch wesentlich größer
> als 8?
>
> Lohnt es sich überhaupt, das vorzusortieren, bzw. für was brauchst du
> die definierte Reihenfolge in dem Array?

Das war doch der Beitrag mit 1µs Genauigkeit für 9 Servos ohne 
zeitlichen Versatz (also nicht sequentiell ein Servo nach dem anderen). 
Eine vorgeschlagene Lösung benötigte dazu die sortierten Zeiten der PWM.
Nachtrag: der hier:
Beitrag "Newbie braucht Hilfe: 9 Servos mit 1µs Auflösung ansteuern? (AVR)"

[Karl H. (kbuchegg)]

Udo Schmitt schrieb:
> Εrnst B✶ schrieb:
>> Wie groß ist denn deine SERVOANZAHL ? Wird die noch wesentlich größer
>> als 8?
>>
>> Lohnt es sich überhaupt, das vorzusortieren, bzw. für was brauchst du
>> die definierte Reihenfolge in dem Array?
>
> Das war doch der Beitrag mit 1µs Genauigkeit für 9 Servos ohne
> zeitlichen Versatz (also nicht sequentiell ein Servo nach dem anderen).
> Eine vorgeschlagene Lösung benötigte dazu die sortierten Zeiten der PWM.
> Nachtrag: der hier:
> Beitrag "Newbie braucht Hilfe: 9 Servos mit 1µs Auflösung ansteuern? (AVR)"

Wobei ich auch dort nicht davon überzeugt bin, dass es notwendig ist ein 
Servo 330 mal in der Sekunde upzudaten.

Ausserdem ist es eine GAAAAAAANZ schlechte Idee, wenn man sich diese 
Daten durcheinandsortiert. Das macht dann das zuweisen von neuen Werten 
so spannend, wenn man die Werte die zb aus der Mischerstufe 
herauskommen, dann auch noch an die richtigen Servokanäle verteilen 
will.

Aber vielleicht ist es ja auch nur eine Übung im behandeln von struct.

[Udo S. (urschmitt)]

Karl Heinz Buchegger schrieb:
> Wobei ich auch dort nicht davon überzeugt bin, dass es notwendig ist ein
> Servo 330 mal in der Sekunde upzudaten.

Eben, wie groß sind denn bei Flugmodellen die Zeitkonstanten der 
verschiedenen Bewegungen? Nimmt man einen kleinen Hubschrauber, dann sag 
ich mal keine Zeitkonstante der Bewegungen in irgendeiner der 3 Achsen 
ist kleiner als 1/10 Sekunde. Also macht es eigentlich keinen Sinn die 
Abtastzeit der Regelung deutlich unter 1/50 Sekunde zu legen.
Damit handelt man sich doch nur wieder Probleme ein, daß sich I Anteile 
zu weit aufintegrieren, D-Anteile zu schnell weg sind. Dann behilft man 
sich wieder indem man die Eingangswerte künstlich verlangsamt indem man 
gleitende Mittelwerte bildet etc.
Aber das hatten wir in dem Thread ja schon durchdiskutiert: Die Werbung 
sagt die Servos können so viel auflösen und sind so schnell, also muss 
es die erste Ansteuerung auch schon im allerersten Anlauf auch können 
(sollen)

Man kann sich das Leben selbst schwer machen, aber man wächst ja mit 
seinen Herausforderungen. Insofern: Viel Erfolg.

[Ernst B. (puravida)]

Karl Heinz Buchegger schrieb:
> Wobei ich auch dort nicht davon überzeugt bin, dass es notwendig ist ein
> Servo 330 mal in der Sekunde upzudaten.
>
> Ausserdem ist es eine GAAAAAAANZ schlechte Idee, wenn man sich diese
> Daten durcheinandsortiert. Das macht dann das zuweisen von neuen Werten
> so spannend, wenn man die Werte die zb aus der Mischerstufe
> herauskommen, dann auch noch an die richtigen Servokanäle verteilen
> will.
>
> Aber vielleicht ist es ja auch nur eine Übung im behandeln von struct.

Es ist beides. Das ganze Projekt ist eine Übung für mich. :-) Und es 
macht halt mehr Spaß was zu üben wenn man auch ein gewisses Ziel 
verfolgt.

Daß Du von den 330Hz nicht überzeugt bist habe ich eh gelesen. In dem 
Projekt habe ich auch schon auf 50Hz umgestellt. Bleibe aber trotzdem 
noch dabei alle Servos parallel anzusprechen und nicht seriell.

Neue Werte werden eigentlich nicht zugewiesen, die Werte werden 
eingestellt und liegen im EEProm, so der Plan zumindest. Und von einer 
Mischerstufe oder Fernbedienung kommen auch keine Werte die man 
berücksichtigen muß. Außer f_status der peridisch abgefragt werden soll.

Aber das ist eigentlich eh nicht Thema sondern das sortieren des Structs 
bzw. Arrays.

LG
Ernst

[Ernst B. (puravida)]

Karl Heinz Buchegger schrieb:
>
> Dein Code:
>

> void Bubble(struct serv *sort, int elemente)
> {
>   uint8_t k;
>   struct serv *temp;
> 
>   while (elemente--)
>   {
>     for (k=1; k<=elemente; k++)
>     {
>       if (sort[k-1].position > sort[k].position)
>       {
>         *temp = sort[k];
>         sort[k] = sort[k-1];
>         sort[k-1]= *temp;
> 
>       }
>     }
>   }
>

>
> Kurze schmerzlose Frage.
> Wo genau ist denn der Speicher, auf den du hier einen Pointer erzeugt
> hast
>
>   struct serv *temp;
>
> und auf den du hier
>
>         *temp = sort[k];
>
> eine komplette Struktur zwecks Zwischenspeicherung ablegen möchtest?
>
> Nur weil du einen Pointer hast, heißt das noch lange nicht, dass du auch
> den entsprechenden Speicher für die Daten hast, auf die ein Pointer
> zeigen könnte.

Hallo Karl Heinz,

inzwischen sind die Fragen schon nimmer schmerzlos... :-)

Ich dachte eigentlich, durch die Referenz von struct serv ist die Größe 
eigentlich klar. Aber scheinbar noch nicht wenn ich Deine Zeilen so 
lese.

Heißt das, daß ich mittels

temp = malloc(sizeof(struct serv *));

noch einen Speicher reservieren muß? Und muß ich den Speicher am Ende 
der Funktion wieder freigeben?

LG und Danke

Ernst

[Εrnst B. (ernst)]

Ich würde das nicht mit malloc machen, da fängtst du dir auf den kleinen 
AVRs einen ganzen Rattenschwanz zusätzlicher Fehlerquellen ein.

Stattessen könntest du ein zweites "sortier-array" verwenden:

(ungetesteter Pseudo-Code)

  uint8_t reihenfolge[9]={0,1,2,3,4,5,6,7,8};


Bubble:
...
 if (servos[reihenfolge[k-1]].position > servos[reihenfolge[k]].position) {
   // Swape nur noch die indices!
  uint8_t tmp=reihenfolge[k];
  reihenfolge[k]=reihenfolge[k-1];
  reihenfolge[k-1]=tmp;
 }
...

die Servos bleiben so an Ort und Stelle, d.H. "servos[5]" verweist immer 
auf das gleiche.
servos[reihenfolge[0]] bis servos[reihenfolge[8]] sind sortiert.

[Ernst B. (puravida)]

Rufus Τ. Firefly schrieb:
> AVerr schrieb:
>> Struct-Zuweisungen funktionieren nicht immer so, wie du das
>> erwartest.
>>
>>   sort[k] = sort[k-1];
>>
>> wird dir also nicht den struct im Array verschieben.
>
> Seit C89 sind Strukturzuweisungen zulässig.

Karl Heinz Buchegger schrieb:
> AVerr schrieb:
>> wird dir also nicht den struct im Array verschieben. Du müsstest schon
>> jedes einzelne Feld im struct kopieren, also
>
> Bloss nicht.
>

Widersprechen sich diese beiden Beiträge? Aber wahrscheinlich verstehe 
ich es nur nicht.

ist so eine Zuweisung

sort[k] = sort[k-1]

jetzt erlaubt oder nicht?

LG
Ernst

[struct (Gast)]

Und warum nicht einfach sowas wie

void Bubble(struct serv *sort, int elemente)
{
  uint8_t k; 
  struct serv *temp;
  
  while (elemente--)
  {
    for (k=1; k<=elemente; k++)
    {
      if (sort[k-1].position > sort[k].position)
      {
                                memcpy(temp,&sort[k],sizeof(serv));
                                memcpy(&sort[k],&sort[k-1],sizeof(serv));
                                memcpy(&sort[k-1],temp,sizeof(serv));
        
      }
    }
  }

?

[Εrnst B. (ernst)]

Ernst B. schrieb:
> ist so eine Zuweisung
> sort[k] = sort[k-1]
> jetzt erlaubt oder nicht?

Probiers aus. Das Problem liegt eher hier:

> *temp = sort[k];

Wenn *temp "in den Void" zeigt.

dann lieber:

struct serv temp;
...

  temp = sort[k];

Wobei auch das bei deinen großzügig verteilten "volatiles" vermutlich 
suboptimal ausgeführt werden wird. memcopy statt der Zuweisung umgeht 
das.


Hier gleich vorneweg eine Warnung zum nächsten Fallstrick:
bei den "int"s (16 bit) in deiner Struct reicht das volatile alleine 
nicht aus, damit du diese gleichzeitig gefahrlos in der ISR und im 
Restprogramm verwenden kannst, zusätzlich müssen bei Zugriffen 
ausserhalb der ISR auf diese Variablen die interrupts gesperrt werden.

[Ernst B. (puravida)]

Εrnst B✶ schrieb:
> Ich würde das nicht mit malloc machen, da fängtst du dir auf den kleinen
> AVRs einen ganzen Rattenschwanz zusätzlicher Fehlerquellen ein.
>
> Stattessen könntest du ein zweites "sortier-array" verwenden:
>
> (ungetesteter Pseudo-Code)
>

>   uint8_t reihenfolge[9]={0,1,2,3,4,5,6,7,8};
> 
> 
> Bubble:
> ...
>  if (servos[reihenfolge[k-1]].position >
> servos[reihenfolge[k]].position) {
>    // Swape nur noch die indices!
>   uint8_t tmp=reihenfolge[k];
>   reihenfolge[k]=reihenfolge[k-1];
>   reihenfolge[k-1]=tmp;
>  }
> ...
> 
>

>
> die Servos bleiben so an Ort und Stelle, d.H. "servos[5]" verweist immer
> auf das gleiche.
> servos[reihenfolge[0]] bis servos[reihenfolge[8]] sind sortiert.

Hallo doppelter Namensvetter! (Ist ja schon selten, daß noch jemand 
Ernst heißt. Aber noch dazu den gleichen Buchstaben beim Nachnamen...)

Das ist auch eine lässige Idee. Ich sortiere dann nur noch das Array 
reihenfolge[], richtig? Ist sicher eine praktikablere Lösung als das was 
ich wollte. Ich kann auch die Servonummer im Struct weglassen wenn dann 
servos[5] immer aufs gleiche verweist.  (Wobei mir nicht klar ist wie 
ich die Reihenfolge beim Debuggen kontrolliere, aber gut, das sehe ich 
dann :-))

Neugierig wäre ich aber doch wie man das struct-Array von meiner 
Ausgangsfrage sortiert? Muß ja auch irgendwie gehen.

LG
Ernst

[struct (Gast)]

Εrnst B✶ schrieb:
> Hier gleich vorneweg eine Warnung zum nächsten Fallstrick:
> bei den "int"s (16 bit) in deiner Struct reicht das volatile alleine
> nicht aus, damit du diese gleichzeitig gefahrlos in der ISR und im
> Restprogramm verwenden kannst, zusätzlich müssen bei Zugriffen
> ausserhalb der ISR auf diese Variablen die interrupts gesperrt werden.

kurz eine Erklärung dazu: Da der AVR nur 8 Bit auf einmal verarbeitet 
könnte zwischen den beiden Bytes (high und low) ein Interrupt kommen der 
die Daten liest bzw. ändert, das ergibt dann Inkonsistenzen.

z.B. main: schreibt beide Bytes, tut irgendwas, schreibt neues low-Byte, 
Interrupt
ISR: liest altes high-Byte und neues low-Byte -->bumm.

Fachbegriff imho "atomarer Zugriff".

[struct (Gast)]

(streiche imho ersetze durch iirc)

[Ernst B. (puravida)]

struct schrieb:
> Εrnst B✶ schrieb:
>> Hier gleich vorneweg eine Warnung zum nächsten Fallstrick:
>> bei den "int"s (16 bit) in deiner Struct reicht das volatile alleine
>> nicht aus, damit du diese gleichzeitig gefahrlos in der ISR und im
>> Restprogramm verwenden kannst, zusätzlich müssen bei Zugriffen
>> ausserhalb der ISR auf diese Variablen die interrupts gesperrt werden.
>
> kurz eine Erklärung dazu: Da der AVR nur 8 Bit auf einmal verarbeitet
> könnte zwischen den beiden Bytes (high und low) ein Interrupt kommen der
> die Daten liest bzw. ändert, das ergibt dann Inkonsistenzen.
>
> z.B. main: schreibt beide Bytes, tut irgendwas, schreibt neues low-Byte,
> Interrupt
> ISR: liest altes high-Byte und neues low-Byte -->bumm.
>
> Fachbegriff imho "atomarer Zugriff".

Ich glaube, die volatile kann ich mir eh überall sparen bis auf den 
Port-Zeiger. Der dürfte lt. Karl Heinz so definiert sein:

Karl Heinz Buchegger schrieb:
> ein Port hat den Datentyp *(volatile unsigned char*)

Warum das aber ein char sein soll...?

In den FAQ steht: "...volatile teilt dem Compiler mit, dass ausnahmslos 
alle Zugriffe auf eine Variable auch tatsächlich auszuführen sind und 
keine Optimierungen gemacht werden dürfen, weil sich eine Variable auf 
Wegen ändern kann, die für den Compiler prinzipiell nicht einsichtig 
sind." Deshalb dachte ich, daß es eventuell Bröseln beim sortieren gibt.

Den Wert servos[].position werde ich in einer weiteren Routine 
verändern. Aber keiner der Werte aus dem struct wird in einer ISR 
verändert. Also nix was für den Compiler überraschend hinter seinem 
Rücken passieren sollte. Ich schwitze allerdings immer davor, daß 
irgendwas wegoptimiert wird. :-))

So, ich werde jetzt mal die einzelnen Vorschläge ausprobieren. :-D

[Ernst B. (puravida)]

Εrnst B✶ schrieb:
> dann lieber:
>

> struct serv temp;
> ...
> 
>   temp = sort[k];
>

>
> Wobei auch das bei deinen großzügig verteilten "volatiles" vermutlich
> suboptimal ausgeführt werden wird. memcopy statt der Zuweisung umgeht
> das.

Was heißt "suboptimal" in dem Fall? Einfach "nur" langsam oder stellt es 
mich mit dem Speicher irgendwann auf? (die Sortierungsroutine wird 
häufig aufgerufen)

LG
Ernst

[Rufus Τ. F. (rufus)]

Ernst B. schrieb:
> Was heißt "suboptimal" in dem Fall?

Langsam. Sehr langsam, im Vergleich zur Variante mit dem Pointerarray.

[Karl H. (kbuchegg)]

Rufus Τ. Firefly schrieb:
> Ernst B. schrieb:
>> Was heißt "suboptimal" in dem Fall?
>
> Langsam. Sehr langsam, im Vergleich zur Variante mit dem Pointerarray.

Dafür sind dann die Zugriffe in der sortierten Reihenfolge um einen Tick 
schneller.
Man kann eben nicht alles haben.

Wichtig wär auch noch den Bubbelsort entweder durch etwas besseres zu 
ersetzen oder dem einen vorzeitigen Abbruch zu erlauben wenn sich deine 
Werte von einem Sortierlauf zum nächsten nur wenig ändern.

[Ernst B. (puravida)]

Karl Heinz Buchegger schrieb:
> Rufus Τ. Firefly schrieb:
>> Ernst B. schrieb:
>>> Was heißt "suboptimal" in dem Fall?
>>
>> Langsam. Sehr langsam, im Vergleich zur Variante mit dem Pointerarray.
>
> Dafür sind dann die Zugriffe in der sortierten Reihenfolge um einen Tick
> schneller.
> Man kann eben nicht alles haben.

Wenn der Zugriff auf die sortierte Reihenfolge schneller ist, dann kommt 
mir das eher gelegen als eine schnellere Sortierung. Ich greife ja dann 
in einer ISR darauf zu und das ist das zeitkritischere.

>
> Wichtig wär auch noch den Bubbelsort entweder durch etwas besseres zu
> ersetzen

Was wäre denn schneller bzw. besser? Im Buch C von A bis Z schneidet bei 
wenigen Elementen das Bubble-Sort sehr gut ab. Nur noch selection-Sort 
ist einen Tick schneller. Vielleicht sollte ich das mal probieren.

> oder dem einen vorzeitigen Abbruch zu erlauben wenn sich deine
> Werte von einem Sortierlauf zum nächsten nur wenig ändern.

Ich probiere lieber einen anderen Sortieralgorithmus denn dazu habe ich 
keine Idee wie ich das anstelle.

Ich kämpfe eh gerade - nachdem das jetzt sortiert wird - damit, daß mein 
Code, je nachdem ob ich mit den open oder closed Werten beginne, 
funktioniert bzw. nicht funktioniert. Dem Code nach sollte es eigentlich 
egal sein, ist es aber nicht. grml

@Rufus: Ich habe gerade gesehen, daß ich mich vorher verlesen habe. 
Sorry. Habe ...seit C89 unzulässig... gelesen statt zulässig.

[Karl H. (kbuchegg)]

Ernst B. schrieb:

>> oder dem einen vorzeitigen Abbruch zu erlauben wenn sich deine
>> Werte von einem Sortierlauf zum nächsten nur wenig ändern.
>
> Ich probiere lieber einen anderen Sortieralgorithmus denn dazu habe ich
> keine Idee wie ich das anstelle.

   do {
     sorted = true;
     for( i = 0; i < NrElements - 1; ++i )
       if( element[i] > element[i+1] ) {
         tmp = element[i];
         element[i] = element[i+1];
         element[i+1] = tmp;
         sorted = false;
       }
     }
   } while( !sorted );

sobald bei einem Durchlauf durch die for Schleife festgestellt wird, das 
alles sortiert ist, hört der Algorithmus auf. Wenn nur wenige 
Vertauschungen notwendig sind (weil sich die Daten nur wenig verändert 
haben), macht das einen Unterschied. Sind die Daten bereits sortiert 
oder nahezu sortiert, dann ist das von keinem anderen Sortierverfahren 
zu schlagen. Leider gibts den Fall nur selten. Deiner könnte aber so 
einer sein.

[Cyblord -. (cyblord)]

Karl Heinz Buchegger schrieb:
> Ernst B. schrieb:
>

>

>    do {
>      sorted = true;
>      for( i = 0; i < NrElements - 1; ++i )
>        if( element[i] > element[i+1] ) {
>          tmp = element[i];
>          element[i] = element[i+1];
>          element[i+1] = tmp;
>          sorted = false;
>        }
>      }
>    } while( !sorted );
>

>

Das gute alte Bubblesort. Aber ob man dies wirklich produktiv einsetzen 
sollte? Bedenke das Ding läuft in O(n²).

gruß cyblord

[Εrnst B. (ernst)]

cyblord ---- schrieb:
> Bedenke das Ding läuft in O(n²)

Naja, N ist in dem Fall ja "9".
Also läufts in O(9^2) = O(81) = O(1)
;)

Scherz beiseite: Hier wird ja eine Datenstruktur benötigt, bei der der 
"dringenste" Servo-Eintrag vorne liegt, eine komplette Sortierung ist 
garnicht nötig.

daher: statt komplett sortieren vielleicht eine "priority queue" 
einsetzen. Lässt sich schön innerhalb des Arrays (Binary Heap) 
implementieren.

Entnehmen des "fälligen" Servos in der ISR als auch wieder-einfügen 
eines Servos mit geänderter "position" gehen dann in O(log N).

[PuraVida (Gast)]

cyblord ---- schrieb:
> Das gute alte Bubblesort. Aber ob man dies wirklich produktiv einsetzen
> sollte? Bedenke das Ding läuft in O(n²).

Das läuft in was? :-))

[Karl H. (kbuchegg)]

cyblord ---- schrieb:


> Das gute alte Bubblesort. Aber ob man dies wirklich produktiv einsetzen
> sollte? Bedenke das Ding läuft in O(n²).

Diese Variante allerdings nur im Worstcase.

[Cyblord -. (cyblord)]

Karl Heinz Buchegger schrieb:
> cyblord ---- schrieb:
>
>
>> Das gute alte Bubblesort. Aber ob man dies wirklich produktiv einsetzen
>> sollte? Bedenke das Ding läuft in O(n²).
>
> Diese Variante allerdings nur im Worstcase.

Ändert nichts, die Laufzeit liegt in O(n²). Du kannst keine kleinere 
obere Schranke angeben. Natürlich wird die reale Laufzeit einiges 
darunter liegen, aber es geht ja darum wie schlimm es mit vielen 
Elementen wird. Und mit BS wird es sehr schlimm.
Vergleiche hierzu QuickSort, hat ebenfalls im Worst-Case O(n²), arbeitet 
jedoch unter Normalbedingungen in O(n*log(n)).

Wenn man auf der sicheren Seite sein will, sollte man sich mal 
Intro-Sort angucken. Sortiert normalerweise mit Quicksort, erkennt aber 
Partition-Elements welche in einem Teilarray eine Worst-Case Laufzeit 
hervorrufen und fällt dann für diesen Teil auf Heap-Sort zurück. Sehr 
effizient gelöst, alles in allem.

gruß cyblord

[PuraVida (Gast)]

Εrnst B✶ schrieb:
> Scherz beiseite: Hier wird ja eine Datenstruktur benötigt, bei der der
> "dringenste" Servo-Eintrag vorne liegt, eine komplette Sortierung ist
> garnicht nötig.

Ich bin in meinen Überlegungen eigentlich davon ausgegangen, daß ich 
eine komplette Sortierung - zumindest der aktuellen bzw. nächsten 
Positionswerte brauche.

Da ich die Werte ja nicht kenne kann es sein, daß - so wie bei meinen 
Beispielwerten - einige Positionen sehr knapp oder gar genau gleich 
sind. Die kann ich dann nicht mit dem OCR1B abfangen sondern muß über 
die Differenz zum vorhergehenden Servo diese im selben ISR-Aufruf 
abschalten. (Das ist IMHO der größte Schwachpunkt meiner Lösung. Ich 
kann zwar 9 Servos anschließen, diese auch 1µs genau ansprechen. Aber 
nicht, wenn zwei Werte sehr knapp nebeneinander liegen bzw. gleich 
sind.)

Dazu habe ich jetzt noch ein Flag im Struct eingefügt auf das hin 
untersucht wird.

Zwischen den Open und Closed werten muß auch noch eine Berechnung 
stattfinden damit die Servos in der Verfahrensgeschwindigkeit 
eingestellt werden können. Ich nähere mich also von der Open-Position zb 
2000 langsam, zB in 10er Schritten der Closed-Position 4000. Da bleibt 
die Liste - zumindest am Anfang - eigentlich sortiert. Deswegen scheint 
mir so ein Abbruch der Sortierung eine gute Idee zu sein.


LG
Ernst

[Karl H. (kbuchegg)]

cyblord ---- schrieb:
> Karl Heinz Buchegger schrieb:
>> cyblord ---- schrieb:
>>
>>
>>> Das gute alte Bubblesort. Aber ob man dies wirklich produktiv einsetzen
>>> sollte? Bedenke das Ding läuft in O(n²).
>>
>> Diese Variante allerdings nur im Worstcase.
>
> Ändert nichts, die Laufzeit liegt in O(n²). Du kannst keine kleinere
> obere Schranke angeben. Natürlich wird die reale Laufzeit einiges
> darunter liegen, aber es geht ja darum wie schlimm es mit vielen
> Elementen wird. Und mit BS wird es sehr schlimm.
> Vergleiche hierzu QuickSort, hat ebenfalls im Worst-Case O(n²), arbeitet
> jedoch unter Normalbedingungen in O(n*log(n)).


Genau.
Und wenn die Werte bereits nahezu sortiert vorliegen, ist BS nicht so 
schlecht, bei geringem Aufwand. Und da es sich um Servowerte handelt, 
die sich über die Zeit gesehen von einem Zeitschritt zum nächsten nur 
wenig ändern, ist die Annahme, dass die Daten bereits nahezu sortiert 
vorliegen, nicht von der Hand zu weisen.

Nichts anderes sag ich die ganze Zeit.

Du gehst immer vom allgemeinen Fall aus, ich hingegen versuch ein wenig 
Wissen über die Daten mitzubenutzen.

Meine 'Verteidigung' ist keineswegs als allgemeine Empfehlung für BS zu 
sehen! Bisher hatte ich nur 1 Fall, in dem BS tatsächlich (wegen seiner 
Einfachheit und eben der nahezu Sortiertheit) die beste Lösung 
darstellte. Ein Scan-Line Sweep Algorithmus, bei dem in jeder Scanline 
Punkte sortiert werden müssen und die sich von einer Scanline zur 
nächsten nur selten ändern. BS läuft dann in fast O(n), wobei der 
konstante Anteil, der in der O Notation geflissentlich ignoriert wird 
bei BS eben so klein ist, dass er O(log(n)) aussticht. O Notation ist 
gut, wenn man auf große Zahlen extrapolieren muss. 9 Elemente in einem 
Array sind aber nicht große Mengen.

[cyblord (Gast)]

Karl Heinz Buchegger schrieb:

> Genau.
> Und wenn die Werte bereits nahezu sortiert vorliegen, ist BS nicht so
> schlecht, bei geringem Aufwand. Und da es sich um Servowerte handelt,
> die sich über die Zeit gesehen von einem Zeitschritt zum nächsten nur
> wenig ändern, ist die Annahme, dass die Daten bereits nahezu sortiert
> vorliegen, nicht von der Hand zu weisen.
Stimmt.
>
> Nichts anderes sag ich die ganze Zeit.
Ich weiß doch
>
> Du gehst immer vom allgemeinen Fall aus, ich hingegen versuch ein wenig
> Wissen über die Daten mitzubenutzen.

Da ist was drann. Vorallem weil wir ja hier, soweit ich sehe, ein 
relativ kleines konstantes n haben.

[Klaus W. (mfgkw)]

Wenn man nicht selbst sortieren kann oder will, kann man im 
alleräussersten Notfall ja noch auf die Standard-C-Bibliothek 
zurückgreifen.
Da gibt es ein quick sort, das kaum zu toppen ist im allgemeinen Fall, 
ausgetestet und kostenlos ist und nur mit einer passenden 
Vergleichsfunktion aufgerufen werden muß (schließlich muß ja irgendwo 
gesagt werden, anhand welchen Kriteriums sortiert werden soll).

/* Time-stamp: "15.11.11 18:24 t.c klwa4345?wachtler.de"
 *
 * [1] http://linux.die.net/man/3/qsort
 */

#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>

#define  SERVOANZAHL       (10)

typedef struct serv
{
    volatile uint8_t  servo;
    volatile int      open;
    volatile int      closed;
    volatile int      position;
    volatile uint8_t *port;      //Adresse des Ports
    volatile uint8_t  portbin;
} serv_t;

serv_t   servos[SERVOANZAHL] =
{
    { 100, 10100, 0, 10, NULL, 20 },
    { 190, 19190, 0, 19, NULL, 29 },
    { 110, 11110, 0, 11, NULL, 21 },
    { 170, 17170, 0, 17, NULL, 27 },
    { 180, 18180, 0, 18, NULL, 28 },
    { 140, 14140, 0, 14, NULL, 24 },
    { 150, 15150, 0, 15, NULL, 25 },
    { 130, 13130, 0, 13, NULL, 23 },
    { 120, 12120, 0, 12, NULL, 22 },
    { 160, 16160, 0, 16, NULL, 26 },
};

/* vergleicht zwei serv_t anhand von position, z.B. fuer qsort() oder
 * bsearch()
 *
 * liefert einen Wert <0, wenn p1->position<p2->position, einen Wert
 * gleich 0, wenn p1->position==p2->position, sonst einen Wert >0.
 */
int cmp_serv_t_by_position( const void *p1, const void *p2 )
{
    return ((const serv_t*)p1)->position - ((const serv_t*)p2)->position;
}

void dumpServos( const serv_t *p_servos, size_t nServos )
{
    size_t    iServo;
    for( iServo=0; iServo<nServos; ++iServo )
    {
        printf( "servo=%5u open=%5d closed=%5d position=%5d port=0x%08p portbin=%5u\n",
                (unsigned)p_servos[iServo].servo,
                p_servos[iServo].open,
                p_servos[iServo].closed,
                p_servos[iServo].position,
                p_servos[iServo].port,
                (unsigned)p_servos[iServo].portbin
              );
    }
}


int main( int nargs, char **args )
{
    puts( "vorher:" );
    dumpServos( servos, sizeof(servos)/sizeof(servos[0]) );

    qsort( servos,
           sizeof(servos)/sizeof(servos[0]),
           sizeof(servos[0]),
           cmp_serv_t_by_position
         );

    puts( "nachher:" );
    dumpServos( servos, sizeof(servos)/sizeof(servos[0]) );

  return 0;
}

[Ernst B. (puravida)]

Karl Heinz Buchegger schrieb:
>

>    do {
>      sorted = true;
>      for( i = 0; i < NrElements - 1; ++i )
>        if( element[i] > element[i+1] ) {
>          tmp = element[i];
>          element[i] = element[i+1];
>          element[i+1] = tmp;
>          sorted = false;
>        }
>      }
>    } while( !sorted );
>

Hi Karl Heinz,

warum hast Du da ein ++i und nicht ein i++?

Schreibe ich meine Schleifen bis jetzt falsch?  :-/

Würde die Schleife bei einem i++ zwei mal i=0 durchlaufen werden? (Weil 
ja postfix zuerst den "alten" Wert weitergibt und dann erst den 
addierten?)

Oder beginnt Deine Schleife mit i=1? (Was ich mir nicht vorstellen kann, 
Du wirkst sehr souverän in C auf mich)

Man sieht die For Schleifen aber so oft mit i++ statt ++i?

LG
Ernst

[Stefan E. (sternst)]

Ernst B. schrieb:
> warum hast Du da ein ++i und nicht ein i++?

Ist an der Stelle völlig egal, die "Rückgabe" des Ausdrucks wird ja 
nicht verwendet. Ist lediglich eine Frage des persönlichen Geschmacks.

[Karl H. (kbuchegg)]

Ernst B. schrieb:

> warum hast Du da ein ++i und nicht ein i++?

C++ Gewohnheit.

In C ist es völlig wurscht, weil ++ sowieso nur auf integrale Typen 
angewendet werden kann. In C++ kann es einen Unterschied in der Laufzeit 
mchen, wenn die Laufvariable einen Datentyp hat, der Iterator Charakter 
hat und die Pre und Post-fix ++ Operation implementier hat. In a 
Nutshell: die Prefix Operation ++ kann man ohne Hilfsvariable 
implementieren, die Postfix Version aber nicht. D.h. man hat eine 
Objekterzeugung, die der Compiler mglw. nicht wegoptimieren kann.

Wie gesagt: Es ist einfach nur als eine von C++ herübertransportierte 
Gewohnheit anzusehen, die in C keine Rolle spielt und an dieser Stelle 
keinerlei funktionalen Unterschied mit sich bringt.