Recent

Author Topic: TStringList and Random  (Read 3724 times)

apeoperaio

  • Sr. Member
  • ****
  • Posts: 272
TStringList and Random
« on: November 19, 2018, 02:57:41 pm »
Dear all,
I had issues using threads, TStringList and Random (see the topic: http://forum.lazarus.freepascal.org/index.php/topic,42595.0.html).
I solved my problems using a thread safe random implementation (http://forum.lazarus.freepascal.org/index.php/topic,35050.msg242571.html#msg242571).
Anyway there is still an issue when using Random and TStringList (sort) even on single thread applications.
The TStringList sort (since it uses a quicksort implementation using random to initialize the algorithm) affects the random sequence.
In order to reproduce this issue just place a button, a checkbox and a memo on a form.
The random sequence is different if TStringList is sorted or not.
Is it documented somewhere?

Code: Pascal  [Select][+][-]
  1. procedure TForm1.Button1Click(Sender: TObject);
  2. var
  3.   mem: TStringList;
  4.   i: Integer;
  5. begin
  6.   RandSeed:= 5;
  7.   memo1.Clear;
  8.   mem:= TStringList.Create;
  9.   mem.Sorted:= CheckBox1.Checked;
  10.   for i:= 0 to 9 do
  11.     mem.Append(IntToStr(Random(100)));
  12.   Memo1.Text:= mem.Text;
  13.   mem.Free;
  14. end;  

wp

  • Hero Member
  • *****
  • Posts: 11857
Re: TStringList and Random
« Reply #1 on: November 19, 2018, 03:10:51 pm »
Cannot reprodude. The attached demo is a modification of yours and shows that both sorted and unsorted lists contain the same numbers.

apeoperaio

  • Sr. Member
  • ****
  • Posts: 272
Re: TStringList and Random
« Reply #2 on: November 19, 2018, 03:17:33 pm »
Sorry, my fault. I got different random sequence if I do TStringList.Sort during my Random sequence production.
The following example produce two different random sequence if a Sort is performed or not.

Code: Pascal  [Select][+][-]
  1. var
  2.   mem: TStringList;
  3.   i: Integer;
  4. begin
  5.   RandSeed:= 5;
  6.   memo1.Clear;
  7.   mem:= TStringList.Create;
  8.   for i:= 0 to 9 do begin
  9.     mem.Append(IntToStr(Random(100)));
  10.     if CheckBox1.Checked then
  11.       mem.Sort;
  12.     memo1.Append(IntToStr(Random(100)));
  13.   end;
  14.   mem.Free;


apeoperaio

  • Sr. Member
  • ****
  • Posts: 272
Re: TStringList and Random
« Reply #3 on: November 19, 2018, 03:22:13 pm »
More informative code

Code: Pascal  [Select][+][-]
  1. procedure TForm1.Button1Click(Sender: TObject);
  2. var
  3.   mem: TStringList;
  4.   i: Integer;
  5. begin
  6.   RandSeed:= 5;
  7.   mem:= TStringList.Create;
  8.   try
  9.     for i:= 0 to 9 do
  10.       mem.Append(IntToStr(Random(100)));
  11.     //  doing sort modify the random sequence
  12.     if CheckBox1.Checked then
  13.       mem.Sort;
  14.     //
  15.   finally
  16.     mem.Free;
  17.   end;
  18.  
  19.   memo1.Clear;
  20.   for i:= 0 to 9 do
  21.     memo1.Append(IntToStr(Random(100)));
  22. end;    

wp

  • Hero Member
  • *****
  • Posts: 11857
Re: TStringList and Random
« Reply #4 on: November 19, 2018, 03:34:56 pm »
Again, I cannot reproduce. That the list in reply #2 is different is because the random numbers are called in a different sequence, one for the stringlist, one for the memo. That the second list in the last code is different is due to the fact that RandSeed isn't reset back to 5.

Random numbers are absolutely reproducible when you begin with the same randseed - and don't call Random for another purpose in between.

Please post a compilable demo project which shows the issue, instead of code snippets. (Pack pas, lfm, lpr and lpi files to a single zip which you can upload here via "Attachments and other options").
« Last Edit: November 19, 2018, 05:42:53 pm by wp »

apeoperaio

  • Sr. Member
  • ****
  • Posts: 272
Re: TStringList and Random
« Reply #5 on: November 19, 2018, 06:16:54 pm »
Sorry, here the full project to reproduce the issue.
If the checkbox is checked the second 5 numbers in the random sequence are different.
This means that if, during a random sequence I perform a TStringList.Sort the random sequence change.

wp

  • Hero Member
  • *****
  • Posts: 11857
Re: TStringList and Random
« Reply #6 on: November 19, 2018, 06:41:42 pm »
Thank you. I see it now.

The issue is that the QuickSort  method of TStringList pulls a random number itself, and this one is missing in your sequence.
Here are the first lines of TStringList.QuickSort, you see the "Random" in the last line?:

Code: Pascal  [Select][+][-]
  1. procedure TStringList.QuickSort(L, R: Integer; CompareFn: TStringListSortCompare
  2.   );
  3. var
  4.   Pivot, vL, vR: Integer;
  5.   ExchangeProc: procedure(Left, Right: Integer) of object;
  6. begin
  7.   //if ExchangeItems is override call that, else call (faster) ExchangeItemsInt
  8.   if TMethod(@Self.ExchangeItems).Code = CodePointer(@TStringList.ExchangeItems) then
  9.     ExchangeProc := @ExchangeItemsInt
  10.   else
  11.     ExchangeProc := @ExchangeItems;
  12.  
  13.   if R - L <= 1 then begin // a little bit of time saver
  14.     if L < R then
  15.       if CompareFn(Self, L, R) > 0 then
  16.         ExchangeProc(L, R);
  17.  
  18.     Exit;
  19.   end;
  20.  
  21.   vL := L;
  22.   vR := R;
  23.  
  24.   Pivot := L + Random(R - L); // they say random is best
  25.  
  26. ...

[EDIT]
Re-reading your first post I see that you already knew that. Sorry, I did not.
« Last Edit: November 19, 2018, 07:41:19 pm by wp »

lucamar

  • Hero Member
  • *****
  • Posts: 4219
Re: TStringList and Random
« Reply #7 on: November 19, 2018, 07:13:59 pm »
Well, this is curious. It doesn't happen with a (slightly modified) demo.

All I did (mainly) is add another memo and direct the output to one or other depending on whether the checkbox is checked. The result can be seen in the adjunct image.


Oops! Revising the code it seems I did a Cut/Paste instead of a Copy/Paste in the worst place. After correcting it *does* indeed reproduce the OP's observations.
« Last Edit: November 19, 2018, 07:23:40 pm by lucamar »
Turbo Pascal 3 CP/M - Amstrad PCW 8256 (512 KB !!!) :P
Lazarus/FPC 2.0.8/3.0.4 & 2.0.12/3.2.0 - 32/64 bits on:
(K|L|X)Ubuntu 12..18, Windows XP, 7, 10 and various DOSes.

Thaddy

  • Hero Member
  • *****
  • Posts: 14204
  • Probably until I exterminate Putin.
Re: TStringList and Random
« Reply #8 on: November 19, 2018, 07:17:01 pm »
A quicksort does not need a random optimization. Other sorts do. Strange.
Anyway one can fix this by storing the randomseed (the last random value) - all in in the quicksort - and restoring it afterwards (To the last random value). The only reason is to approach random distribution (which only makes sense on very large numbers of items)
This is a bug in the quicksort of the stringlist, not the random. The quicksort uses it, the quicksort is responsible to maintain correct PRNG. (which as you guessed is not random....)
« Last Edit: November 19, 2018, 07:19:07 pm by Thaddy »
Specialize a type, not a var.

Almir.Bispo

  • Jr. Member
  • **
  • Posts: 91
  • CSV Comp DB is the Best NoSQL
    • CSV Comp DB (NoSQL)
Re: TStringList and Random
« Reply #9 on: November 19, 2018, 09:35:31 pm »
There is no bug.
The Sort (method ) just make itens order by alfabetic/number order while Random (method) do random position.
Sort is not Random
CSV Comp DB Developer {Pascal Lover}

Zoran

  • Hero Member
  • *****
  • Posts: 1829
    • http://wiki.lazarus.freepascal.org/User:Zoran
Re: TStringList and Random
« Reply #10 on: November 20, 2018, 08:54:47 am »
There is no bug.
The Sort (method ) just make itens order by alfabetic/number order while Random (method) do random position.
Sort is not Random

Quicksort does not need random position when choosing the pivot. Usually aritmetic mean is used for this purpose. Sometimes, even the first or last element is chosen (well, that will make the worst scenario for already sorted list).

@apeoperaio - if you need the stable pseudo-random sequence, better don't use RTL's random, but use Thaddy's Mersenne twister implementation -- http://wiki.freepascal.org/A_simple_implementation_of_the_Mersenne_twister. Then, QuickSort will not interfere with your sequence.

apeoperaio

  • Sr. Member
  • ****
  • Posts: 272
Re: TStringList and Random
« Reply #11 on: November 20, 2018, 09:10:57 am »
Quicksort does not need random position when choosing the pivot. Usually aritmetic mean is used for this purpose. Sometimes, even the first or last element is chosen (well, that will make the worst scenario for already sorted list).

@apeoperaio - if you need the stable pseudo-random sequence, better don't use RTL's random, but use Thaddy's Mersenne twister implementation -- http://wiki.freepascal.org/A_simple_implementation_of_the_Mersenne_twister. Then, QuickSort will not interfere with your sequence.

Additionaly TFPObjectList does not use random to initialize the pivot in quicksort, so it does not affect the random sequence.
@Zoran I actually use the thread safe implementation described in this post http://forum.lazarus.freepascal.org/index.php/topic,42595.15.html

Thaddy

  • Hero Member
  • *****
  • Posts: 14204
  • Probably until I exterminate Putin.
Re: TStringList and Random
« Reply #12 on: November 20, 2018, 01:46:24 pm »
That's the same. Can be that the wiki entry is slightly more up-to-date.
Specialize a type, not a var.

Thaddy

  • Hero Member
  • *****
  • Posts: 14204
  • Probably until I exterminate Putin.
Re: TStringList and Random
« Reply #13 on: November 20, 2018, 02:50:23 pm »
There is no bug.
The Sort (method ) just make itens order by alfabetic/number order while Random (method) do random position.
Sort is not Random
Indeed. But some sorts start at a randomly chosen position. (it is not a pre-sort). As I said: bit of nonsense to have it in a TStringlist sort.
The ratio behind it is not a single sort, but the average of multiple sorts on multiple similar data that already have a possible bias. So it should not be in the TStringlist source.
« Last Edit: November 20, 2018, 02:52:30 pm by Thaddy »
Specialize a type, not a var.

 

TinyPortal © 2005-2018