Stringliste zufällig mischen

[kcx]

Hallo,

Ich suche einen Code eine Stringliste möglichst schnell zu mischen.
Ich habe folgenden Code, der auch funktioniert, nur leider sehr langsam ist.

Delphi-Quellcode:

procedure Shuffle(List: TStrings);
var
  i: Integer;
begin
  Randomize;
  List.BeginUpdate;
  try
    for i := 0 to Pred(List.Count) do
      List.Exchange(i, Random(List.Count));
  finally
    List.EndUpdate;
  end;
end;

Kann man das auch schneller machen?

Danke

[shmia]

Um welche TStrings Klasse handelt es sich genau ?
Ist es vielleicht das Property Lines von TMemo oder Items von TComboBox ?
Dann sind die Zugriff stark verlangsamt, da im Hintergrund Windows Messages verschickt werden.

Workararoud: alle Items auf eine echte TStringList kopieren, Daten verwürfeln und wieder zurückkopieren.

[kcx]

Zitat:

Zitat von shmia

Um welche TStrings Klasse handelt es sich genau ?
Ist es vielleicht das Property Lines von TMemo oder Items von TComboBox ?
Dann sind die Zugriff stark verlangsamt, da im Hintergrund Windows Messages verschickt werden.

Es sind die Items einer ListBox.

Zitat:

Zitat von shmia

Workararoud: alle Items auf eine echte TStringList kopieren, Daten verwürfeln und wieder zurückkopieren.

Habe ich schon probiert, ist aber leider genauso langsam.

Eine Möglichkeit wäre wohl der Umweg über ein String Array oder gibt es noch eine bessere Lösung?

[shmia]

Versuch mal spasseshalber, um zu Testen, ob die Random-Funktion die Bremse ist:

Delphi-Quellcode:

procedure Shuffle(List: TStrings); 
var 
  i: Integer; 
begin 
  Randomize; 
  List.BeginUpdate; 
  try 
    for i := 0 to Pred(List.Count) do 
      List.Exchange(i, (i*991+103) mod List.Count); // 991 & 103=Primzahl
  finally 
    List.EndUpdate; 
  end; 
end;

[kcx]

Zitat:

Zitat von shmia

Versuch mal spasseshalber, um zu Testen, ob die Random-Funktion die Bremse ist:

Delphi-Quellcode:

procedure Shuffle(List: TStrings); 
var 
  i: Integer; 
begin 
  Randomize; 
  List.BeginUpdate; 
  try 
    for i := 0 to Pred(List.Count) do 
      List.Exchange(i, (i*991+103) mod List.Count); // 991 & 103=Primzahl
  finally 
    List.EndUpdate; 
  end; 
end;

Ist gut 200 ms schneller, also nicht wirklich viel. :wink:

So ist es zwar etwas umständlich, aber dafür sehr schnell:

Delphi-Quellcode:

procedure Shuffle3(List: TStrings);
var
  i, r: Integer;
  s: Array of String;
  t: String;
begin
  SetLength(s, List.Count);
  for i := 0 to Pred(List.Count) do
    s[i] := List[i];
  List.BeginUpdate;
  try
    List.Clear;
    for i := Low(s) to High(s) do
    begin
      //repeat
        r := Random(High(s));
      //until r <> i;
      t := s[i];
      s[i] := s[r];
      s[r] := t;
    end;
    for i := Low(s) to High(s) do
      List.Add(s[i]);
  finally
    List.EndUpdate;
  end;
end;

Werde es dann wohl doch so machen, Thx@All.

[SirThornberry]

also ist einfach das exchange zu langsam?! Dann gibts noch bessere Möglichkeiten

[Klaus01]

Hallo,

eine kleine Testprozedur:

TStringList.Exchange : 0ms
ListBox1.items.Exchange: 1060ms
Listbox über TStringList mischen: 109ms

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var
  sl: TStringList;
  i : Integer;
  start : TDateTime;
begin
  sl := TStringList.create;
  for i:=0 to 9999 do
    sl.add(intToStr(i));
  ListBox1.Items.Assign(sl);

  // durchwürfeln

  start := now;
  for i:=sl.count -1 downto (sl.count - 1) div 2 do
    sl.Exchange(i,random(sl.count));
  showMessage('TStringList.Exchange: '+IntToStr(MilliSecondsBetween(now,start)));


  ListBox1.Items.BeginUpdate;
  start := now;
  for i:= ListBox1.Items.Count -1 downto (ListBox1.Items.Count -1) div 2 do
    ListBox1.Items.Exchange(i,random(ListBox1.Items.count));
  showMessage('TListBox.items.Exchange: '+IntToStr(MilliSecondsBetween(now,start)));
  ListBox1.Items.EndUpdate;

  start := now;
  sl.Assign(ListBox1.items);
  for i:=sl.count -1 downto (sl.count - 1) div 2 do
    sl.Exchange(i,random(sl.count));
  ListBox1.Items.Assign(sl);
  showMessage('TListBox über StringList.exchange: '+IntToStr(MilliSecondsBetween(now,start)));

  sl.free;
end;

Grüße
Klaus

[bigg]

Hi,

mischt doch nur die Indizes. Das dürfte die schnellste Methode sein.

[Klaus01]

Zitat:

Zitat von bigg

Hi,

mischt doch nur die Indizes. Das dürfte die schnellste Methode sein.

Das macht .Exchange doch.

Hansa hatte freundlicherweise den Code von Exchange in diesem Thread in Beitrag #15 eingestellt.
Grüße
Klaus

[bigg]

Exchange ist doch imho eine SWAP-Funktion. Warum muss die Liste, also deren Strings umsortiert werden, es reicht doch wenn nur deren Index (Integer) "sortiert" wird.