Shuffle Textdatei Delphi Quelle oder irgendetwas anderes

Question

Ich habe eine string mit 10.000 Einträgen. Ich habe eine Shuffle-Routine, aber eines der Elemente Zugriff auf eine Menge Zeit. Wenn man durch alle 10k Artikel nimmt eine Menge Zeit.

Ich will es tun Scheibe speichern und tun dann einen Shuffle auf die Datei andere Methode verwendet.

Irgendwelche Vorschläge?

Answer 1

Wie wird Ihre Shuffle-Routine implementiert? Vor allem der Austausch-Routine? Wenn Sie Ihre eigene geschrieben, in dieser Richtung:

vTempSrting := vStringList[I]; 
vStringList.Delete(I); 
vStringList.Insert(J,vTempString);

wird es sehr langsam sein. Verwenden Sie die Austausch-Methode auf dem String.

Dieser Code hat 78 ms auf meinem ziemlich durchschnittlich (3 Jahre alt) Computer:

program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils,Classes,uIntegerList,Windows,Math;

procedure Shuffle(aSL : TStringList);
var I,J : integer;
begin
  for I := 0 to aSL.Count-1 do
  begin
    J := randomrange(I,aSL.Count);
    aSL.Exchange(I,J);
  end;
end;

procedure CreateTestFile;
var
  vSL : TStringList;
  I : integer;
begin
  vSL := TStringList.Create;
  try
    for I := 1 to 100000 do vSL.Add('Sample text #'+inttostr(I));
    vSL.SaveToFile('c:\test.txt');
  finally
    vSL.Free;
  end;
end;

function TestShuffle : longword;
var
  vSL : TStringList;
  vTick0 : longword;
begin
  vSL := TStringList.Create;
  try
    vTick0 := gettickcount;
    vSL.LoadFromFile('c:\test.txt');
    Shuffle(vSL);
    vSL.SaveToFile('c:\test.txt');
    Result := gettickcount - vTick0;
  finally
    vSL.Free;
  end;
end;

begin
  CreateTestFile;
  writeln(TestShuffle,' ms');
  readln;
end.

Answer 2

einen string im Speicher Umstellen ist langsam, also würde ich eine Indexliste als anfängliche Optimierung mische.

Ich vermute, Sie string für die Bequemlichkeit der Laden von und Speichern auf der Festplatte gewählt haben. Ein schneller Ansatz wäre, einen Index zu mischen. Machen Sie ein Array von 10.000 ganzen Zahlen, mischen diejenigen, verwenden Sie dann ein temporäres String-Variable das Swap-Element zu halten und neu anordnen Ihr string von oben nach unten den schlurfte Indexwerten.

Wichtige Schreibungen werden größere Verbesserungen bieten, aber dies kann helfen, wenn die Saiten nicht zu groß ist.

Answer 3

Eine einfache Möglichkeit ist, eine Liste von Zufallszahlen zu erzeugen, sortieren sie, und dann später tun paarweise Swaps von Daten. Die Sortierung kann als o (n * log (n)) Algorithmus durchgeführt werden, während Swapping immer eine o (n) Algorithmus, so viel schneller.

Gerade falls Sie nicht daran gedacht haben, sollten Sie die Daten belassen, wie es ist, und nur einen zusätzlichen Shuffled Index speichern.

Answer 4

, fragte ich eine Frage, bevor über einen schlurfte Bereich zu schaffen - anstatt eine Liste von Zahlen zu erzeugen und sie dann schlurfend, wollte ich eine Funktion, die iterativ eine Liste der neu gemischte Zahlen zurückkehren konnte, ohne die O (n) Speicherkosten :

Generating schlurfte Bereich ein PRNG verwendet, anstatt schlurfenden

Wenn Sie irgendeine Art von Index für die Datei auf der Festplatte zu erstellen, dann können Sie eine schlurfte Version erstellen, ohne die Speicherkosten zu zahlen, die für sehr große Dateien wichtig sein können. Für einen Index, schlage ich vor, etwas einfach, wie ein flacher Strom von den Positionen (als 32- oder 64-Bit-Integer) jeder Zeile Start. Auf diese Weise, die N-ten Zeile aus der Textdatei zu extrahieren, können Sie einfach in dem Index-Stream suchen zu N * 4 (oder N * 8 für 64-Bit-Indizes) den Versatz des Zeilenanfangs zu entdecken, und dann versuchen, diese Position in dem Textdatei-Stream und eine Zeile ausgelesen werden.

Mit diesem Ansatz können Sie extrem große Dateien mischen, ohne zu bezahlen, die im Speicher Kosten. Natürlich schlurfenden Linien zufällig aus der Quelldatei bedeuten extrahieren, die nicht so effizient sein wird, wie im Speicher befindlichen Sortier es sei denn, die Datei ist sehr klein (passt in Cache fast beim ersten Zugriff) oder sehr groß (in Dreschen diesem Fall Speicher schlechter sein wird als zufällige sucht), oder vielleicht, wenn Sie nicht eine mechanische Festplatte (zB SSD).

mit

Für Ihre Situation, 10K ist wirklich keine große Zahl. Etwas in der Region von 10 Millionen Zeilen, vielleicht in mehr Gigabyte Text bekommen (je nach Leitungslänge natürlich), wird viel schwieriger sein, und das ist, wo dieser Ansatz (oder so ähnlich) in 32-Bit notwendig wäre.