TStrings mischen nach Fisher-Yates

[shmia]

Es gibt verschiedene Verfahren um eine Liste zu Mischen; also in eine zufällige Unordnung zu bringen.
Der bekannteste Algorithmus dürfte der nach Fisher-Yates sein.

Man darf sich von der Einfachheit der procedure FisherYatesShuffle() nicht täuschen lassen.
Beim Mischen kann man durchaus einige Fehler machen, die leider nicht sofort ins Auge fallen.

Zusätzlich sorgt der folgende Code dafür, dass z.B. das Mischen von Memo-Zeilen schnell vonstatten geht.
Hintergrund: der Zugriff auf einzelne Strings von [TMemo].Lines, [TListbox].Items oder [TCombobox].Items ist sehr langsam. Durch das Kopieren in ein TStringList-Objekt kann die Gewschwindigkeit massiv gesteiegert werden.

Delphi-Quellcode:

procedure ShuffleTStrings(s:TStrings);
  procedure FisherYatesShuffle(x:TStrings);
  var
     i : Integer;
  begin
     for i := x.Count-1 downto 1 do
        x.Exchange(i, random(i+1));
  end;
var
   t : TStringList;
begin
   Assert(Assigned(s));
   if s is TStringList then
      FisherYatesShuffle(s)
   else
   begin
      t := TStringList.Create;
      try
         t.Assign(s);
         FisherYatesShuffle(t);
         s.Assign(t);
      finally
         t.Free;
      end;
   end;
end;

[Sir Rufo]

Die Performance-Probleme kommen aber von der falschen Handhabung.

So ist der Zugriff auch schnell

Delphi-Quellcode:

Memo1.Lines.BeginUpdate;
try
  { irgendwas mit dem Memoinhalt machen }
finally
  Memo1.Lines.EndUpdate;
end;

Trotzdem würde ich das immer in einer Funktion auslagern, aufgrund der Trennung von Logik und Anzeige.

[Luckie]

Und das Assert würde ich durch eine Exception ersetzen. Und generell würde ich voraussetzen, dass du einen Nachfahren von TStrings bekommst. Denn ein bisschen Intelligenz sollte man schon voraussetzen können.

[Sir Rufo]

Das reicht voll und ganz aus.

Delphi-Quellcode:

procedure FisherYatesShuffle( x : TStrings );
  var
     i : Integer;
  begin
    x.BeginUpdate;
    try
      for i := x.Count - 1 downto 1 do
        x.Exchange( i, random( i + 1 ) );
    finally
      x.EndUpdate;
    end;
  end;

Und ob es nun wegen dem Assert rummst oder man eine Exception selber schmeißt ist egal, da auch ohne das Gerafffel automatisch eine Exception hochpoppt, wenn x keine gültige Instanz hat.
Also kann man das bei solch hochkomplexen Routinen auch gleich weglassen.

[shmia]

Zum Thema Performance: Sortieren von 3000 Zeilen eines TMemo

Code:

Procedure aus Betrag #1:          0,26 Sekunden
Procedure aus vorherigem Betrag: 39,5 Sekunden

Damit ist die ursprüngliche Procedure mehr als 100fach schneller.

Zitat:

Und ob es nun wegen dem Assert rummst oder man eine Exception selber schmeißt ist egal, da auch ohne das Gerafffel automatisch eine Exception hochpoppt, wenn x keine gültige Instanz hat.

Also ich sehe das so:
Die Procedure erwartet ein gültiges Objekt von TStrings bzw. eine Ableitung davon.
Sollte der Programmierer fälschlicherweise ein "Nil-Objekt" übergeben, dann ist das Programmierfehler anzusehen; also ein Zustand der "eigentlich" nie auftreten dürfte.
Hier eine Exception zu werfen wäre nicht richtig, da es sich nicht um einen erwarteten Fehler handelt.
Es bleiben also noch 4 Optionen übrig, wie man damit umgeht:
1.) nichts tun - damit würde es eine Zugriffsverletztung geben.
Leider gibt es überhaupt keine Hinweis auf die Ursache der Zugriffsverletzung.
Ich weiss nicht, kennt ihr das bescheidene Gefühl, wenn bei einer Livevorführung vor versammelter Mannschaft plötzlich eine Zugriffsverletzung angezeigt wird?
Man möchte geradewegs im Boden versinken.
2.) Assert verwenden - man bekommt Dateiname+Zeilennummer; das hilft ungemein bei der Fehlersuche
3.) if not Assigned(s) then Exit; Keine schlechte Option; so kann die Procedure keinen Schaden anrichten
4.) Kombination aus 2.) und 3.)

Delphi-Quellcode:

if not Assigned(s) then
begin
  Assert(False, 'ShuffleTStrings(nil)');
  Exit;
end;

Das scheint mir der beste und sauberste Weg zu sein mit dem nil-Zeiger Problem umzugehen.

[Luckie]

Zitat von shmia:

Sollte der Programmierer fälschlicherweise ein "Nil-Objekt" übergeben, dann ist das Programmierfehler anzusehen; also ein Zustand der "eigentlich" nie auftreten dürfte.
Hier eine Exception zu werfen wäre nicht richtig, da es sich nicht um einen erwarteten Fehler handelt.

Doch genau, das wäre ein Fall für eine Exception, denke ich. Denn es war nicht die Absicht des Programmierer ein NIL.Objekt zu übergeben.

Zitat:

2.) Assert verwenden - man bekommt Dateiname+Zeilennummer; das hilft ungemein bei der Fehlersuche

Das ist schon richtig, hat aber in produktiven Code nichts verloren. Deswegen gibt es ja auch die Option die Assertions per Compilerschalkter abzuschalten. Was machst du dann?

Zitat:

3.) if not Assigned(s) then Exit; Keine schlechte Option; so kann die Procedure keinen Schaden anrichten

Und man sucht sich dumm und dämloich, warum nichts passiert.

Zitat:

4.) Kombination aus 2.) und 3.)

Siehe oben. Teste auf nil und wirf eine Exception.