テキストファイルDelphiソースまたはその他のファイルをシャッフルする

StackOverflow https://stackoverflow.com/questions/1600012

質問

10,000エントリの文字列リストがあります。シャッフルルーチンがありますが、いずれかのアイテムにアクセスするには時間がかかります。 1万個すべてのアイテムを処理するには膨大な時間がかかります。

ディスクを保存してから、別の方法を使用してファイルをシャッフルします。

提案はありますか

役に立ちましたか？

解決

シャッフルルーチンはどのように実装されていますか？特に交換ルーチンは？独自のコードを作成している場合、これらの行に沿って： 

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

非常に遅くなります。 stringlistでexchange-methodを使用します。

このコードは、私の平均的な（3歳）コンピューターで78ミリ秒かかりました：

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.

他のヒント

メモリ内の文字列リストの再配置は遅いため、最初の最適化としてインデックスリストをシャッフルします。

ディスクからのロードとディスクへの保存の利便性のために、stringlistを選択したと思います。より簡単な方法の1つは、インデックスをシャッフルすることです。 10,000個の整数の配列を作成し、それらをシャッフルしてから、一時的な文字列変数を使用してスワップ要素を保持し、シャッフルされたインデックス値を使用して文字列リストを上から下に再配置します。

大幅な書き換えにより大幅に改善されますが、これは文字列が大きすぎない場合に役立ちます。

簡単な方法は、乱数のリストを生成してソートし、後でデータのペアごとのスワップを行うことです。ソートはo（n * log（n））アルゴリズムとして実行できますが、スワッピングは常にo（n）アルゴリズムであるため、はるかに高速です。

念のため、データをそのままにして、シャッフルされた余分なインデックスを保存することを検討してください。

シャッフルされた範囲の作成について質問しました-数値のリストを生成してからシャッフルするのではなく、シャッフルされた数値のリストをO（n）メモリコストなしで繰り返し返すことができる関数が必要でした：

シャッフルではなくPRNGを使用してシャッフル範囲を生成

ディスク上のファイルに何らかの種類のインデックスを作成すると、メモリコストを支払うことなくシャッフルバージョンを作成できます。これは、非常に大きなファイルの場合に重要です。インデックスについては、各行の開始位置（32ビットまたは64ビット整数）のフラットストリームのような単純なものをお勧めします。このようにして、テキストファイルからN行目を抽出するには、インデックスストリームでN * 4（または64ビットインデックスの場合はN * 8）をシークして、ラインスタートのオフセットを見つけてから、テキストファイルストリーム内のその位置に移動し、1行を読み取ります。

このアプローチを使用すると、メモリ内のコストを支払うことなく、非常に大きなファイルをシャッフルできます。もちろん、シャッフルは、ソースファイルからランダムに行を抽出することを意味します。これは、ファイルが非常に小さい（最初のアクセスでほぼキャッシュに収まる）または非常に大きい（この場合、メモリスラッシング）場合を除き、インメモリソートほど効率的ではありませんランダムシークよりも悪化します）、またはおそらく機械式ハードドライブ（SSDなど）を使用していない場合。

あなたの状況では、10Kはそれほど大きな数字ではありません。おそらく数ギガバイトのテキスト（もちろん行の長さによる）に入る1000万行の領域の何かははるかに困難であり、32ビットではこのアプローチ（または同様のもの）が必要になります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top