使用delphi生成随机样本数据的快速方法

Question

我有这样的结构

const
  MaxSignalRecords=255;
type
  TSignalRecord=record
   signal1  : integer;
   signal2  : integer;
   signal3  : integer;
   signal4  : integer;
   signal5  : integer;
   signal6  : integer;
   bsignal1 : Boolean;
   bsignal2 : Boolean;
   bsignal3 : Boolean;
   bsignal4 : Boolean;
   bsignal5 : Boolean;
   bsignal6 : Boolean;
  end;

TListSignals = Array[0..MaxSignalRecords-1] of TSignalRecord;

以及生成随机样本数据的过程

Procedure FillRandomListSignals(var ListSignals:TListSignals);
var
  i :Integer;
begin
  for i := 0 to MaxSignalRecords - 1 do
  with ListSignals[i] do
  begin
   signal1   :=Random(MaxInt);
   signal2   :=Random(MaxInt);
   signal3   :=Random(MaxInt);
   signal4   :=Random(MaxInt);
   signal5   :=Random(MaxInt);
   signal6   :=Random(MaxInt);
   bsignal1  :=Boolean(Random(2));
   bsignal2  :=Boolean(Random(2));
   bsignal3  :=Boolean(Random(2));
   bsignal4  :=Boolean(Random(2));
   bsignal5  :=Boolean(Random(2));
   bsignal6  :=Boolean(Random(2));
  end;
end;

我怎样才能提高FillRandomListSignals程序的性能？

编辑:此结构用于制作数千(可能是数百万)的计算

for i:=1 to 1000000 do
begin
  CleartheList(MyList);
  FillRandomListSignals(MyList);
  DotheMath(MyList);
  DotheChart(MyList);
end;

Answer 1

当您生成随机数据时,速度不是您唯一关注的问题,您实际上希望数据是随机的,您不希望您的实验受到重复数据或其他伪随机生成器问题的困扰.如果你更关心速度和随机性,你可以随时使用像这样的功能,这将是超快的!</joke>.

以下是Barry Kelly关于Stack Overflow的文章,描述了内置随机数生成器可能出现的问题.不打算在这里引用它,自己去读它,这是好东西.

为了得出结论,当我需要一个足够好的PRNG来生成大量的随机数据时,我使用了一个Mersenne Twister (维基百科链接),由Delphi的PRNG播种.

来自维基百科的Mersene Twister引用:

对于许多应用来说,Mersenne twister很快成为首选的伪随机数发生器.Mersenne Twister的设计考虑了蒙特卡罗模拟和其他统计模拟.研究人员主要想要高质量的数字,但也受益于它的速度和便携性.

为了打破我每个帖子链接数量的所有记录,我使用了这个Delphi实现.

我最后的想法是:除非你非常擅长数学,否则要远离自制的PRNG实施.就像哈希函数一样,它很容易出错并且很难分析.

编辑

有一些时间,使用以下代码.使用Mersenne Twister生成10,000,000条记录需要1480毫秒.使用Delphi的内置随机数生成器的相同代码仅花费250毫秒,对于相同的10M记录.有些东西告诉我,这不是需要优化的随机生成器,而是代码中的其他内容.

procedure TForm1.Button1Click(Sender: TObject);
var InitArray:array[0..99] of LongInt;

    i, N:Integer;
    TSR: TSignalRecord;

    CStart, CStop: Int64;

begin
  Randomize;
  for i:=0 to 99 do InitArray[i] := Random($effffff);
  InitMTbyArray(InitArray, Length(InitArray));

  CStart := GetTickCount;

  for i:=1 to 10000000 do
  begin
    TSR.signal1 := IRanMT;
    TSR.signal2 := IRanMT;
    TSR.signal3 := IRanMT;
    TSR.signal4 := IRanMT;
    TSR.signal5 := IRanMT;
    TSR.signal6 := IRanMT;

    N := IRanMT;

    TSR.bsignal1 := (N and 1) <> 0;
    TSR.bsignal2 := (N and 2) <> 0;
    TSR.bsignal3 := (N and 4) <> 0;
    TSR.bsignal4 := (N and 8) <> 0;
    TSR.bsignal5 := (N and 16) <> 0;
    TSR.bsignal6 := (N and 32) <> 0;
  end;

  CStop := GetTickCount;

  Caption := IntToStr(CStop - CStart);
end;

Answer 2

您可能不会在每个字段中使用内置的Random()函数,但在全局范围内使用流水线优化的访问,使用随机预生成的数组:

var
  crc32tab: array[byte] of cardinal;

procedure InitCrc32Tab;
var i,n: integer;
    crc: cardinal;
begin // this code size is only 105 bytes, generating 1 KB table content
  for i := 0 to 255 do begin
    crc := i;
    for n := 1 to 8 do
      if (crc and 1)<>0 then
        // $edb88320 from polynomial p=(0,1,2,4,5,7,8,10,11,12,16,22,23,26)
        crc := (crc shr 1) xor $edb88320 else
        crc := crc shr 1;
    crc32tab[i] := crc;
  end;
end;

type NativeUInt = cardinal; // before Delphi 2007

procedure RandomData(P: PAnsiChar; Len: integer);
var i: integer;
    seed0, seed1, seed2, seed3: cardinal;
begin
  if Len>=16 then
  begin
    seed0 := Random(maxInt);
    seed1 := seed0*$8088405;
    seed2 := seed1*$8088405;
    seed3 := seed2*$8088405;
    for i := 1 to Len shr 4 do begin  // pipelined loop for 16 bytes at once
      PCardinalArray(P)[0] := crc32tab[byte(seed0)] xor seed0;
      seed0 := seed0 xor NativeUInt(P);
      PCardinalArray(P)[1] := crc32tab[byte(seed1)] xor seed1;
      seed1 := seed1 xor NativeUInt(P);
      PCardinalArray(P)[2] := crc32tab[byte(seed2)] xor seed2;
      seed2 := seed3 xor NativeUInt(P);
      PCardinalArray(P)[3] := crc32tab[byte(seed3)] xor seed3;
      seed3 := seed3 xor NativeUInt(P);
      inc(P,16);
    end;
  end;
  for i := 1 to Len and 15 do begin
    P^ := PAnsiChar(@crc32tab)[NativeUInt(P) and 1023];
    inc(P);
  end;
end;

可以像这样调用上面的函数(你必须在程序中调用一次InitCrc32Tab过程):

procedure FillRandomListSignals(var ListSignals: TListSignals);
begin
  RandomData(@ListSignals,sizeof(ListSignals));
end;

它将比使用Random()函数更快,因为此函数使用两个整数乘法,并且根本不进行流水线操作.上面的循环将同时处理16个字节,没有乘法,每个CPU时钟有多个操作,因为我优化它以使用尽可能多的CPU流水线.我们也许可以玩种子？变量,或使用一些优化的asm,但你已经有了这个想法.

Postscriptum:

由于您使用随机数据填充列表,因此无需先清除它.只是浪费时间.