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.
oder man verwendet kein Array sondern eine Doppelt-Verkette-Liste. Da kann man mal schnell etwas einfügen, ohne die andere Daten zu verschieben.
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.
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.