Array und duplikate

[delphinia]

Hallo

wie finde ich und was ist der effektivste Weg Duplicate in einem Array zu finden und in ein anderes Array zu schieben?

Edit: ich möchte NICHT das doppelte Array ausortieren sondern BEIDE doppelten oder mehrfachvorhandene nur verschieben

[mkinzler]

Vor dem Einfügen mit .IndexOf überprüfen.

[Dani]

Wenn ich dich richtig interpretiere, meinst du mit effektiv eigentlich effizient, also müssen wir die Zeit und Speicherkosten berücksichtigen. Wie sieht dein Array denn aus? Was mir jetzt auf die Schnelle einfällt wäre:

1. Die Reihenfolge der Elemente in der Liste darf nicht verändert werden.
-> 1.a Alle Elemente paarweise miteinander vergleichen und Duplikate markieren (Zwei verschachtelte for-Schleifen). Aufwand für das Finden der Duplikate = O(1) bzw. O(n) Speicherverbrauch, O(n²) Zeitaufwand.
-> 1.b Alle Elemente in eine zweite Liste kopieren und diese Liste wie in 2. verarbeiten: Aufwand für das Finden der Duplikate = O(n) Speicherverbrauch, O(n * log(n)) Zeitaufwand.

2. Die Reihenfolge der Elemente in der Liste darf verändert werden.
-> 2.a Die Liste sortieren (z.B. mit Heapsort oder Quicksort), danach stehen alle Duplikate hintereinander. Aufwand für das Finden der Duplikate = O(1) Speicherverbrauch, O(n * log(n)) Zeitaufwand.

3. Die Liste ist bereits zu jedem Zeitpunkt sortiert.
-> 3.a Alle Duplikate stehen bereits hintereinander.

4. ???

Nachdem jetzt alle Duplikate entweder markiert sind oder direkt hintereinander stehen, kannst du das Array von vorne nach hinten durchlaufen und die Elemente, die doppelt oder mehrfach vorkommen, in eine andere Liste verschieben. (Frage: verschieben von A nach B = Element aus Liste A löschen und in Liste B einfügen?)

Jetzt bleibt nur noch das Problem, dass man aus einer Arraybasierten Liste nicht effizient löschen/verschieben kann, da jede Löschaktion O(n) Zeit in Anspruch nimmt.

Ich häng mal noch diesen völlig ungetesteten Code an, vielleicht hilft der irgendwie (und wenns nur als Beispiel dient, wie man's nicht machen sollte ^^)

Gruß Dani

[delphinia]

Hier mehr Infos:


Mein Array

Delphi-Quellcode:

type
  TDi= packed record
    S1: string;
    p1: integer;
  end;

  tdia= array of TDi;

in diesem können Strings auch mehrmals vorkommen.

[DaHui]

ganz einfach könntest du ausschliessen ob überhaupt Doppelte sachen drin vorkommen indem du (falls bekannt) die Anzahl der Stellen (oder wie das heisst in dem Array) des Arrays die der Array hat und die er haben sollte (maximal ohne Duplikate) vbergleichst und dem Programm dann in ner If Else Funktion sagst das wenn gleich gross ist ist alles ok (vorraus dein reinschreiben in den Array war lückenfrei) und dann weiter machst wie oben schon beschrieben mit Sortieren und dann stehen die ja eh hintereinandern und musst die nur noch durchgehen.

wäre meine spontane idee

[Dani]

Du hast es oft leichter, wenn du auf Relikte wie dynamische Arrays und Records verzichtest.

Delphi-Quellcode:

program Project2;

{$APPTYPE CONSOLE}

uses SysUtils, Classes;

type
  TDi = class(TObject)
  private
    FP1: Integer;
    FS1: String;
  public
    constructor Create(S1: String; P1: Integer);
    property S1: String read FS1 write FS1;
    property P1: Integer read FP1 write FP1;
  end;

  TDiArray = class(TList)
  public
    procedure Print;
    function ExtractDuplicates: TDiArray;
  end;

procedure TDiArray.Print;
var I: Integer;
    Item: TDi;
begin
  for I := 0 to Count - 1 do begin
    if (Items[I] <> nil) then begin
      Item := TDi(Items[I]);
      WriteLn(Item.S1  + ' = ' + IntToStr(Item.P1));
    end;
  end;
end;

(************************************
 * Annahme: DiArray ist unsortiert. *
 * Entspricht im Wesentlichen einem *
 * Bubblesort.                      *
 ************************************)
function TDiArray.ExtractDuplicates: TDiArray;
var I,J: Integer;
begin
  Result := TDiArray.Create;
  for I := 0 to Count - 1 do begin
    if (Items[I] <> nil) then
      for J := I + 1 to Count - 1 do begin
        if (Items[J] <> nil) and
           (TDi(Items[I]).S1 = TDi(Items[J]).S1) then begin
          Result.Add(Items[J]);
          Items[J] := nil;
        end;
      end;
  end;
  //Pack() aufrufen, wenn die "nil"-Löcher entfernt werden sollen.
end;

{ TDi }

constructor TDi.Create(S1: String; P1: Integer);
begin
  inherited Create;
  Self.S1 := S1;
  Self.P1 := P1;
end;

procedure Foo;
var
  Arr, Duplicates: TDiArray;
begin
  Arr := TDiArray.Create;
  Arr.Add(TDi.Create('a', 1));
  Arr.Add(TDi.Create('b', 2));
  Arr.Add(TDi.Create('b', 3));
  Arr.Add(TDi.Create('a', 4));
  Arr.Add(TDi.Create('c', 5));
  Arr.Add(TDi.Create('a', 6));
  Arr.Add(TDi.Create('b', 7));
  Arr.Add(TDi.Create('c', 8));
  Arr.Add(TDi.Create('c', 9));
  Arr.Add(TDi.Create('a', 10));
  Duplicates := Arr.ExtractDuplicates;

  WriteLn('Arr:');
  Arr.Print;
  WriteLn('Duplikate:');
  Duplicates.Print;
  ReadLn;
end;


begin
  Foo;
end.