Hi zusammen,
ich habe ein struct, das bspw. zwei Variablen beinhaltet, x und y.
Nun habe ich ein Array (ca. 100 Elemente lang), das nach und nach mit
diesen Structs gefüllt wird. Dabei soll in aufsteigender Reihenfolge
nach x direkt beim Befüllen das neue Struct sortiert/eingeordnet werden.
Nun würde ich es so angehen:
- Herausfinden, an welcher Stelle im Array x größer gleich dem neuen
Struct-Element ist
- Alle Elemente bis hin zu dieser Stelle um einen Platz im Array
weiterschieben
- Das neue Struct einfügen.
Gibt es dafür noch einen besseren Weg? Oder kann man sogar automatisch
ein Struct Array nach einer bestimmten Variable sortieren lassen?
Wenn ja, wie viel Zeit/Rechenaufwand beansprucht diese Aufgabe?
Gruß,
Durokh
Durokh schrieb:> Oder kann man sogar automatisch ein Struct Array nach einer bestimmten> Variable sortieren lassen?
Ja, mit qsort. Du mußt nur eine kleine Funktion schreiben, die zwei
Elemente vergleicht und zurückmeldet, welches von beiden nach dem von
dir gewünschten Kriterium als größer zu betrachten ist.
Ohne das jetzt genauer analysiert zu haben, würde ich erwarten, daß das
auch schneller geht, als beim Einsortieren jedesmal alle folgenden
Elemente umkopieren zu müssen.
Das kommt schwer auf die Sortierung und der Struktur an. Man kann sich
da ziemlich unglücklich damit machen.
Du vermischst zwei Dinge. Handhabung der Strukturen in einem Array und
dessen Sortierung.
Ersteres hängt stark von der Zielplattform ab und der verwendeten
Sprache (c/c++).
Zweiteres, hängt davon ab wie dein Key aussieht mit dem du sortieren
willst.
Also lässt sich das mit den Angaben pauschal kaum beantworten.
Grüsse,
René
Auch nicht ganz uninteressant:
Was bedeutet 'nach und nach'?
Alle 2 Minuten mal ein Neuzugang oder alle 100 in einem Aufwasch aber
eben eins nach dem anderen.
Je nachdem ist es schneller ob man sich nur um dieses 1 neue Element
kümmert oder ob man (gegebenenfalls) erst mal alle einfügt und dann alle
in einem Aufwasch sortiert.
Rene H. schrieb:> Du vermischst zwei Dinge. Handhabung der Strukturen in einem Array und> dessen Sortierung.>> Ersteres hängt stark von der Zielplattform ab und der verwendeten> Sprache (c/c++).
Ich möchte auf einem Atmega644 dieses Array befüllen lassen.
Rene H. schrieb:> Zweiteres, hängt davon ab wie dein Key aussieht mit dem du sortieren> willst.
Meinst du mit "Key" die Zielvariable? Wenn ja: Dabei handelt es sich um
16-Bit Integer.
Karl Heinz Buchegger schrieb:> Auch nicht ganz uninteressant:> Was bedeutet 'nach und nach'?> Alle 2 Minuten mal ein Neuzugang oder alle 100 in einem Aufwasch aber> eben eins nach dem anderen.> Je nachdem ist es schneller ob man sich nur um dieses 1 neue Element> kümmert oder ob man (gegebenenfalls) erst mal alle einfügt und dann alle> in einem Aufwasch sortiert.
Aus einem Datenstrom über die Serielle Schnittstelle (Baudrate: 115200
)werden die einzelnen Structs ausgelesen und in das Array geladen. Also
alle 100 in einem Aufmarsch.
Aus deiner Frage lese ich heraus, dass das Sortieren im Nachhinein
geeigneter ist, korrekt?
Rolf Magnus schrieb:> Ja, mit qsort. Du mußt nur eine kleine Funktion schreiben, die zwei> Elemente vergleicht und zurückmeldet, welches von beiden nach dem von> dir gewünschten Kriterium als größer zu betrachten ist.> Ohne das jetzt genauer analysiert zu haben, würde ich erwarten, daß das> auch schneller geht, als beim Einsortieren jedesmal alle folgenden> Elemente umkopieren zu müssen.
Ist qsort immer noch sinnvoll, wenn ich nachträglich alles sortieren
lassen?
Und: Wie kann ich die Zeit, die für das Sortieren benötigt wird,
berechnen? Das müsste ich nämlich wissen.
Durokh schrieb:> Aus einem Datenstrom über die Serielle Schnittstelle (Baudrate: 115200> )werden die einzelnen Structs ausgelesen und in das Array geladen. Also> alle 100 in einem Aufmarsch.> Aus deiner Frage lese ich heraus, dass das Sortieren im Nachhinein> geeigneter ist, korrekt?
korrekt.
Vergleichsfunktion schreiben - qsort anwerfen und die Sache ist geritzt.
Details findest du in deinem C-Buch
> Ist qsort immer noch sinnvoll, wenn ich nachträglich alles sortieren> lassen?
Gerade WEIL du nachträglich sortierst, ist ein ordentliches
Sortierverfahren das Mittel der Wahl.
> Und: Wie kann ich die Zeit, die für das Sortieren benötigt wird,> berechnen? Das müsste ich nämlich wissen.
Dazu gibts theoretisce Untersuchungen, wie sich die Sortierzeit im
Mittel verhält und mit der Anzahl der zu sortierenden Elemente
entwickelt. Hängt ja auch nicht ganz unwesentlich von den Daten selber
ab.
Also: im einfachsten Fall messen! Mit ein paar typischen Stichproben
kriegst du aussagekräftige Zahlen.
Du kannst natürlich auch erst mal dich ein bischen einlesen. Das Thema
Sortieren und was damit zusammenhängt 'Suchen' ist ja in der EDV nicht
ganz unwichtig. Da wurden auch schon Bücher darüber geschrieben. Da
empfehle ich mal den Band (ich glaube es war) 3 der Reihe "The Art of
Computer Programming" von Donald Knuth mit dem Subtitel "Sorting and
Searching". Hat ja nur so um die 300 Seiten. (wenn man mit 300 überhaupt
auskommt)
Edit und PS: Das 'q' in 'qsort' steht für 'quick'.
Wenn nur beim Einfügen sortiert eingefügt werden soll, bietet sich - bei
selber machen - eine verkettet Liste geradezu an. Ob sie doppelt
verkettet sein muß, ist noch die Frage. Die Implementierung ist
sicherlich recht überschaubar und sehr kompakt. Bei einigen
Sotieralgorithmen spielen Rekursionen eine Rolle, die auf einem AVR
nicht unbedingt zu empfehlen sind.
Rosa
Rosa-Kleidchen schrieb:> Wenn nur beim Einfügen sortiert eingefügt werden soll, bietet sich - bei> selber machen - eine verkettet Liste geradezu an.
Alternative wäre ein simples zusätzliches Array A, welches mit den
Indices des zu sortierenden Arrays S gefüllt ist. Dann lässt man per
qsort einfach das Array A sortieren.
Der Vorteil: Die Originaldaten werden gar nicht sortiert (also
umfangreich im Speicher hin- und hergeschoben), sondern nur die Indices
darauf.
Nachteil: Der sortierte Zugriff erfolgt indirekt auf das Array S - unter
Zuhilfenahme von A.
Wenn die Daten sowieso im RAM stehen, ist diese Art von "umständlicher"
Sortierung ziemlich unsinnig. Sind sie aber größer (als das verfügbare
RAM) und stehen sie zum Beispiel auf einem externen Datenträger oder in
einem EEPROM, dann kann diese Art und Weise der Sortierung sehr
effizient sein.
Rosa-Kleidchen schrieb:> sicherlich recht überschaubar und sehr kompakt. Bei einigen> Sotieralgorithmen spielen Rekursionen eine Rolle, die auf einem AVR> nicht unbedingt zu empfehlen sind.
Übertreib mal nicht.
Bei einer Datengröße von 100 hast du eine rekursive Schachtelungstiefe
von ca. 7 bis 9, je nachdem an welcher Stelle der Quicksort seinen
Sentinel einsetzt. Alles noch überschaubar.
Man kann natürlich auch einen Shell-Sort oder Heap-Sort selber
schreiben, wenn man der vorhandenen Quicksort-Lösung nicht über den Weg
traut.
Wenns auf Laufzeit ankommt und man damit leben kann, dass man eine
Obergrenze für die Anzahl verarbeitbarer Daten festlegen muss, ist das
alles um Größenordnungen besser als eine verkettete Liste mit direktem
Einfügen. Zumal ja die Verkettung der Liste auch Speicher braucht, den
man ja aber angeblich für die paar Rekursionsstufen nicht hat.
Rosa-Kleidchen schrieb:> Wenn nur beim Einfügen sortiert eingefügt werden soll, bietet sich - bei> selber machen - eine verkettet Liste geradezu an.
Suchen/Zugriff und sortiertes Einfügen sind da recht ineffizient. Das
sollte man daher auch nur bei kleinen Datensätzen machen (wobei in einen
AVR auch nichts wirklich Großes passt).
Andreas B. schrieb:> Suchen/Zugriff und sortiertes Einfügen sind da recht ineffizient.
ich den zugriff bei einer verkettet Liste eigentlich sehr ineffizient.
Man geht einfach der reihe nach durch und wenn das das nächste elemen
kleiner als das einzufügende ist, dann wird einfach die Kette an dieser
stelle verlängert.
Peter II schrieb:> Andreas B. schrieb:>> Suchen/Zugriff und sortiertes Einfügen sind da recht ineffizient.>> ich den zugriff bei einer verkettet Liste eigentlich sehr ineffizient.> Man geht einfach der reihe nach durch
Ja, eine lineare Suche eben. Die ist nicht besonders effizient. Besser
wäre ein binärer Baum.
> und wenn das das nächste elemen kleiner als das einzufügende ist, dann> wird einfach die Kette an dieser stelle verlängert.
Das einzige, was da effizienter ist als beim Array ist das eigentiche
Einfügen. Die Suche nach der Stelle zum Einfügen ist eher langsamer, da
man jedesmal erst den Pointer auf's nächste Element aus dem Speicher
lesen muss. Beim Array kann ich einen Pointer oder einen Index in einem
Register halten und jedesmal einfach inkrementieren.
Rolf Magnus schrieb:> Ja, eine lineare Suche eben. Die ist nicht besonders effizient. Besser> wäre ein binärer Baum.
wobei dann das sortierte aulesen wieder schwerer ist.
Karl Heinz Buchegger schrieb:> Also: im einfachsten Fall messen! Mit ein paar typischen Stichproben> kriegst du aussagekräftige Zahlen.
Messen, indem ich am Atmega einfach einen Pin direkt vor und nach dem
Sortieren einen Pin high/low setze? Oszi hätte ich dafür hier stehen.
Die Sache mit der verketteten Liste lasse ich mir nochmal durch den Kopf
gehen.
Auf jeden Fall vielen Dank! Das gibt mir auf jeden Fall die Sicherheit,
dass ich nun zwei Wege habe, die in Ordnung sind. Ich glaube, bei der
Wahl ist es dann letztendlich "Geschmackssache" bzw. Erfahrung, womit
man in der Vergangenheit am meisten gearbeitet hat. Bei mir ist beides
nicht der Fall, daher schaue ich mir beides mal an.
Danke nochmal!
Gruß,
Durokh
PS: Ich schreib nachher aber nochmal einen Thread zu einem anderen
Thema, das hiermit aber auch zu tun hat.
>Übertreib mal nicht.>Bei einer Datengröße von 100 hast du eine rekursive Schachtelungstiefe>von ca. 7 bis 9, je nachdem an welcher Stelle der Quicksort seinen>Sentinel einsetzt. Alles noch überschaubar.
Meine Erfahrungen sagen mir, dass aus 100 schnell mal 1000 und mehr
werden können. Die Begehrlichkeiten sind dann schnell da.
Rosa
>Ja, eine lineare Suche eben. Die ist nicht besonders effizient. Besser>wäre ein binärer Baum.
Immer noch effizienter als Sortieren! Aber gute Idee! Einen binären Baum
benutzen zum Suchen der Stelle, in der das Element eingefügt werden soll
und eine verkettete Liste hält die sortierten Elemente.
Rosa
Peter II schrieb:> Rolf Magnus schrieb:>> Ja, eine lineare Suche eben. Die ist nicht besonders effizient. Besser>> wäre ein binärer Baum.>> wobei dann das sortierte aulesen wieder schwerer ist.
Geht so. Ist auch nur eine rekursive Funktion. Wobei, da gibt es auch
eine clevere Strategie den Baum aufzufädeln, indem man die Verpointerung
manipuliert und so die Rekursion vermeidet.
Wobei die Sache mit dem Binärbaum auch wieder ihre Tücken hat. Mit den
richtigen Daten degeneriert das dann schon wieder schnell in die Nähe
einer linearen Liste. D.h. Besser wäre ein balanzierter binärer Baum.
Aber jetzt steigt der Aufwand schon beträchtlich.
Was sich auch lohnen kann, wenn wesentlich mehr Abfragen als Einfügungen
gemacht werden.
Aber ich denke wir sind uns soweit einig, dass auf einem kleinen AVR
schon rein technisch die Datenmenge nicht zustande kommen wird, so dass
sich da etwas großartig gefinkeltes lohnt. Bei beispielsweise 10
angenommenen Datensätzen lohnt sich binäres Suchen nicht gegenüber
simplen linearen Suchen. Mit dem von TO genannten Mengengeräst von 100
Datensätzen ist man da zwar schon über der Grenze drüber, wo die
programmtechnische gegen gefinkelte Strategien verlieren wird, aber auch
nur eher sehr knapp. In einem Array halten, sortieren und dann binär
suchen sollte bei diesem Mengen eigentlich ein guter Kompromiss aus
Aufwand und Nutzen darstellen. Zumal ja beide 'komplizierte' Operationen
von der Standard-Lib in Form von Funktionen abgedeckt sind, so dass sich
auch der programmiertechnische Aufwand dafür in Grenzen hält.
NB ist ja von Suchen im Originalposting überhaupt nicht die Rede.
Rosa-Kleidchen schrieb:>>Übertreib mal nicht.>>Bei einer Datengröße von 100 hast du eine rekursive Schachtelungstiefe>>von ca. 7 bis 9, je nachdem an welcher Stelle der Quicksort seinen>>Sentinel einsetzt. Alles noch überschaubar.> Meine Erfahrungen sagen mir, dass aus 100 schnell mal 1000 und mehr> werden können.
Der TO hat es zwar nicht explizit geschrieben, ich sags aber trotzdem:
Auf einem kleinen AVR mit vielleicht 2kB SRAM?
> Einen binären Baum benutzen zum Suchen der Stelle, in der das Element> eingefügt werden soll und eine verkettete Liste hält die sortierten> Elemente.
Dein Enthusiasmus in allen Ehren. Aber wieviel Speicher willst du
eigentlich noch sinnlos verbrutzeln?
Rosa-Kleidchen schrieb:>>Ja, eine lineare Suche eben. Die ist nicht besonders effizient. Besser>>wäre ein binärer Baum.> Immer noch effizienter als Sortieren!
Naja, kommt drauf an. Wenn man nur eine Liste füllen und dann einmalig
sortieren muss, ist das die einfachere Möglichkeit. Wenn die Daten aber
tröpfchenweise reinkommen und zwischendurch auch immer sortiert sein
müssen, siehts natürlich anders aus. Du musst auch bedenken, daß jedes
Element aus gerade mal zwei 16-Bit-Integern besteht. Wenn man statt
eines Arrays eine doppelt verkettete Liste draus macht, verdoppelt sich
der Speicherverbrauch dadurch (16-Bit-Zeiger angenommen). Und die Zeiger
umzubiegen ist auch nicht weniger Aufwand als beim Array zwei Elemente
einfach durch umkopieren auszutauschen.
> Aber gute Idee! Einen binären Baum benutzen zum Suchen der Stelle, in der> das Element eingefügt werden soll und eine verkettete Liste hält die> sortierten Elemente.
Wozu soll da die verkettete Liste gut sein?
Durokh schrieb:> - Alle Elemente bis hin zu dieser Stelle um einen Platz im Array> weiterschieben> - Das neue Struct einfügen.>> Gibt es dafür noch einen besseren Weg?
Wohl nicht. Abgesehen davon, daß du nicht die Elemente bis zu dieser
Stelle, sondern die bereits gespeicherten Elemente ab dieser Stelle
verschieben mußt.
Ich sehe auch keinen Vorteil darin, alles erstmal wild zu speichern und
dann einen Sortieralgo drauf loszulassen. Das ist nicht produktiver,
denn man muß in jedem Falle alle Elemente anfassen, und das gleich
zweimal: einmal alle beim einstapeln und dann nochmal alle beim
Sortieren (vergleichen und ggf. vertauschen).
Das Suchen der richtigen Stelle ist in einem Array immer einfacher als
in einer verlinkten Kette, weil man nicht alle Einträge durchkämmen muß.
Stattdessen kann man darauf zurückgreifen, daß ja alles dort schon
vorhandene bereits sortiert ist, man kann also dort binär suchen.
Naja, und das stupide Verschieben eines Blockes von Einträgen ist meist
ne Angelegenheit, die wenige Befehle pro Zyklus braucht, weil man
einfach byteweise oder wordweise oder dwordweise verschieben kann ohne
Rücksicht auf die interne Struktur der Elemente.
Also stapele deine Werte lieber gleich sortiert ein, das dürfte das
Beste sein - insbesondere dann, wenn dein X eine Gleitkommazahl ist.
Dann sehen nämlich alle Sortieralgorithmen eher alt aus, weil sie immer
auf der vollen Anzahl von Elementen herumsortieren müssen. Beim
sortierten Einstapeln hingegen hat man durchweg deutlich weniger
Vergleiche.
W.S.
W.S. schrieb:> Wohl nicht. Abgesehen davon, daß du nicht die Elemente bis zu dieser> Stelle, sondern die bereits gespeicherten Elemente ab dieser Stelle> verschieben mußt.>> Ich sehe auch keinen Vorteil darin, alles erstmal wild zu speichern und> dann einen Sortieralgo drauf loszulassen. Das ist nicht produktiver,> denn man muß in jedem Falle alle Elemente anfassen, und das gleich> zweimal: einmal alle beim einstapeln und dann nochmal alle beim> Sortieren (vergleichen und ggf. vertauschen).
Dann würde ich dir mal ein paar Versuche mit realen Programmen
empfehlen, ehe du hier aus dem Bauch heraus argumentierst.
Denn die gemessene Realität spricht gegen deine Argumentation.
Was du vorschlägst ist unter dem Namen 'Insertion Sort' bekannt. Lies
mal darüber nach.
https://de.wikipedia.org/wiki/Insertionsort
Eine doppelt verkettete Liste ist beim sortierten Einfügen nicht besser
als eine einfach verkettete Liste. Eine doppelt verkettete Liste ist nur
dann besser, wenn man von einem Element ausgehend in beide Richtungen
gehen will.
Man kann bei der Verkettung auch den Index an Stelle des Pointers
verwenden, wozu in diesem Fall ein Byte bereits ausreicht.
Ob aber hier Verkettung besser oder schlechter als ein normales Array
ist hängt von den übrigen Umständen ab. Ist die Zeit knapp? Ist der
Speicher knapp? Wird später indiziert darauf zugegriffen, oder nur
sequentiell?
A. K. schrieb:> Eine doppelt verkettete Liste ist nur> dann besser, wenn man von einem Element ausgehend in beide Richtungen> gehen will.
PS: Das bezieht sich auf den hier betrachteten Kontext, nicht auf Listen
allgemein.
