Doppelte Zahlen in Arrays finden

[KeeN]

Hallo!

Ich hab grad ein Programm geschrieben, dass mir Zufallszahlen in ein Array abspeichert. Jetzt gehts darum Doppelte Zahlen zu filtern.

Frage: Wie stellt man das am effizientesten an? Das Array Stück für Stück zu durchsuchen dürfte wohl ziemlich uneffizient sein.

MfG
KeeN

[MadMason]

wird dir aber wohl nichts anderes übrigbleiben
(verbessert mich wenn ich mich irre) aber ein anderer weg als "per hand" ist mir nicht bekannt

Delphi-Quellcode:

for i:= 0 to Length(array)-1 do begin
 for i2:= 0 to Length(array)-1 do begin
  if array[i2] = array[i] then begin
   //tu was
  end;
 end;
end;

[Jan]

Hallo KeeN,
du solltest von Anfang an filtern bevor du ins array schreibst.
Schau dir mal diesen thread an:
http://www.delphipraxis.net/viewtopi...ghlight=random
Gruß
Jan

[janjan]

Zitat von MadMason:

wird dir aber wohl nichts anderes übrigbleiben
(verbessert mich wenn ich mich irre) aber ein anderer weg als "per hand" ist mir nicht bekannt

Delphi-Quellcode:

for i:= 0 to Length(array)-1 do begin
 for i2:= 0 to Length(array)-1 do begin
  if array[i2] = array[i] then begin
   //tu was
  end;
 end;
end;

ich würds eher so machen

Delphi-Quellcode:

for i:= 0 to Length(array)-1 do begin
 for i2:= [color=#f60000]i[/color] to Length(array)-1 do begin
  if array[i] = array[i2] then begin
   //tu was
  end;
 end;
end;

[KeeN]

Jan's Vorschlag klingt am besten, find ich. In dem anderen Beitrag steht geschrieben:

Zitat:

Etwas besser ist es da (insbesondere bei noch größeren Bereichen) die gezogene Zufallszahl als Zähler in der Menge der noch nicht gefundenen Zahlen zu benutzen.

Ok. Und nun für Dumme :Wie stell ich das an, bzw. kann mir das einer mal etwas genauer erläutern?

KeeN

[nailor]

Nimm doch statt nem Array ein Set. Das hat mit dem "in" Operator schon einen Membership-Test.

Also wenn, du wissen willst, ob die 5 in deinem Set ist, dann schreibst du einfach:

if 5 in DeinSet then ...

[Hansa]

Hi,

die gezogene Zahl muß dann aber aus der Menge wenigstens raus, glaube Du brauchst nur

Code:

VorhandenesSet := VorhandenesSet - [gezogene Zahl]

zumindest so in dem Sinne. Die leere Menge muß dabei eventuell berücksichtigt werden.

Gruß
Hansa

[jbg]

Und nun die Einschränkung von Sets:
Sets können max. 256 unterschiedliche Werte aufnehmen.

[janjan]

bei großen arrays wäre es glaube ich sinnvoller und schneller die zahlen erst der größe nach zu sortieren und danach die liste einmal von oben nach unten durchzukucken:

Delphi-Quellcode:

for i:= 0 to Length(array)-2 do begin
  if array[i] = array[i+1] then 
    begin
      DoSomething;
    end;
end;

[MrSpock]

Hallo KeeN,

der Beitrag mit dem Nutzen der Zufallszahl als Zähler war von mir. Das Problem war ja, dass Privateer3000 Zufallszahlen ziehen wollte und doppelte vermeiden wollte. Er benötigt also eine zufällige Reihenfolge einer Menge von Zahlen. Mein Vorschlag bezog sich darauf, dass du anfangs eine Liste mit allen erlaubten Zahlen erzeugst. Das kann ein Array, eine Menge (Set) oder eine ring verkette Liste sein.

Wenn du eine Zufallszahl n gezogen hast, nimmst du das n-te noch nicht gezogene Element als neue Zahl und löscht dieses bzw. markierst es als gezogen, falls du ein Array benutzt. Die Lösung mit der ring verketteten Liste ist dabei wohl die flexibelste.