3

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

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

有什么建议么？

4

4 回答 4

7

你的 shuffle-routine 是如何实现的？特别是交换程序？如果您已经编写了自己的代码，请遵循以下原则：

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.
于 2009-10-21T11:16:17.647 回答
1

在内存中重新排列一个字符串列表很慢，所以我会打乱一个索引列表作为初始优化。

我猜您选择 stringlist 是为了方便从磁盘加载和保存到磁盘。一种更快的方法是对索引进行洗牌。制作一个包含 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（或 N*8 对于 64 位索引）以发现行开始的偏移量，然后查找文本文件流中的那个位置并读出一行。

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

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

于 2009-10-21T19:28:16.877 回答