Autor Beitrag
Flamefire
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1207
Erhaltene Danke: 31

Win 10
Delphi 2009 Pro, C++ (Visual Studio)
BeitragVerfasst: Do 10.09.09 20:26 
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:
ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: Do 10.09.09 21:00 
Wenn die Reihenfolge der Einträge im Ziel-Array nicht wichtig ist, kann man das so machen:

ausblenden 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:

ausblenden volle Höhe 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 ...

_________________
Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
Flamefire Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1207
Erhaltene Danke: 31

Win 10
Delphi 2009 Pro, C++ (Visual Studio)
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 19346
Erhaltene Danke: 1754

W11 x64 (Chrome, Edge)
Delphi 12 Pro, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
BeitragVerfasst: Do 10.09.09 21:40 
Es geht auch sehr gut ohne ein zusätzliches Array:
ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 328
Erhaltene Danke: 101



BeitragVerfasst: 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:
ausblenden 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1207
Erhaltene Danke: 31

Win 10
Delphi 2009 Pro, C++ (Visual Studio)
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1048
Erhaltene Danke: 4



BeitragVerfasst: 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.

_________________
Nur die Menschheit ist arrogant genug, um zu glauben sie sei die einzige intelligente Lebensform im All. Wo nicht mal das nachhaltig bewiesen wurde.
Flamefire Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1207
Erhaltene Danke: 31

Win 10
Delphi 2009 Pro, C++ (Visual Studio)
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Administrator
Beiträge: 10185
Erhaltene Danke: 1261

W11x64
TP3 .. D7pro .. D10.2CE
BeitragVerfasst: 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

_________________
There are 10 types of people - those who understand binary and those who don´t.
Flamefire Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1207
Erhaltene Danke: 31

Win 10
Delphi 2009 Pro, C++ (Visual Studio)
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Administrator
Beiträge: 10185
Erhaltene Danke: 1261

W11x64
TP3 .. D7pro .. D10.2CE
BeitragVerfasst: 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

_________________
There are 10 types of people - those who understand binary and those who don´t.
Lossy eX
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1048
Erhaltene Danke: 4



BeitragVerfasst: 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.

_________________
Nur die Menschheit ist arrogant genug, um zu glauben sie sei die einzige intelligente Lebensform im All. Wo nicht mal das nachhaltig bewiesen wurde.
Flamefire Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1207
Erhaltene Danke: 31

Win 10
Delphi 2009 Pro, C++ (Visual Studio)
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Administrator
Beiträge: 10185
Erhaltene Danke: 1261

W11x64
TP3 .. D7pro .. D10.2CE
BeitragVerfasst: 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

_________________
There are 10 types of people - those who understand binary and those who don´t.
Flamefire Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1207
Erhaltene Danke: 31

Win 10
Delphi 2009 Pro, C++ (Visual Studio)
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1048
Erhaltene Danke: 4



BeitragVerfasst: 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.

_________________
Nur die Menschheit ist arrogant genug, um zu glauben sie sei die einzige intelligente Lebensform im All. Wo nicht mal das nachhaltig bewiesen wurde.