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
jaenicke hat folgendes geschrieben : |
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);
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:
- hast du viele indizierte Zugriffe (Suchen) und wenig Datenfluktuation, dann ist das Array besser, denn hier kann die Zugriffsadresse berechnet werden
- hast du wenig indizierte Zugriffe (man kann zu Referenzzwecken ja die Adresse eines Elementes hinterlegen, z.B. bei einem GUI-Control) und hohe Datenfluktuation, ist die lineare Liste besser, da hier die Daten nicht im Speicher bewegt werden müssen (und dafür gibt man schon gerne die 4 zusätzlichen Bytes aus ;))
cu
Narses
Lossy eX - Fr 11.09.09 16:05
Flamefire hat folgendes geschrieben : |
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!
Flamefire hat folgendes geschrieben : |
| 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)
Flamefire hat folgendes geschrieben : |
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
Flamefire hat folgendes geschrieben : |
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.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!