Doppelte Einträge in Array finden

[BungeeBug]

Hi,

ich suche eine schnelle Möglichkeitkeit die Einträge in einem sehr Großen Array zuvergleichen.
Am Ende soll kein doppelter Eintrag mehr vorhanden sein. Hat da jmd. ein Stück Code oder kann man sowas schnell schreiben? Ich scheiter im mom immer daran das der erste gleiche Eintrag gefunden wird die darauf folegenden nicht mehr. Ich glaube das es an der Schleife liegt die ich dazu verwende. Ich find aber den Fehler nich ... mag an der grausamen Erkältung liegen ... wenns mir gleich einer zeigt hau ich mir wieder vor den Kopf.

Achso mit sehr groß mein ich 6000 - 7000 Einträge ...

[Luckie]

Was hälts du von der Idee mal deinen Code zu posten? :roll:

[BungeeBug]

Delphi-Quellcode:

// Gleiche Datein suchen
     FOR i := 0 TO High(MyHashArray) DO
      BEGIN
       j := 0;
       WHILE j <= High(MyHashArray) DO
        BEGIN
          // Sind die Eintrage die selben?
          IF i <> j THEN
           BEGIN
            IF MD5DigestCompare(MyHashArray[i],MyHashArray[j]) THEN // Vergleichen
             BEGIN
              Form1.CheckListBox1.Items.Add(Form1.ListBox1.Items[j]);
              // Doppelten Hashentfernen
               FOR k := j TO High(MyHashArray) DO // Folgende doppelte Einträge entfernen
                BEGIN
                 MyHashArray[k] := MyHashArray[k+1];
                END;
              // SetLength(MyHashArray,High(MyHashArray)-1); // <- E/A Fehler
              j := 0;
             END;
           END;
         inc(j);
        END;
       END;

Ich hab aber nich wirklich den Durchblick ... da kann auch sonst der ein oder ander Fehler drin sein.

[Matze]

Das da ein E/A Fehlöer kommt ist eigentlich logisch, da das Array ja eine bestimmte Länge hat, dessen Felder alle ausgefüllt sind.

[himitsu]

Und wie sieht es damit aus?

Delphi-Quellcode:

Var A: Array of irgendwas;
  I, I2, I3: Integer;

For I := High(A) - 1 downto 0 do
  For I2 := High(A) downto I + 1 do
    If A[I] = A[I2] Then Begin
      For I3 := I2 to High(A) - 1 do
        A[I3] := A[I3 + 1];
      SetLength(A, High(A));
    End;

Um das Array um einen Eintag zu kürzen:

Delphi-Quellcode:

SetLength(MyHashArray, High(MyHashArray));

Wenn bei dir nur noch ein Eintrag im Array ist:

Delphi-Quellcode:

SetLength(MyHashArray, High(MyHashArray) - 1);

{High(MyHashArray) = 0}
SetLength(MyHashArray, High(MyHashArray) - 1);
SetLength(MyHashArray, 0 - 1);
SetLength(MyHashArray, -1);

und -1 ist nicht möglich, also kommt ein Fehler...

[BungeeBug]

Zitat:

Zitat von Matze

Das da ein E/A Fehlöer kommt ist eigentlich logisch, da das Array ja eine bestimmte Länge hat, dessen Felder alle ausgefüllt sind.

Wird wenn ich SetLength(); benutze das ganze Array überschrieben?

[himitsu]

nein

wenn du eine kleinere Größe angibst, als drin ist, dann werden die Letzten (x = alte Anzahl - neue Anzahl) Einträge gelöscht.

wenn du eine größere Größe angibst, als drin ist, dann werden x neue Eintgäge angehängt (x = neue Anzahl - alte Anzahl).

[edit]Nachtag im vorherigen Post]

[SirThornberry]

nein, werden nicht alle felder überschrieben bei setlength

[BungeeBug]

HI all,

ich hab den Code nun an meinen Angepasst nur funktioniert dieser leider nicht so wie wer soll.
Es werden von 5 Einträgen 3 als doppelt angezeigt, welche aber garnicht doppelt sein können.
Desweitergen bin ich fast sicher das der Code garnicht alle Einträge durchgeht da z.B.:

Code:

For I := High(A) - 1 downto 0 do

Den letzten Index einfach auslässt.

[Pseudemys Nelsoni]

machmal:

Delphi-Quellcode:

For I := High(A) downto 0 do

statt

Delphi-Quellcode:

For I := High(A) - 1 downto 0 do

[BungeeBug]

Hab ich schon , was aber keine Verbesserung bringt. Son bisschen Delphi kann ich ja auch :)

Also irgendwas ist da ganz gehörig flasch ... nur blick ich im mom nicht durch was ...

[Minz]

Ist doch vom Prinzip nicht schwierig:

Delphi-Quellcode:

for i:=low(Array) to high(array)-1 do begin
    for i2:=i+1 to high(array) do begin
        if Array[i]=Array[i2] then entferneEintrag; 
        //Achtung! die Länge des Arrays ist jetzt anders
        //müsste man prüfen, ob das irgendwo zum tragen kommt
        //hiermit findet man allerdings nur doppelte Einträge, nicht jedoch
        //dreifache oder nochmehrfache gleiche Einträge s.u.
    end;
end;

für mehr als doppeltfache gleich Einträge: (z.B. Array[1], [5] und [10] sind gleich)

Delphi-Quellcode:

for i:=low(Array) to high(array)-1 do begin
    for i2:=low(Array) to high(array) do begin
        if not (i=i2) then
           if Array[i]=Array[i2] then entferneEintrag; 
    end;
end;

[Minz]

Alternative wäre noch, dein Array nach einem schnellen
Sortieralgorithmus zu sortieren, so das du nur einmal durchlaufen musst und immer nur die benachbarten Elemente vergleichst.

Siehe Bubble-, Quick-, ...sort

[Pseudemys Nelsoni]

Zitat:

for i:=low(Array) to high(array)-1

wieso -1?

so wird das letzte item nie erreicht

eher:

Delphi-Quellcode:

for i:= low(Array) to high(array)

:thuimb:

[BungeeBug]

So langsam bekomm ich das Gefühl das das Problem woanders liegt als am sortiern. Es scheint egal was ich mache, es werden immer doppelte Datein (die es nicht gibt) öffter angezeigt als eigendlich Möglich.

[Neg]

Na, dann teste doch einfach die einzelnen Abschnitte deines Codes, ob sie so arbeiten wie sie sollen. :gruebel:

Eine Alternative zum Finden von doppelten Einträgen wäre noch die Einführung eines temporären Arrays. Diese Variante finde ich in sofern "schöner" als dass man sich dabei nicht in so vielen verschachtelten For-Schleifen verliert.

Delphi-Quellcode:

function IsInArray(Element: DeinTyp; ElementArray: Array of DeinTyp): boolean;
var i: integer;
begin
  for i:=0 to length(ElementArray)-1 do
  begin
    if DeineEqualsFunktion(Element, ElementArray[i]) then
    begin
      Result:=true;
      exit;
    end;
  end;

  Result:=false;
end;

procedure DeleteDoubleElements(var ElementArray: Array of DeinTyp);
var
i, iActualLength, iIndex: integer;
tmp: Array of DeinTyp;
begin
  iIndex:=0;
  iActualLength:=0;

  // Temp-Array initialisieren
  SetLength(tmp, Length(ElementArray));
  for i:=0 to length(tmp)-1 do
  begin
    tmp[i]:=[i]DeinInitialwert[/i];
  end;

  // Elemente nur einmalig nach tmp kopieren
  for i:=0 to length(ElementArray)-1 do
  begin
    if not IsInArray(ElementArray[i], tmp) then
    begin
      tmp[iIndex]:=ElementArray[i];
      inc(iIndex);
      inc(iActualLength);
    end;
  end;

  // Temp-Array nach ElementArray zurück kopieren
  SetLength(ElementArray, iActualLength);
  for i:=0 to iActualLength-1 do
  begin
    ElementArray[i]:=tmp[i];
  end;
end;

[Minz]

@Pseudemys

es muss -1 sein

weil die innere Schleife das letzte Element überpüft, während die äußere Schleife dabei auf dem vorletzten steht.

es wird dann das vorletzte u.a. mit dem letzten verglichen.

[BungeeBug]

Hi,

es geht ja darum das jedes Element mit jedem Verglichen wird. Egal ob es das erste oder das letzte ist.

[Minz]

Bungee für wen war das jetzt bestimmt?