Entwickler-Ecke

Delphi Language (Object-Pascal) / CLX - Element aus dyn. Array effektiv entfernen


Flamefire - Do 10.09.09 20:26
Titel: Element aus dyn. Array effektiv entfernen
Ich will ungültigeeinträge aus einem array effektiv entfernen. dazu habe ich mir folgendes gedacht:
Ich erstelle ein array "del" of boolean, in dem ich zu jedem eintrag speichere, ob er gelöscht werden soll oder nicht.
danach gehe mit nem zeiger von links nach rechts durch, und suche nach einem element links, dass gelöscht werden soll, und einem rechts, dass nicht gelöscht werden soll.
wenn gefunden und keine überschneidung, vertausche ich diese einträge
besser code:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
var i,j:Integer;
    del:Array of Boolean;
begin
  SetLength(del,Length(entries));
  for i:=0 to Length(entries)-1 do
    del[i]:=EntryGultig(entries[i]);
  i:=0;
  j:=Length(del)-1;
  while(i<j) do begin
    while(i<j) and (not del[i]) do Inc(i);
    while(i<j) and (del[j]) do Dec(j);
    if(i<j) then begin
      entries[i]:=entries[j];
      del[i]:=false;
      Inc(i);Dec(j);
    end;
  end;
  j:=Length(del);
  for i := 0 to Length(del) - 1 do
    if(del[i]) then begin
      j:=i;
      break;
    end;
  if(j<>Length(del)) then SetLength(entries,j);
  SetLength(del,0);


so weit so gut...
ich glaube zumindest, dass das ganz gut so funktionieren sollte
was ich gern hätte: die 2. schleife entfernen (die in der die endgültige länge des arrays ermittelt wird)
man müsste doch aus dem endstand von i,j auf die länge schließen können...aber iwie schaff ichs nicht
bei nem array, dass nur aus gültigen besteht, ist i,j die anzahl-1
wenn nicht, ist i,j die anzahl, die ich will...


BenBE - Do 10.09.09 21:00

Wenn die Reihenfolge der Einträge im Ziel-Array nicht wichtig ist, kann man das so machen:


Delphi-Quelltext
1:
2:
3:
4:
5:
procedure DelItem(var A: TDeinArray; index: Integer);
begin
    A[index] := A[high(A)];
    SetLength(A, High(A));
end;


Möchtest du ein gesamtes Array etwas aufräumen, kann man das etwas optimieren:


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
type TBooleanArray = array of Boolean;
procedure DelItemArray(var A: TDeinArray; D: TBooleanArray);
var
    I: Integer;
    N: Integer;
begin
    if Length(A) <> Length(D) then
        exit;

    I := 0;
    N := High(A);
    While I <= N do
    Begin
        If D[I] Then
        Begin
            While (N > I) and D[N] do
                Dec(N);

            If I < N then
                A[I] := A[N]
            else
                Break;

            Dec(N);
        end;

        Dec(I);
    end;

    SetLength(A, I + 1);
end;


Der Algo für die Schleife ist ungetestet ...


Flamefire - Do 10.09.09 21:28

deine schleife ist das was ich brauche.
nur funktioniert es nicht ganz.

bsp: (1=löschen;)
1001011

i=0;j=4-->tauschen
i=3;j=3-->Break
SetLength(...,3+1=4) -->1 zuviel...

ich glaube, ohne das +1 sollte es funktionieren...


jaenicke - Do 10.09.09 21:40

Es geht auch sehr gut ohne ein zusätzliches Array:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
function DeleteItems(var AItems: array of <Typ>): Integer;
var
  j: Integer;
begin
  Result := Low(AItems);
  j := High(AItems);
  while Result < j do
  begin
    while IsEntryValid(Result) and (Result < j) do
      Inc(Result);
    while not IsEntryValid(j) and (Result < j) do
      Dec(j);
    AItems[Result] := AItems[j];
    Dec(j);
    if Result <= j then
      Inc(Result);
  end;
end;
Da die Gültigkeit ohnehin nur einmal pro Eintrag geprüft wird, ist das zusätzliche Array unnötig. Die Anzahl der gültigen Einträge wird zurückgegeben.

// EDIT:
Unnötige Variable entfernt. Kleine Korrektur.


Gammatester - Fr 11.09.09 09:54

user profile iconjaenicke hat folgendes geschrieben Zum zitierten Posting springen:
Es geht auch sehr gut ohne ein zusätzliches Array:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
function DeleteItems(var AItems: array of <Typ>): Integer;
var
  j: Integer;
begin
  Result := Low(AItems);
  j := High(AItems);
  while Result < j do
  begin
    while IsEntryValid(Result) and (Result < j) do
      Inc(Result);
    while not IsEntryValid(j) and (Result < j) do
      Dec(j);
    AItems[Result] := AItems[j];
    Dec(j);
    if Result <= j then
      Inc(Result);
  end;
end;
Da die Gültigkeit ohnehin nur einmal pro Eintrag geprüft wird, ist das zusätzliche Array unnötig. Die Anzahl der gültigen Einträge wird zurückgegeben.

Das kann nicht allgemein richtig sein! Wenn zB Low(AItems) = High(AItems) ist wird gar nichts getestet und Result=0 zurückgeliefert.


Flamefire - Fr 11.09.09 11:42

doch würde gehn...ok fast...
wenn Low(AItems) = High(AItems) dann ist Result=Low(AItems)
er setz die länge dann auf low(aitems) und es fehlt einer...mist


Lossy eX - Fr 11.09.09 12:05

Muss es denn unbedingt ein Array sein? Bzw wozu ist es überhaupt?

Wenn du zum Beispiel nämlich nur eine Liste haben musst, dann kannst du das Ganze auch als verkettete Liste machen. Also ein Record mit einem Pointer auf den nächsten Eintrag. Um dann Einträge zu entfernen musst nur einmal durch die Liste und ungültige Einträge aus der Liste hängen. Also beim vorherigen Eintrag den Pointer auf das Nächste setzen. Das ausgehangene Element kann dann normal gelöscht werden und der Drops wäre gelutscht. Falls du die ausgehangen Elemente noch benötigst, dann könntest du aus denen eine zweite Liste machen. Dann gibt es keine umständliche Markierung zu löschender Einträge und es muss auch kein Element im Array hin und her verschoben weden.


Flamefire - Fr 11.09.09 13:51

das ist tatsächlich eine möglichkeit, das ganze als liste zu machen.
aber ich denke letztendlich hab ich dadurch mehr overhead als mit nem array

stell dir 1000 elemente vor
in nem array sind das 1000*sizeof(element)+16 Bytes
(die 16 ist der pointer auf das array sowie ein paar daten. ka obs 16 sind, aber so ungefähr)

in ner liste wäre es: 1000*(sizeof(element)+4) Bytes
-->4KB mehr, da ich immer nen pointer auf das nächste element mit brauche...


Narses - Fr 11.09.09 14:42

Moin!

Deine Rechnung kann ich nicht nachvollziehen, ob du die Pointer auf die Elemente in dem Element-Record unterbringst oder in einem Array, ist doch wohl schnuppe. :nixweiss:

cu
Narses


Flamefire - Fr 11.09.09 15:37

habe ich in dem array denn tatsächlich pointer?

ich dachte im speicher sieht das so aus:

mYArray=Array of record(X,Y:Integer);

Zitat:
X0|Y0|X1|Y1...


Narses - Fr 11.09.09 16:03

Moin!

Ah, du hast direkt das Array of record, hatte irgendwie eine TList-artige Struktur im Kopf... :gruebel: Dann ist das natürlich tatsächlich so, dass die unglaubliche Menge von 4 Bytes pro Eintrag dazu kämen. 8)

Sieht für mich nach dem klassichen Problem aus: Array oder lineare Liste. Was besser ist, entscheidet sich nach dem Anwendungszweck:cu
Narses


Lossy eX - Fr 11.09.09 16:05

user profile iconFlamefire hat folgendes geschrieben Zum zitierten Posting springen:
in ner liste wäre es: 1000*(sizeof(element)+4) Bytes
-->4KB mehr, da ich immer nen pointer auf das nächste element mit brauche...

4KB <> 4000 Bytes. Aber prinzipiell hast vollkommen recht. Zu den eigentlichen Nutzdaten kommt jeweils ein Pointer hinzu. In einem Array of record würden die Daten alle an einem Stück im Speicher liegen.

Um so kleiner die Nutzdaten sind um so größer der Overhead. Allerdings bei 1000 Einträgen ist der gesammte Speicherverbrauch doch wohl eher lächerlich. 12.000 Bytes im Vergleich zu 8.000 Bytes? Und da obliegt es dir als Entwickler ob du bereit bist ein wenig Speicher zu opfern und dadurch schneller, stabiler und kompfortabler arbeiten zu können oder ob wirklich jedes bisschen Speicher wichtig ist. Aber dann müsstest du eigentlich auch die VCL austauschen.

Anders siehsts natürlich aus, wenn du mehrere Millionen Einträge haben willst. Aber dann kann ich nur auf mein Post verweisen. "Muss es denn unbedingt ein Array sein? Bzw wozu ist es überhaupt?" Aber dann dürftest du mit Arrays auch so deine Probleme bekommen. Da solltst du dann genauer beschreiben was du machen willst etc.

PS: Genau genommen könnte es in der Kombination 2 Integer + Pointer sogar noch mehr Overhead geben. Denn der Speichermanager hat mehr kleine Pointer, die er auch irgendwo verwalten muss. Bzw. könnte der Speichermanager das auch auf 8 Bytes ausrichten. Damit würden effektiv noch mal 4 Bytes angehangen werden. Aber. Selbst dann sind die Speichermengen bei 1.000 - 10.000 Einträgen wohl kaum der Rede wert.


Flamefire - Fr 11.09.09 17:59

ok...4KB=4096Bytes...und?
war doch nur für die größenordnung ;-)

ich denke ich werd bei dem array erstmal bleiben...vorteil ist die schnellere speicherverwaltung mittels setlength
mit ner liste müsste ich die objecte immer einzeln erzeugen/löschen...
dadurch hätte ich jedesmal ein dispose/new


Narses - Fr 11.09.09 18:25

Moin!

user profile iconFlamefire hat folgendes geschrieben Zum zitierten Posting springen:
vorteil ist die schnellere speicherverwaltung mittels setlength
Das halte ich aber für ein Gerücht. Mach mal ein paar SetLength()-Calls, die das Array vergrößern... 8)

user profile iconFlamefire hat folgendes geschrieben Zum zitierten Posting springen:
mit ner liste müsste ich die objecte immer einzeln erzeugen/löschen...
dadurch hätte ich jedesmal ein dispose/new
Dann forderst du halt Blöcke an und verkettest trotzdem die Elemente über eine Pointer-Struktur. Aber auch einzelne New/Dispose-Aufrufe sind nicht schlimmer/langsamer als SetLength(), wenn die Gültigkeitsdauer vieler Elemente lang ist.

cu
Narses


Flamefire - Fr 11.09.09 18:43

ich meine: erstelle ein array:
setlength(x,1000);
...
setlength(x,reallength);

oder löschen:
//umsortieren
setlength(x,reallength);


Lossy eX - Fr 11.09.09 18:52

user profile iconFlamefire hat folgendes geschrieben Zum zitierten Posting springen:
ok...4KB=4096Bytes...und?
war doch nur für die größenordnung ;-)

Wollte nur eventuellen Boardspaltern den Wind aus den Segeln nehmen in dem ich selber Spalter spiele. ;)

Sonst kann ich Narses aber nur recht geben. SetLength bzw generell dynamische Arrays haben an sich schon einen größeren Overhead. Durch die Benutznung dynamischer Arrays wird auch ständig ein unsichtbares try finally erzeugt. Ich persönlich benutze dynamische Arrays mittlerweile eher nur noch recht selten.

Es kommt natürlich auch darauf an wie oft du Dinge rauschmeißt. Wenn du oft umsortieren musst, dann ist eine Liste deutlich schneller. Dadurch, dass du bei einem Array durch die Speicherkopiererei nicht erreichen kannst. Vor allem nicht, wenn du 2-3 mal durch das Array durch musst. 1 Mal durch das Array muss genügen. Ist aber wie gesagt deine Entscheidung. Wir können dir nur Vorschläge unterbreiten.