Array sortieren

[MrChipsy]

Zuviel Werbung?
-> Hier kostenlos registrieren

Hallo Community,
ich habe ein Array und möchte die Elemente, deren Inhalt Null ist, aufrücken. Die übrigen Elemente müssen nicht sortiert oder geordnet werden.

array[0] -> 0
array[1] -> 4
array[2] -> 2
array[3] -> 3
array[n] -> 0

wird zu

array[0] -> 4
array[1] -> 2
array[2] -> 3
array[3] -> 0
array[n] -> 0

Ich habe dies mit einer for Schleife gelöst.
Gibt es für solche Anwendungen Sortieralgorithmen? Meine Lösung kommt mir sehr langsam vor.

Vielen Dank

 

[PN/DP]

Hallo

FOR-Schleife klingt erst mal nicht verkehrt. Eine fertige Lösung für das Aufrücken/Konzentrieren der belegten Werte kenne ich nicht. Im Grunde muß die Schleife nur suchen, ob nach einem 0-Wert noch Wert(e) <> 0 kommen und diese ggf. aufrücken und am Ende die aufgerückten Elemente auf 0 löschen.

In welcher Programmiersprache für welches Gerät brauchst Du die Lösung?
Wie groß ist das Array (Anzahl Elemente)?
Wie langsam ist "gefühlt langsam"?
Wie häufig soll das "Aufrücken" ausgeführt werden?
Sind da statistisch mehr Inhalte = 0 oder mehr <> 0?
Wodurch entstehen die "Lücken" (die 0-Werte)?

Harald

 

[Larry Laffer]

Zuviel Werbung?
-> Hier kostenlos registrieren

Um beurteilen zu können ob man etwas optimieren kann müßte man deinen Code sehen.
Zum Sortieren würde ich den Bubblesort-Algorithmus nehmen - der ist natürlich bei sehr vielen Elementen nicht unbedingt eine Rakete.
Wieviele Elemente sortiertst du denn in welchem Zeitintervall (also wie oft) ?

Gruß
Larry

 

[PN/DP]

Im Grunde muß die Schleife nur suchen, ob nach einem 0-Wert noch Wert(e) <> 0 kommen und diese ggf. aufrücken und am Ende die aufgerückten Elemente auf 0 löschen.

Einfache Variante (in SCL/ST) mit ggf. auf sich selbst kopieren (kann effizienter sein als zusätzlich Kopier-Einsparungen (Index-Differenz) zu testen und Aufrückungen mitzuzählen. Ausführungszeit ist immer ungefähr gleich lang: jedes Array-Element wird einmal gelesen und einmal geschrieben):

a : ARRAY [0..imax] OF INT;
ir : UINT; //Read-Index
iw : UINT; //Write-Index


iw := 0;                //Schreib-Index auf erstes Element setzen

FOR ir := 0 TO imax DO  //jedes Array-Element einmal lesen
  IF a[ir] <> 0 THEN    //Element mit einem Wert belegt?
    a[iw] := a[ir];     //Element (um)kopieren
    iw := iw + 1;       //Schreib-Index auf nächstes Element
  END_IF;
END_FOR;

WHILE iw <= imax DO      //in Ausgabe-Array nicht belegte Elemente löschen
  a[iw] := 0;
  iw := iw + 1;
END_WHILE;

Je nach Compiler kann es effizienter sein, für den gelesenen Array-Wert eine Zwischenspeicher-Variable zu verwenden:

...
  v := a[ir];
  IF v <> 0 THEN
    a[iw] := v;         //Element (um)kopieren
...

Harald

 

[MrChipsy]

Nachfolgend mein Code:

[FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1] 
[/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff]    IF [/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]StartSorting [/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff]THEN[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][INDENT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]StartSorting [/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]:= FALSE;[/SIZE][/FONT][/SIZE][/FONT][/INDENT]
[FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]       xtmp[/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]:=[/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]0;

       [/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff]FOR [/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]xcnt[/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]:=[/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]0 [/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff]TO [/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]LAST_INDEX [/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff]DO[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]    
[/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff]         IF [/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]ArrayIn[xcnt] [/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]<> [/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]0 [/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff]THEN
[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]            ArrayTmp[xtmp][/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]:=[/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]ArrayIn[xcnt];
            xtmp[/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]:=[/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]xtmp+1;
         [/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff]END_IF

[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff]         IF [/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]xcnt [/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]= [/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]LAST_INDEX [/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff]THEN
[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]            ArrayIn[/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]:=[/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]ArrayOut[/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]:=[/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]ArrayTmp;
            brsmemset([/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff]ADR[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1](ArrayTmp),0,[/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff]SIZEOF[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1](ArrayTmp));
            xtmp:=[/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][FONT=Courier New][SIZE=1]0;
         [/SIZE][/FONT][/SIZE][/FONT][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff]END_IF
[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff]       END_FOR
[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff][FONT=Courier New][SIZE=1][COLOR=#0000ff]   END_IF[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT]

Ich sortiere bis zu 2000 Elemente. Geschwindigkeit ist relativ, mir erscheint es langsam.
Die Task, in der das Sortieren durchgeführt wird, werde ich aufräumen.

 

[PN/DP]

Zuviel Werbung?
-> Hier kostenlos registrieren

Oha, da ist in der Tat einiger zeitfressender Code am Ende der FOR-Schleife enthalten, und korrekt funktionieren tut der Code eigentlich auch nicht (hast Du zum hier posten noch Code weggekürzt?)

Wenn Du schon das ganze ArrayTmp mit 0 initialisierst, dann muß das VOR der FOR-Schleife passieren und nicht danach. Effizienter ist aber, nach der FOR-Schleife nur noch die nicht belegten Arrayelemente auf 0 zu löschen (von ArrayTmp[xtmp] bis ArrayTmp[LAST_INDEX]).
Warum sortierst Du nicht direkt das ArrayIn, sondern sortierst in ein ArrayTmp und kopierst das ArrayTmp dann zweimal (in das ArrayIn zurück und in ein zusätzliches ArrayOut)? Das ArrayTmp erscheint mir völlig unnötig. Du könntest auch von ArrayIn direkt nach ArrayOut sortieren.

Der ganze Code "IF xcnt = LAST_INDEX THEN ... END_IF" gehört hinter das END_FOR, und dort kann das IF dann auch entfallen. Das "xtmp:=0;" am Ende ist unnötig.

Probiere mal meinen Code aus #4, der eigentlich auch nichts anderes macht wie Dein Code, nur nicht so aufwändig.

Harald

 

[Jonny-Banana666]

Einfache Variante (in SCL/ST) mit ggf. auf sich selbst kopieren (kann effizienter sein als zusätzlich Kopier-Einsparungen (Index-Differenz) zu testen und Aufrückungen mitzuzählen. Ausführungszeit ist immer ungefähr gleich lang: jedes Array-Element wird einmal gelesen und einmal geschrieben):

a : ARRAY [0..imax] OF INT;
ir : UINT; //Read-Index
iw : UINT; //Write-Index


iw := 0;                //Schreib-Index auf erstes Element setzen

FOR ir := 0 TO imax DO  //jedes Array-Element einmal lesen
  IF a[ir] <> 0 THEN    //Element mit einem Wert belegt?
    a[iw] := a[ir];     //Element (um)kopieren
    iw := iw + 1;       //Schreib-Index auf nächstes Element
  END_IF;
END_FOR;

WHILE iw <= imax DO      //in Ausgabe-Array nicht belegte Elemente löschen
  a[iw] := 0;
  iw := iw + 1;
END_WHILE;

Harald

Hallo Harald, ich habe es selbst einmal ausprobiert weil ich darüber gestolpert bin...
Ich konnte nur mit dem iMax nix anfangen da bei mir die Boundprüfung hängt.
Aber kann ich so etwas nicht einfach so lösen? =>

PROGRAM PRG_TEST_1
VAR
    aAlt    :    ARRAY    [0..15000]    OF    INT;
    aNeu:    ARRAY    [0..15000]    OF    INT;
    iIndexAlt    :    INT;    (*Index aAlt *)
    iIndexNeu    :    INT;    (*Index aNeu *)
END_VAR


    FOR    iIndexAlt    := 0    TO    15001    DO
        IF    aAlt[iIndexAlt]    <>    0    THEN        (*Wenn Wert vorhanden*)
            aNeu[iIndexNeu]    :=    aAlt[iIndexAlt];    (*Wert in neues Array schreiben*)
            iIndexNeu    :=    iIndexNeu    +    1;    (*Index hochzaehlen*)
        END_IF
    END_FOR

    aAlt            :=    aNeu;                        (*Altes Array ueberschreiben*)
    iIndexNeu    :=    0;                            (*Index Neu zurueck setzen*)

Die 15000 sind nur irgend ein Wert...

 

[PN/DP]

Ich konnte nur mit dem iMax nix anfangen da bei mir die Boundprüfung hängt.

Was meinst Du mit "die Boundprüfung hängt"?

Überall da wo bei meinem Code "iMax" steht, muß der höchste Index des Arrays stehen (UBound). Entweder schreibt man da direkt den Wert hin oder deklariert eine Konstante oder fragt UBound des Arrays ab. Je nachdem was das Programmiersystem so hergibt.

VAR CONSTANT  //oder VAR_GLOBAL CONSTANT
  iMax : INT := 15000;
END_VAR

oder: iMax := 15000;

oder: iMax := UPPER_BOUND(a);

oder: iMax := SIZEOF(a) / SIZEOF(INT) - 1;

...

Aber kann ich so etwas nicht einfach so lösen?

Oft wenn Leute kommen um etwas "einfach" zu lösen, entsteht eine uneffiziente und/oder unvollständige Lösung
Dein Code ist uneffizient und unvollständig und hat Fehler:
- "FOR iIndexAlt := 0 TO 15001 DO" darf nur bis max 15000
- "aAlt := aNeu;" kopiert immer das komplette Array mit 15001 Elementen, auch wenn nur 3 Elemente belegt sind
- "iIndexNeu := 0;" gehört vor die FOR-Schleife
- die unbenutzten Elemente von aNeu werden nicht auf 0 initialisiert, und haben dann in aAlt irgendeinen Wert

Harald

 

[Jonny-Banana666]

Zuviel Werbung?
-> Hier kostenlos registrieren

Was meinst Du mit "die Boundprüfung hängt"?

Ich müsste diese Funktion erst prüfen da ich die noch nicht benutzt habe, aber das ist nur eine Fingeraufgabe.
Ich stimme Dir bei allem zu denn wenn ich so darüber nach denke ist es auch sehr offensichtlich. Vielen Dank für die Lektion

 

[vollmi]

Würds zyklusmässig nicht sinn machen, sich ne kleine funktion zu schreiben welche das erste 0 findet ggf wenn im paket noch das letzte 0 eben jenes und die anzahl zusammenhängender nullen. dieses dann löscht indem es einen ganzen block mit inhalt an diesen platz kopiert. Also möglichst ganze blöcke verschiebt. Also gar nicht erst einen Sortieralgoritmus dazu bemühen sondern nur find and destroy, den platz der dann frei wird mit fill 0 auffüllen. Das müsste doch wesentlich schneller gehen, als anzufangen element für element rauszuschieben.

 

[Heinileini]

Würds zyklusmässig nicht sinn machen, sich ne kleine funktion zu schreiben welche das erste 0 findet ggf wenn im paket noch das letzte 0 eben jenes und die anzahl zusammenhängender nullen. dieses dann löscht indem es einen ganzen block mit inhalt an diesen platz kopiert. Also möglichst ganze blöcke verschiebt. Also gar nicht erst einen Sortieralgoritmus dazu bemühen sondern nur find and destroy, den platz der dann frei wird mit fill 0 auffüllen. Das müsste doch wesentlich schneller gehen, als anzufangen element für element rauszuschieben.

Die Aufgabenstellung spricht zwar von sortieren, aber es sollen nur die Nullen nach hinten "geschoben" werden und alles andere nach vorn, ohne die Reihenfolge der Werte <> 0 zu ändern.
Eigentlich ist das nicht das, wofür es alle möglichen SortierAlgorithmen gibt. Da hast Du Recht, aber das hat auch niemand vorgeschlagen.
Aber die erste 0 finden und dann die letzte 0 eines zusammenhängenden 0-Bereichs und diese Nullen dann auch "löschen"!? Und dann dasselbe Spiel für nächsten 0-Bereich u.s.w..
Das klingt ja richtig kompliziert im Vergleich zu Haralds Lösung. Er hat schon Recht, das Einbauen von vermeintlichen "Abkürzungen" lohnt nicht, wenn das Aufspüren und Ausführen der "Abkürzungen" keinen Vorteil bringt.
Mit fill 0 auffüllen? Das ist dann doch eine weitere Funktion, die ein Array von Index a bis Index b löscht. Was gefällt Dir nicht an Haralds WhileSchleife, die den zusammenhängenden Bereich ab Index x bis zum letzten Element löscht?

 

[vollmi]

Zuviel Werbung?
-> Hier kostenlos registrieren

Das ist dann doch eine weitere Funktion, die ein Array von Index a bis Index b löscht. Was gefällt Dir nicht an Haralds WhileSchleife, die den zusammenhängenden Bereich ab Index x bis zum letzten Element löscht?

Haralds Schleife macht genau das was der User will. Das gefällt durchaus. Mein gedankengang war mehr, lässt sich das (Kompliziert mal dahingestellt) auf die Zykluszeit optimieren indem man mit Blockmove arbeitet statt zeile für zeile zu schieben.

 

[PN/DP]

lässt sich das (Kompliziert mal dahingestellt) auf die Zykluszeit optimieren indem man mit Blockmove arbeitet statt zeile für zeile zu schieben.

Es wird jedes belegte Element (Zeile) genau einmal umkopiert, da lohnt Ersatz durch ein Blockmove nur, wenn das Element ein Datensatz/Struct/Datentyp >> 4 Byte ist bzw. die Entscheidung kann man dem SCL/ST-Compiler überlassen, wie er "a[iw] := a[ir];" realisiert.
Falls das/die erste Element(e) (zusammenhängend) belegt sind, dann werden die auf sich selbst kopiert. Das könnte man noch optimieren, indem man nur kopiert, wenn der Schreibindex ungleich Leseindex ist (iw <> ir).

Am Ende das Löschen der nicht/nicht mehr belegten Elemente mit der While-Schleife könnte man bei großen Arrays durch ein Memset o.Ä. ersetzen (wenn die Speicheradressen berechnet werden können, also nicht "optimierter" Speicher), und ggf. nur ausführen wenn der Schreibindex ungleich Leseindex ist (iw <> ir).

Harald

 

[Heinileini]

Am Ende das Löschen der nicht/nicht mehr belegten Elemente mit der While-Schleife könnte man ... ggf. nur ausführen wenn der Schreibindex ungleich Leseindex ist (iw <> ir).

Moin Harald,
der LeseIndex läuft aber immer bis zum letzten Element. Wenn der SchreibIndex dann gleich dem LeseIndex ist, weil keine Nullen gefunden wurden, dann ist diese Abfrage überflüssig!
Die LöschSchleife wird dann ohnehin nicht durchlaufen.
Gruss, Heinileini

 

[PN/DP]

Zuviel Werbung?
-> Hier kostenlos registrieren

Moin Heinrich, Du hast recht, ganz so einfach ist es doch nicht.
Um das Löschen am Ende einzusparen müsste man sich merken, ob überhaupt mindestens ein Element umkopiert/verschoben wurde.
Noch besser: den Wert des LeseIndex merken, von dem (zuletzt) umkopiert wurde (was das letzte belegte Element war), dann braucht man nur den Bereich ab Schreibindex bis gemerkten Index löschen. (Oder hab ich da auch schon wieder einen Gedankenfehler?)

Harald

 

[Heinileini]

Um das Löschen am Ende einzusparen müsste man sich merken, ob überhaupt mindestens ein Element umkopiert/verschoben wurde.

Das muss man sich nicht extra merken. Man merkt es daran, dass der SchreibIndex hinter dem LeseIndex her bummelt.
So gesehen ist die Abfrage SchreibIndex <> LeseIndex sinnvoll. Aber, da der LeseIndex immer jedes einzelne Element abklappern muss, von Lbound bis Ubound, um eventuelle Nullen zu finden, wird die Abfrage erst stattfinden, wenn schon alle abgeklappert sind und dann ist schon zu spät, um noch auf Einsparungen zu hoffen. Der nicht nachhinkende SchreibIndex steht dann schon im "Jenseits" und die LöschSchleife wird sowieso nicht aktiviert.
Manchmal sieht man die Unmöglichkeit einer Abkürzung vor lauter Einfachheit einfach nicht ... das ist so, wie Du es beim Verarbeiten des Überlaufs eines EndlosZählers immer wieder "gepredigt" hast.

PS:
Man könnte sich den LeseIndex merken, auf dem zuletzt etwas ungleich Null gefunden wurde - dahinter muss nicht gelöscht werden, weil es schon gelöscht ist.

PS:
Oder
Wenn a[iw] = 0 UND a[ir] <>0 dann a[iw]:=a[ir]; a[ir]:=0;
Dann kann die abschliessende LöschRoutine ganz entfallen.

 

[PN/DP]

Oder
Wenn a[iw] = 0 UND a[ir] <>0 dann a[iw]:=a[ir]; a[ir]:=0;
Dann kann die abschliessende LöschRoutine ganz entfallen.

Da löscht man aber zu oft und beschreibt womöglich fast jedes Element zweimal, wenn man beim Verschieben eines Elementes sofort das Quell-Element löscht, ohne zu wissen ob es danach nicht sowieso nochmal überschrieben wird. Beispiel: nur das erste Element ist 0, dann müssen alle Elemente aufrücken und man muß nur das letzte Element löschen.

Man könnte sich den LeseIndex merken, auf dem zuletzt etwas ungleich Null gefunden wurde - dahinter muss nicht gelöscht werden, weil es schon gelöscht ist

Noch besser: den Wert des LeseIndex merken, von dem (zuletzt) umkopiert wurde (was das letzte belegte Element war), dann braucht man nur den Bereich ab Schreibindex bis gemerkten Index löschen. (Oder hab ich da auch schon wieder einen Gedankenfehler?)

Unsere letzten Ideen meinen das Gleiche und sind der Schlüssel für Reduzierung der Löschvorgänge auf das unbedingt nötige.
Wenn man direkt im Quell-Array umkopiert/aufrückt, hier eine verbesserte Lösung, die nur kopiert und löscht wo nötig (ungetestet):

a : ARRAY [0..imax] OF INT;
ir : UINT; //Read-Index
iw : UINT; //Write-Index
ix : UINT; //Index letztes frei gewordenes Element


ix := 0;                //Merk-Index initialisieren
iw := 0;                //Schreib-Index auf erstes Element setzen

FOR ir := 0 TO imax DO  //jedes Array-Element einmal lesen
  IF a[ir] <> 0 THEN    //Element mit einem Wert belegt?
    IF iw <> ir THEN    //nicht auf sich selber kopieren
      a[iw] := a[ir];   //Element umkopieren
      ix := ir;         //Quell-Index des umkopierten Elements merken
    END_IF;
    iw := iw + 1;       //Schreib-Index auf nächstes Element
  END_IF;
END_FOR;

WHILE iw <= ix DO       //frei gewordene Elemente löschen
  a[iw] := 0;
  iw := iw + 1;
END_WHILE;

Die Lösung hat (vermutlich) nur noch einen "Schönheitsfehler", daß bei einem leeren Array (alle Elemente sind 0) ganz zum Schluß unnötigerweise das Element a[0] gelöscht wird (nochmal 0 hineingeschrieben wird).
Das könnte man verhindern, indem man ix := -1; initialisiert, was aber nicht geht wenn die Index-Variablen UINT sind.
PS: Lösung: die WHILE-Schleife nur ausführen, wenn iw <> 0 ist.

Harald

 

[Heinileini]

Zuviel Werbung?
-> Hier kostenlos registrieren

Ja Harald, Deinem letzten Code ist doch nichts mehr hinzuzufügen! Wenn nur ein einziges Element unnötigerweise gelöscht wird, lohnt doch kein zusätzlicher Aufwand, um diesen Fall auch noch einzusparen!
Wenn man schon mit Arrays zu tun hat, die mehr als 2^15 Elemente haben (Index UINT oder DINT), dann lauert das wahre Problem (ZyklusBelastung) nicht darin, die Löschung eines einzigen Elements zu viel auszuführen!

Meine 'PS' aus #16 ziehe ich hiermit zurück.
Der erste gefällt mir zwar, aber den hattest Du schon vorher geäussert (ich hab's erst zu spät wahrgenommen) und der zweite gefällt mir nach wie vor nicht wirklich.

 

[PN/DP]

Wenn nur ein einziges Element unnötigerweise gelöscht wird, lohnt doch kein zusätzlicher Aufwand, um diesen Fall auch noch einzusparen!

Der zusätzliche Aufwand ist nur ein zusätzliches einmaliges IF..THEN vor der WHILE-Schleife. So, hier nun meine letzte Version:

a : ARRAY [0..imax] OF INT;
ir : UINT; //Read-Index
iw : UINT; //Write-Index
ix : UINT; //Index letztes frei gewordenes Element


ix := 0;                //Merk-Index initialisieren
iw := 0;                //Schreib-Index auf erstes Element setzen

FOR ir := 0 TO imax DO  //jedes Array-Element einmal lesen
  IF a[ir] <> 0 THEN    //Element mit einem Wert belegt?
    IF iw <> ir THEN    //nicht auf sich selber kopieren
      a[iw] := a[ir];   //Element umkopieren
      ix := ir;         //Quell-Index des umkopierten Elements merken
    END_IF;
    iw := iw + 1;       //Schreib-Index auf nächstes Element
  END_IF;
END_FOR;

IF iw <> 0 THEN         //wenn mindestens 1 Element umkopiert wurde
  WHILE iw <= ix DO     //frei gewordene Elemente löschen
    a[iw] := 0;
    iw := iw + 1;
  END_WHILE;
END_IF;

Ich denke, mehr lässt sich nicht mehr sinnvoll optimieren, wenn der Code mit beliebigen Verteilungen der belegten und leeren Elemente klarkommen soll. Nur bei speziellen Aufgaben lässt sich noch etwas optimieren.
Wenn wie hier die Array-Elemente nur INT sind und nicht ein größerer Datensatz, dann kann es sogar sein, daß Deine letzte Idee von #16 gleichwertig oder effizienter als die abschließende LöschRoutine ist (also das Quell-Element einer Verschiebung sofort mit 0 beschreiben anstatt sich den Index dieses Elementes zu merken).
Wenn die Aufgabenstellung ist, daß bei jedem Aufruf nur maximal eine Lücke aufgerückt werden soll, dann könnte man das Aufrücken mit einem Memcopy/Blockmove machen, falls der Speicher eine solche Adressierung zulässt.

Harald

 

[hucki]

Ich denke, mehr lässt sich nicht mehr sinnvoll optimieren, wenn der Code mit beliebigen Verteilungen der belegten und leeren Elemente klarkommen soll.

Wenn die Reihenfolge der Elemente egal ist, dann durch Weglassen der FOR-Schleife:

a : ARRAY * OF INT;                          // Sortier-Array
ip : DINT;                                   // Prüf-Index
il : DINT;                                   // Letzter-Index


#ip := LOWER_BOUND (ARR := #a, DIM := 1);     // Erstes  Array-Element ermitteln
#il := UPPER_BOUND (ARR := #a, DIM := 1);     // Letztes Array-Element ermitteln


WHILE #ip < #il DO                            // bis zum vorletzten (ungelöschten) Element prüfen
    IF #a[#ip] = 0 THEN                       //   Prüf-Element unbelegt?
        #a[#ip] := #a[#il];                   //      letztes Element umkopieren
        #a[#il] := 0;                         //      letztes Element nullen
        #il -= 1;                             //      Letzter-Index dekrementieren
    ELSE                                      //   Element belegt   
        #ip += 1;                             //      Prüf-Index inkrementieren
    END_IF;
END_WHILE;;

PS:
bzw. falls man nicht unnötig Nullen umkopieren möchte:

WHILE #ip < #il DO                            // bis zum vorletzten (ungelöschten) Element prüfen
    WHILE #a[#il] = 0 AND #ip < #il DO        //   Letztes Element leer?
        #il -= 1;                             //      Letzter-Index dekrementieren
    END_WHILE;
    IF #a[#ip] <> 0 THEN                      //   Prüf-Element belegt?
        #ip += 1;                             //      Prüf-Index inkrementieren
    ELSE                                      //    Prüf-Element unbelegt
        #a[#ip] := #a[#il];                   //      letztes Element umkopieren
        #a[#il] := 0;                         //      letztes Element nullen
    END_IF;
END_WHILE;