A quick way to generate random sample data using delphi

Question

I have such a jet

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; 

and procedure for generating random data

 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; 

How can I improve the performance of the FillRandomListSignals procedure?

Edit : This structure is used to create thousands (maybe millions) of calculations.

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

Answer 1

Speed ​​is not the only problem when you generate random data, you really want the data to be random, you don’t want your experiment to suffer from duplicate data or other problems with a pseudo-random generator. If you need speed more and then randomness, you can always use a function like this , which will be very fast! </joke> .

Here's a message from Barry Kelly about a stack overflow describing possible problems with the built-in random number generator. Not going to bring it here, go read it for yourself, this is good stuff.

To conclude, when I needed a PRNG sufficient to generate a huge amount of random data, I used the Mersenne Twister (wikipedia link) sown by Delphi PRNG.

Quote from Wikipedia about Mersen Twister:

For many applications, Mersenne twister quickly becomes a pseudo-random number generator. Mersenne Twister is designed using simulation in Monte Carlo and other statistical simulators. Researchers primarily want high quality, but can also take advantage of their speed and portability.

And in order to break all my records by the number of links per post, I used this implementation of Delphi .

And my last thought: if you are not very good at math, stay away from your own PRNG implementations. Like hash functions, it's easy to make mistakes, and it's very difficult to parse them.

---

Edit

Was there any kind of timing using the following code. 10,000,000 records took 1,480 ms to create using the Mersenne Twister. The same code, using Delphi, built in a random number generator, took only 250 ms, for the same 10M records. Something tells me that this is not a random generator that needs to be optimized, but something else in the code.

 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

You cannot use the built-in Random () function for each field, but globally some code with pipeline-optimized access, working with a random pre-generated array:

 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; 

The above function can be called like this (you have to call the InitCrc32Tab procedure once in your program):

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

This will be faster than using the Random () function, since this function uses two integer multiplications and is not pipelined at all. The above loop will process 16 bytes at a time, without multiplying and several operations per processor cycle, because I optimized it to use as many CPU pipelines as possible. Could we play with the seed? variables or use some optimized asm, but you have an idea.

P.S:

Since you are filling out a list with random data, there is NO NEED to clear it earlier. Just a waste of time.

Answer 3

If you have only 256 entries, I don’t see how this code can take more than a few ms, so why bother. Keep in mind Amdahl’s law :-)