Array-Delete Funktion

[olee]

Hi liebe DP'ler

Gibts ne Funktion, mit der man aus einem Array eines beliebigen Typs
Elemente löschen kann?

Also die das Array automatisch verkleinert und die Elemente entsprechend neu ordnet?

Wenn nein, ist sowas möglich?

If not lastQuestion.Possible then, wie gestaltet man am besten eine Funktion, um
aus einem bestimmten array ein Element zu löschen? :mrgreen:



MFG

[mkinzler]

Da würde ich eher eine Liste verwenden, da ist dies möglich. es wäre zwar möglich, dies auch für einen Array zu implemnetieren; der Aufwand ist es aber imho nicht wert.

[Nersgatt]

Moin,

wenn Du das Element n löschen willst, musst Du alle Elemente ab n+1 um eine Position runterschieben und am Schluss kannst Du mit SetLength die Größe des Arrays um 1 verringern. Je nach Größe des Array wird das aber recht langsam werden.
Besser ist es vielleicht, das Element n nicht wirklich zu löschen, sondern nur als "gelöscht" zu markieren. Deine Anwendung müsste dann gelöschte Elemente igonrieren.

Gruß,
Jens

[Medium]

Zitat:

Zitat von mkinzler

Da würde ich eher eine Liste verwenden

Das, und nichts anderes.

[DeddyH]

Aber dann TList. Eine verkettete Liste wäre zwar auch noch eine Option, ist aber um einiges aufwändiger.

[Neutral General]

Hi,

Naja an die Leute, die hier groß "TList" rufen:

Delphi-Quellcode:

// TList spezifische Dinge weggelassen
procedure TList.Delete(Index: Integer);
var
  Temp: Pointer;
begin
  if (Index < 0) or (Index >= FCount) then
    exit;

  Dec(FCount);
  if Index < FCount then
    System.Move(FList^[Index + 1], FList^[Index],(FCount - Index) * SizeOf(Pointer));
end;

TList ist ja im Prinzip auch nurn Array ;)

TList gibt allerdings reservierten Speicher nicht frei. Also kein SetLength.

PS: Aber handlicher ist TList mit Sicherheit trotzdem :mrgreen:

[DerDan]

Hallo,

Zitat:

Zitat von Nersgatt

Moin,

wenn Du das Element n löschen willst, musst Du alle Elemente ab n+1 um eine Position runterschieben und am Schluss kannst Du mit SetLength die Größe des Arrays um 1 verringern. Je nach Größe des Array wird das aber recht langsam werden.
Besser ist es vielleicht, das Element n nicht wirklich zu löschen, sondern nur als "gelöscht" zu markieren. Deine Anwendung müsste dann gelöschte Elemente igonrieren.

Gruß,
Jens

Das hab ich so auch mal so realisiert, die Elemente erstmal nur zu markieren, hat gut funktioniert.
Man kann ja von Zeit zu Zeit das Array wieder bereinigen.


Kommt halt immer drauf an, wie man auf die Daten zugreifen will.
Wenn man nicht unbedingt über einen Index zugreifen will, kann man auch über doppelt verkettet Listen nachdenken. Dort sind Einfüge und Löschen Operationen schnell möglich. allerdings kann man auf die Daten nur sequenziell zugreifen.

Mit den Listen vom Typ "TList" in der Unit Classes hat das nichts zu tun. Die funktionieren intern wieder mit den dynamischen Arrays. Da bei Änderungen immer noch eine virtuelle Notify Funktion aufgerufen wird, ist die Performance mit selbst verwalteten dynamischen Arrays besser.


mfg

DerDan

[olee]

Also mir war schon klar, dass man den Inhalt des Arrays neu kopieren muss.

Mir gings mehr um das WIE (Performance).

BTW: Ich hab ein Array mit Pointern also wirklich fast ne TList.

Der nachteil von TList ist eben nur, dass man ne klasse hat,
was ich nur sehr ungern haben will.

Ich hätte meine Frage genauer formuliert, musste aber in die Schule :evil: :wall: :dancer2:

EDIT:
System.Move(FList^[Index + 1], FList^[Index],(FCount - Index) * SizeOf(Pointer));
Was das macht ist mir noch nicht so klar :gruebel:


MFG

[mkinzler]

Zitat:

Der nachteil von TList ist eben nur, dass man ne klasse hat,
was ich nur sehr ungern haben will.

OOP würde ich eher als Vorteil ansehen

[olee]

da stimme ich dir zum Teil zu.

Doch das ist nicht immer der Fall.

Ein Beispiel: RECORDS!

Ohne TList könnte ich einfach neue Varieblen davon anlegen, ohne was machen zu müssen.
Mit ner klasse müsste ich nen "constructor" (im gewissen Sinne) basteln.

Hat denn jmd. nen Code-Vorschlag für mein Problem?

EDIT: !!! Korrektur: In meinem Array sind keine Pointer, aber sehr kleine Records,
die selten mehr als 5 werden.

[mkinzler]

Klassen sind ja mit Record sehr verwandt. Man könnte auch eine TObjectList verwenden

[olee]

Also um das mal klarzustellen:

Ich möchte keinesfalls eine Klasse verwenden!!

1.) Ich habe dieses Array sehr oft (Waypoints in ner Map also ca. 200 mal)
2.) Ich möchte nicht immer die TList / TObjectList neu erstellen.

--> mir gehts nur um die Performance eines Codes, um ein Element aus nem Array zu löschen. :wall:


MFG

[olee]

Mein bisheriger Code:

Delphi-Quellcode:

  // zum löschen von mehreren Elementen gleichzeitig
  j := 0;
  for i := 0 to high(AnArray) do
  begin
    AnArray[i-j] := AnArray[i];
    If AnArray[i].destroyed then inc(j);
  end;
  SetLength(AnArray,Length(AnArray)-j);

  // zum löschen eines Elementes
  for i := Index to high(AnArray)-1 do
  begin
    AnArray[i] := AnArray[i+1];
  end;
  SetLength(AnArray,Length(AnArray)-1);

Also ich hab da schon Code nur ist es möglich, eine Funktion zu schreiben,
die ein beliebiges Array annimmt?

(Vllt. mit dem Move-Befehl???)

[jfheins]

vll. mit sowas wie

Delphi-Quellcode:

procedure DeleteIndex(var arr: Array of const; index: Integer)

Aber ich glaube nicht, dass du das Array in der Prozedur verändern darfst ...

@Edit: Mit dem Movebefehl kannst du schnell viele arrayelemente verschieben, aber ich glaube, du darfst trotzdem nicht setlength aufrufen, um die länge anzupassen ;)

[olee]

Also das würde heißen ich bräuchte eine Funktion wie die hier?

Delphi-Quellcode:

procedure DeleteIndex(arr: Pointer; index: Integer; ItemSize: Cardinal);

und das Verschieben dann mit Move.

Aber wie müsste man dann wohl setLength manuell machen?

[Fridolin Walther]

Hm ... wenn das Array nicht sortiert ist (bzw. nicht sortiert sein muss) wäre die performanteste Lösung wahrscheinlich folgende:

Wenn der zu löschende Eintrag der letzte Eintrag ist, einfach den letzten Eintrag abschneiden. Wenn der zu löschende Eintrag nicht der letzte Eintrag ist, einfach den letzten Eintrag mit dem zu löschenden tauschen und den letzten Eintrag abschneiden.

[olee]

Oh man wie geil!

So simpel aber niemand kommt drauf ... außer dir :mrgreen:

Das ist ja ne perfekte Lösung.

Aber du hast recht. Das ist nur möglich, da ich nie den Index der Elemente
zum Identifizieren benutze.

[himitsu]

ich kann mir irgendwie nicht Helfen, aber ich bin mir sicher hier schon mehrmals Funktionen/Codes zum Einfügen/Löschen von von Einträgen gepostet zu haben :gruebel: ... nur finden ...

Move MoveMemory CopyMemory bringt nicht wirklich was
und nach [dp]*swap*[/dp] kann man ja leider nicht suchen :?

[Oreaden]

Zitat:

Zitat von olee

Gibts ne Funktion, mit der man aus einem Array eines beliebigen Typs
Elemente löschen kann?

Also die das Array automatisch verkleinert und die Elemente entsprechend neu ordnet?

Es gibt ein Objekt das dies leistet. TList und ihre Ableitungen. Diese sind alle Arrays welche zusätzlich die Verwaltungsfunktionen wie verkleinern, neu Ordnen, etc. implementiert haben.

Noch einen schönen Abend
Oreaden

[Medium]

Wenn du die maximale Größe des Arrays kennst, ist das Tauschen und seperate Mitführen des max-Indexes vermutlich wirklich die performanteste Lösung. Dann hast du eigentlich nur noch zwei Stolperfallen: Wenn es zu viele zu große Arrays sind, schlabberst du dir massig RAM weg das schlimmsten Falls zu einem winzigen Bruchteil tatsächlich verwendet wird, und versehentliche Aufrufe von SetLength könnten der Geschwindigkeit so richtig einen Dämpfer verpassen. Aber das "schlimmste" ist eigentlich, dass man sich die Performance durch potentiell gewaltigem Speicherverbrauch im Vergleich zur Nutzdatenmenge erkauft. Wenn die Arrays ohnehin meistens fast voll sind, ist das weniger tragisch. Schön oder elegant ist das halt aber nie. Nur performant :)

[himitsu]

Zitat:

Zitat von Medium

Aber das "schlimmste" ist eigentlich, dass man sich die Performance durch potentiell gewaltigem Speicherverbrauch im Vergleich zur Nutzdatenmenge erkauft.

Notfalls bastelt man sich dann einfach eine eigene "SetLength", welche die Arraygröße in größeren Schritten ändert.
> performanter und dennoch nicht all zuviel Overhead

[alzaimar]

Zitat:

Zitat von olee

Ich möchte keinesfalls eine Klasse verwenden!!

Das ist sehr dumm. Oder sagen wir es freundlicher: Kurzsichtig.

Zitat:

Zitat von olee

1.) Ich habe dieses Array sehr oft (Waypoints in ner Map also ca. 200 mal)

Das ist nicht oft.

Zitat:

Zitat von olee

2.) Ich möchte nicht immer die TList / TObjectList neu erstellen.

Warum nicht?

Zitat:

Zitat von olee

--> mir gehts nur um die Performance eines Codes, um ein Element aus nem Array zu löschen. :wall:

Nun ja, es kommt doch auch darauf an, was Du sonst noch alles mit deiner Liste anstellen willst. Irgendwie müssen die Daten ja auch rein. Und suchen willst Du vielleicht auch noch.

Das Löschen würde dann z.B. noch schneller gehen, wenn du das Array an der Stelle einfach mit 'nil' (bw. mit einem wie auch immer gearteten Platzhalter) belegst. Klar, iterieren, suchen, einfügen sind dann etwas langsamer, aber das *löschen* ist dann eigentlich optimal schnell.

Und lass das dumme 'Klassen sind langsam'. In erster Linie dürfte das dein Code bzw. die Algorithmen sein, die Du verwendest. Ich an deiner Stelle würde die von Dir zu optimierende Liste als Klasse implementieren und erstmal irgendwelche halbwegs performanten und vor allen Dingen robusten Methoden implementieren. Wenn dann dein ganzes Konstrukt stabil ist, kannst Duja immer noch die Liste gegen eine für deine Belange besser geeignetere eintauschen.

Wenn es nicht gerade um generische Verfahren geht, bei denen wirklich an der Basis rumgerechnet wird (Compiler, Scanner, Bildverarbeitungsalgorithmen, vielleicht auch ein Memorymanager wären solche Kandidaten), würde ich grundsätzlich einen OOP-Ansatz wählen und mir nur um die Algorithmen und deren Aufwand Gedanken machen, und nicht um Byte-Rumgeschubse auf unterster Ebene.

Wenn Du vielleicht dein 'Problem' bzw. das, was Du insgesamt vorhast, einmal näher erklären würdest, könnte man Dir vermutlich eine geeignete Listen-Klasse (Pfui!) vorschlagen, die die von Dir gewünschten Operationen sehr schnell implementiert.