Arrays doppelte einträge eliminieren

[qwertz543221]

hallo

habe wie folgt versucht, ein array aus randomzahlen (oder vordefiniert) so zu bearbeiten, dass in der ausgabe nur noch jede vorkommende zahl nur noch einmal auftaucht. (... wunschvorstellung)

leider ist es mir nicht gelungen, alle überflüssiigen zu entfernen.
meine idee war folgende:
1 - (aufsteigendes) sortieren des arrays
2 - danach von vorn bis hinten mit einem zähler durchlaufen und schauen, ob einträge doppelt sind
3 - diese einträge dann nach hinten verschieben (damit sich die größe nicht ändert, dachte ich, man könnte einfach diese mit den letzten einträgen tauschen)
dabei wird die anzahl der vertauschungen mitgezählt
4 - so viele einträge hinten abschneiden (setlength), wie der zähler angibt
5 - da das array jetzz wieder unsortiert ist, noch einmal sortieren.


soviel zur idee, bei der ausführung hakt es jedoch, weiß jedoch nicht woran....


qt siehe unten

Delphi-Quellcode:

var i,j,x:longint;

begin

i:=0;
j:=-1;
i:=0;

quicksort(test1,low(test1),high(test1));

while i< = length(test1) do
begin
if test1[i] = test1[i+1] //doppelt?
  then
    begin
    {ans ende stellen durch tauschen}
    x:=test1[i];
    test1[i]:=test1[length(test1)-1]; //möglicherweise ist hier ein fehler???
    test1[length(test1)-1]:=x;
    j:=j+1;
    end;
i:=i+1;
end;

setlength(test1,length(test1)-j);
quicksort(test1,low(test1),high(test1));
write(test1); //ausgabe
end;

vielen dank für eure tips

[alzaimar]

Delphi-Quellcode:

j := 0;
i := 1;
while i < Length (MyArray) - 1 do begin
  if MyArray[i] <> MyArray[j] then begin 
    MyArray[j] := MyArray[i];
    inc(j);
    SetLength (MyArray, Length (MyArray) - 1);
  end;
  inc(i);
end;

Getippt und nicht getestet.

[Corpsman]

Also ich bin ja der meineung das dein 2. Sortieren nicht notwendig ist.

Denn du entfernst aus einem Sortierten Array alle Doppelten, wo soll da Unordnung entstehen ?


Probier mal das hier, ..

Delphi-Quellcode:

  quicksort_Array;
  // entfernen doppelte, dreifache ..
  for i :=high(MyArray) downto 1 do begin
    if MyArray[i-1] = MyArray[i] then begin
      for j := i to High(Myarray)-1 do begin
      myArray[j] := myArray[j+1]; 
      end;
      setlength(Myarray, high(myarray));
    end;
  end;

habs aber nicht getestet ,)

[alzaimar]

Corpsman, deine Lösung ist vom Aufwand O(n^2), meine nur O(n).

[himitsu]

Falls nicht sortiert werden soll/muß

Delphi-Quellcode:

j := 0;
for i := 0 to High(MyArray) do begin
  k := High(MyArray);
  while k > i do 
    if MyArray[i] = MyArray[k] then break else Dec(k);
  if k <> i then Continue;
  MyArray[j] := MyArray[k];
  Inc(j);
end;
SetLength(MyArray, j);

Insgesamt isses eh etwas besser, wenn man nicht ständig das Array (Länge/Speicherverwaltung) ändert.


[add]
meines ist dann wohl irgendwas zwischen O(n^2) und O(n), aber dafür entfällt das vorhergehende Sortieren, welches auch irgendwas über O(n) ist

meines: O(n)..O(n^2)
alzaimar: O(n) + O(n)..O(n^2)
Corpsman: O(n^2) + O(n)..O(n^2)

(die Zeit für eure vielen SetLength hab ich ignoriert)

[alzaimar]

Das ist -mit Verlaub- falsch.

Mein Algorithmus ist O(n) und nicht O(n^2). Auch nicht irgendwas dazwischen. Wir haben eine einfache Schleife über alle Arrayelemente.
Dein Algorithmus ist O(n^2), da es sich um zwei verschachtelte Schleifen mit einer Schleifenlänge proportional N (Anzahl der Arrayelemente) handelt.

Wenn man das Sortieren hinzuzählt, dann ist mein Algorithmus O(n log n). (Komplexität eines beliebigen guten allgemeinen Sortierverfahrens). Wenn Radixsort erlaubt wäre, blieben wir bei O(n).

Bei kombinierten Algorithmen wird die Komplexität des ...komplexeren... Algorithmus genommen.

Komplexitäten kann man im Übrigen nicht addieren.

[gammatester]

Zitat:

Zitat von alzaimar

Das ist -mit Verlaub- falsch.

Mein Algorithmus ist O(n) und nicht O(n^2). Auch nicht irgendwas dazwischen. Wir haben eine einfache Schleife über alle Arrayelemente.

Dafür ist er allerdings -mit Verlaub- völliger Schrott: Wenn man Deinen Code wirklich mal testet, ergibt sich zB

(1,1,2) -> (1,1,2) oder (1,2,1) -> (2,2)

Was sollen also die ganzen Komplexitätsüberlegungen? Das wichtigste ist ein Algorithmus, das tut was er soll.

Gruß Gammatester

[jfheins]

Wenn die Zahlen nicht allzu groß sind, würde ich einen (leicht modifizierten) Bucketsort empfehlen ...

[qwertz543221]

corpsman:

Zitat:

Probier mal das hier, ..
[delphi]
// quicksort_Array;
// entfernen doppelte, dreifache ..
for i :=high(MyArray) downto 1 do begin
if MyArray[i-1] = MyArray[i] then begin
for j := i to High(Myarray)-1 do begin
myArray[j] := myArray[j+1];
end;
setlength(Myarray, high(myarray));
end;
end;
[delphi]


habs aber nicht getestet ,)

danke - das ist in kürze das ausgesagt, was ich brauchte. danke auch an alle anderen für ihre bemühungen.

[alzaimar]

Zitat:

Zitat von gammatester

Dafür ist er allerdings -mit Verlaub- völliger Schrott:

Sehr erfreut, Ihren Charakter kennenzulernen.

Zitat:

... (1,2,1) -> (2,2)

Sortiert sollte die Liste schon sein, so wie in der Lösung des Threaderstellers erwähnt.

Allerdings hast Du bezüglich er mangelnden Korrektheit Recht. Da hat sich -da ungetestet- ein kleiner Fehler eingeschlichen. Danke für's testen. Hier der korrekte Code: Er ist sogar etwas einfacher:

Delphi-Quellcode:

  // MyArray ist sortiert.

  j := 0;
  i := 1;
  while i <= Length (myArray) - 1 do
    if MyArray[i] <> MyArray[j] then begin
      inc(j);
      MyArray[j] := MyArray[i];
    end
    else
      inc(i);

  SetLength (myArray,j+1);

Zitat:

Was sollen also die ganzen Komplexitätsüberlegungen? Das wichtigste ist ein Algorithmus, das tut was er soll.

So kann man das auch sehen.

Es gibt Leute, die wollen nicht nur eine Lösung, sondern sind bestrebt, eine optimale Lösung zu finden. Du gehörst offensichtlich nicht dazu, sondern eher zu dem Schlag, der stattdessen lieber rumpöbelt. Bitte sehr. Jedem das Seine. Oder bist Du nur mit dem falschen Fuß aufgestanden

[gammatester]

Zitat:

Zitat von alzaimar

Danke für's testen. Hier der korrekte Code:

Wollte gerade etwas ausführlicher antworten, als Deine PN auftauchte. Mehr dort, hier nur kurz: Der verbesserte Code ist allerdings entgegen Deiner Behauptung immer noch nicht korrekt, zB wird ein Feld der Länge 0 auf Länge 1 gesetzt.

[user0815]

Frage: Kann man nicht auch einfach eine Stringlist nehmen mit folgenden Eigenschaften: Sorted := True sowie Duplicates := dupIgnore ?

[gammatester]

Zitat:

Zitat von user0815

Frage: Kann man nicht auch einfach eine Stringlist nehmen mit folgenden Eigenschaften: Sorted := True sowie Duplicates := dupIgnore ?

Das wäre allerdings ziemlich umständlich, da die Zahlen erst in Strings umgewandelt, in die Liste verfrachtet, und anschließend wieder zu Zahlen gemacht werden müssen. Da wir nicht wissen, was der TE unter Random-Zahlen versteht, besteht dabei für zumindest für random()-Zahlen (d.h. Fließkommazahlen zwischen 0 und 1) die Gefahr von Umwandlungsungenauigkeiten mit Folgefehlern.

[qwertz543221]

wie ganz zu bewginn erwähnt (nur kurz in der klammerangabe), müssen es nicht nur randomzahlen sein, sondern es dürfen auch zb vordenfinierte arrays - später sollen daraus verkettete listen aus records (eintrag+zeiger auf nächstes element) werden - bearbeitet werden.

Die Randomzahlen stellen nur den anfang dar, um das ganze ienmal zum laufen zu bringen, bzw mögliche vorgehensweisen zu erproben oder zu verfeinern, dafür habt ihr mir ja schon eineiges an nfomaterial geliefert.

[Blup]

Eine Möglichkeit wäre das Sortieren mit dem Filtern zu koppeln:

Delphi-Quellcode:

type
  TElement = Integer;
  TMyArray = array of TElement;

function Filter(const Arr: TMyArray): TMyArray;
{---}
  function MyCompare(const Item1, Item2: TElement): Integer; inline;
  begin
    {Vergleich abhängig vom Typ der Elemente}
    Result := Item1 - Item2;
  end;
{---}
  procedure AddResult(var Result: TMyArray; const Element: TElement); inline;
  var
    idx, idx1, idx2, iComp: Integer;
  begin
    {Index finden}
    idx1 := 0;
    idx2 := High(Result);
    while idx1 <= idx2 do
    begin
      idx := (idx1 + idx2) div 2;
      iComp := MyCompare(Result[idx], Element);
      if iComp < 0 then
        idx1 := idx + 1
      else if iComp > 0 then
        idx2 := idx - 1
      else
        Exit;
    end;
    {Einfügen}
    SetLength(Result, Length(Result) + 1);
    for idx := High(Result) downto idx1 + 1 do
    begin
      Result[idx] := Result[idx - 1];
    end;
    Result[idx1] := Element;
  end;
{---}
var
  i: Integer;
begin
  for i := 0 to High(Arr) do
    AddResult(Result, Arr[i]);
end;

[Codix32]

Hier meine zusammengeschusterte Routine. Die funktioniert perfekt:

Delphi-Quellcode:

Type
 TSXArray = array of shortint;

...
...
var
 SXArray:TSXArray;
....
....
procedure TForm1.entfernedoppelteWerte(myarray:TSXARRAY);
var
  i:integer;
begin
 for i :=high(MyArray) downto 0 do
  begin
   if MyArray[i-1] = MyArray[i] then
      loescheArray(SXArray,i);
  end;

procedure TForm1.loescheArray(var A:TSXArray;Aindex:Integer);
begin
   Move(A[AIndex + 1], A[AIndex], SizeOf(A[0]) * (Length(A) - AIndex - 1));
   SetLength(A, Length(A) - 1); // Länge kürzen
end;

Die Routine geht mit oder ohne Sortierung.

[BUG]

Ich fände es interessant, dass Ganze als modifizierten Mergesort zu implementieren und bei jedem Merge die Dopplungen zu eliminieren. Bei vielen beieinander liegenden Dopplungen könnte das vielleicht sogar ganz vernünftig sein.

[Bjoerk]

Hatte letztens exakt das gleiche Problem. Den Code auf eine IntegerList übertragen:

Delphi-Quellcode:

procedure TIntegerList.RemoveDoubles;
var
  I, J, NewCount: integer;
begin
  if Count > 1 then // Count = Length(Items);
  begin
    Sort;
    I := 0;
    NewCount := 0;
    while I < Count do
    begin
      J := I;
      while (J < Count - 1) and (Items[I] = Items[J + 1]) do
        Inc(J);
      Items[NewCount] := Items[I];
      Inc(NewCount);
      I := J + 1;
    end;
    Count := NewCount; // SetLength(Items, NewCount);
  end;
end;

[Namenloser]

Eine Hashmap wäre auch noch eine Möglichkeit. Einfach im ersten Schritt alle Elemente des einen Arrays durchlaufen und in die Map einfügen, dann im zweiten Schritt das zweite Array durchlaufen und prüfen, ob das jeweilige Element in der Hashmap ist. Wäre dann O(n) für alles zusammen. Ist dafür nicht in-place.

[Dejan Vu]

Hatte ich auch vorgeschlagen, aber der TE hatte sich nicht an diese Struktur 'herangetraut' (soweit ich mich erinnere).
Zudem müsste man die Punkte rastern (weil nicht auf Gleichheit, sondern auf Nähe verglichen wird), und das gäbe ein 'falsches' Ergebnis. Nun muss man dazu sagen, das die jetzige Lösung (Sortieren und Eliminieren) auch 'falsch' ist, bzw. nicht optimal bezüglich der Anzahl der übrig gebliebenen Punkte.

[Sir Rufo]

Ihr wisst aber schon, dass ihr gerade einen Gaul aus 2009 reitet?

Mich dünkt der ein oder andere wähnt sich in einem anderen Thread :mrgreen:

[Dejan Vu]

Ha ha! Verwechselt mit einem Thread fast gleichen Namens...
http://www.delphipraxis.net/183048-d...-loeschen.html