随机播放文本文件 Delphi 源代码或其他任何内容

Question

我有一个包含 10,000 个条目的字符串列表。我有一个随机播放程序，但访问任何项目都需要花费大量时间。浏览所有 10k 项需要花费大量时间。

我想将其保存在磁盘上，然后使用另一种方法对文件进行随机播放。

有什么建议吗？

Answer 1

你的随机播放程序是如何实现的？特别是交换例程？如果您自己编写，那么：

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

它会非常慢。在字符串列表上使用交换方法。

这段代码在我相当普通（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.

Answer 2

在内存中重新排列字符串列表的速度很慢，因此我会打乱索引列表作为初始优化。

我猜您选择 stringlist 是为了方便从磁盘加载和保存到磁盘。一种更快的方法是对索引进行洗牌。创建一个包含 10,000 个整数的数组，对它们进行打乱，然后使用临时字符串变量来保存交换元素，并使用打乱后的索引值从上到下重新排列字符串列表。

主要重写将提供更大的改进，但如果您的字符串不太大，这可能会有所帮助。

Answer 3

一种简单的方法是生成随机数列表，对其进行排序，然后进行数据的成对交换。排序可以使用 o(n*log(n)) 算法来完成，而交换始终是 o(n) 算法，因此速度要快得多。

以防万一您没有想到这一点，请考虑保留数据原样，并仅保存额外的洗牌索引。

Answer 4

我之前问过一个关于创建打乱范围的问题 - 我想要一个能够迭代返回打乱数字列表的函数，而不是生成数字列表然后打乱它们，而不需要 O(n) 内存成本：

使用 PRNG 而不是随机生成随机排列的范围

如果您为磁盘上的文件创建某种索引，那么您可以创建一个打乱版本而无需支付内存成本，这对于非常大的文件来说可能很重要。对于索引，我建议使用一些简单的方法，例如每行开头的位置（作为 32 或 64 位整数）的扁平流。这样，要从文本文件中提取第 N 行，您可以简单地在索引流中查找到 N*4（或 N*8 对于 64 位索引）以发现行开头的偏移量，然后查找文本文件流中的该位置并读出一行。

使用这种方法，您可以打乱非常大的文件，而无需支付内存成本。当然，洗牌意味着从源文件中随机提取行，这不会像内存中排序那样有效，除非文件非常小（几乎在第一次访问时适合缓存）或非常大（在这种情况下内存抖动）会比随机搜索更糟糕），或者如果您不使用机械硬盘驱动器（例如SSD）。

对于你的情况来说，10K确实不是一个大数字。大约 1000 万行的内容，可能会进入几 GB 的文本（当然取决于行长度），将更具挑战性，这就是在 32 位中需要这种方法（或类似的方法）的地方。