3

10,000エントリの文字列リストがあります。シャッフルルーチンがありますが、いずれかのアイテムへのアクセスに時間がかかります。すべての10,000アイテムを通過するには、非常に長い時間がかかります。

ディスクに保存してから、別の方法でファイルをシャッフルしたいと思います。

助言がありますか？

4

4 に答える 4

7

シャッフルルーチンはどのように実装されていますか？特に交換ルーチン？あなたがこれらの線に沿ってあなた自身を書いたならば：

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

非常に遅くなります。文字列リストで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.
于 2009-10-21T11:16:17.647 に答える
1

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

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

大幅な書き換えにより大幅な改善が見られますが、文字列が大きすぎない場合は、これが役立つ可能性があります。

于 2009-10-21T11:04:17.500 に答える
1

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

思いもよらなかった場合に備えて、データをそのままにして、余分なシャッフルされたインデックスを保存することを検討してください。

于 2009-10-21T11:26:47.977 に答える
1

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

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

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

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

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

于 2009-10-21T19:28:16.877 に答える