Jump to content
thirith

BIS_fnc_arrayShuffle - does it work?

Recommended Posts

I've read around a bit and it seems that BIS_fnc_arrayShuffle either was or still is broken. Is that the case? I've not found any clear up-to-date info on the matter. If it's broken, what's the recommended workaround?

Share this post


Link to post
Share on other sites

something like that, works like a charm :don12:

 

New_fnc_shuffle  = {
	private _array = _this;
	private _rand = 0;
	private _count = count(_array) -1;
	for "_i" from 0 to _count do {
		_rand = floor random _count;
		_temp = _array select _i;
		_array set [_i, _array select _rand];
		_array set [_rand, _temp];
	};
	_array;
};

_array = [1,2,3,4,5,6,7,8,9,10];
_result = _array call New_fnc_shuffle;
hintc format ["%1", _result];

 

  • Like 2

Share this post


Link to post
Share on other sites

Thing with just trying is that I don’t have the experience to know if the results would be consistent or if they’d be different if I used a dedicated server etc. I’m a scripting newbie, but I know that there are factors that may influence the results that I’m simply not aware of.

Share this post


Link to post
Share on other sites
25 minutes ago, thirith said:

I've read around a bit and it seems that BIS_fnc_arrayShuffle either was or still is broken. Is that the case? I've not found any clear up-to-date info on the matter. If it's broken, what's the recommended workaround?

 

Where did you find any info that it was broken in the first place? What of the function is supposed to be broken?

Always worked for me, even better since KK reworked it to lightning speeds, something around 0.1ms for shuffling 100 elements if I remember correctly.

 

Cheers

Share this post


Link to post
Share on other sites

It was this thread here: 

 

From the discussion it wasn't clear to me whether there was still a problem (or if there was some confusion in the first place). If it's not an issue, all the better. Thanks!

  • Like 1

Share this post


Link to post
Share on other sites
13 minutes ago, thirith said:

It was this thread here: 

 

From the discussion it wasn't clear to me whether there was still a problem (or if there was some confusion in the first place). If it's not an issue, all the better. Thanks!

Interesting, gonna give it a read, seems this was created after KK modified it?

It's in the troubleshooting forum for some reason, no wonder I missed it.

Thanks for sharing.

 

Cheers

Share this post


Link to post
Share on other sites

As of today (A3 v1.80), BIS_fnc_arrayShuffle looks like this:

Spoiler

/*
	Author: 
		Nelson Duarte, optimised by Killzone_Kid
	
	Description:
		This returns a new array with randomized order of elements from input array
	
	Parameters:
		_this: ARRAY
	
	Returns:
		ARRAY
	
	Example:
	[1, 2, 3] call BIS_fnc_arrayShuffle
	Returns: [2, 3, 1] (For example)
*/

/// --- validate general input
#include "..\paramsCheck.inc"
paramsCheck(_this,isEqualType,[])

_this = +_this;

private _cnt = count _this;

for "_i" from 1 to _cnt do 
{
	_this pushBack (_this deleteAt floor random _cnt);
};

_this 

 

That is, it is still broken in the way that it does not generate a fair shuffle (where all permutations are equally likely).

What this variant does: it takes random element and moves it to back of array, thus after iterations you will have randomized back and ordered (thinned out though) front. The problem is every next random picking can pick from already randomized back too, thus leaving front less randomized.

Consider line

_this pushBack (_this deleteAt floor random _cnt);

To generate truly equally-possible permutations it should have been

_this pushBack (_this deleteAt floor random (_cnt + 1 - _i));

thus only picking from ordered front (of decreasing size) and putting picked element to the back.

 

From the mentioned in linked topic Fisher-Yates shuffle algorithm wiki page:

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

Note picking j from range 0 ≤ j ≤ i, BIS_fnc_arrayShuffle still picks from 0 ≤ j ≤ (n-1) (considering indexes 0 to n-1)

 

 

Also,

_this = +_this;

might not be good enough. Depending on element types,

_this = []+_this;

(shallow copy) can perform better.

  • Like 3

Share this post


Link to post
Share on other sites

I use it often. It was certainly working as expected yesterday

Share this post


Link to post
Share on other sites
9 minutes ago, Tankbuster said:

I use it often. It was certainly working as expected yesterday

And what exactly do you expect from it actually? :)

 

Okay, measuring...

some_array = [];
// filling array with 100 numbers from 0 to 99 sequentially
for "_i" from 0 to 99 do
{
  some_array pushBack _i;
};
zero_on_first = 0;
tests = 10000;
for "_i" from 0 to (tests-1) do
{
  some_array_copy = some_array call BIS_fnc_arrayShuffle;
  if (0 == (some_array_copy select 0)) then {
    zero_on_first = zero_on_first + 1;
  };
};
systemChat format ["First element unchanged %1 times out of %2", zero_on_first, tests];

I expected it would say "First element unchanged 100 times out of 10000" (for equally likely permutations), but it gave me 3664!

  • Like 2
  • Thanks 1

Share this post


Link to post
Share on other sites
8 minutes ago, pedeathtrian said:

And what exactly do you expect from it actually? :)

 

Okay, measuring...


some_array = [];
// filling array with 100 numbers from 0 to 99 sequentially
for "_i" from 0 to 99 do
{
  some_array pushBack _i;
};
zero_on_first = 0;
tests = 10000;
for "_i" from 0 to (tests-1) do
{
  some_array_copy = some_array call BIS_fnc_arrayShuffle;
  if (0 == (some_array_copy select 0)) then {
    zero_on_first = zero_on_first + 1;
  };
};
systemChat format ["First element unchanged %1 times out of %2", zero_on_first, tests];

I expected it would say "First element unchanged 100 times out of 10000" (for equally likely permutations), but it gave me 3664!

 

Neat, was about to do something similar but this really showcases of how broken it actually is. Looks like I got to rework a few scripts then...

 

Also for completion's sake:

 

some_array = [];
// filling array with 100 numbers from 0 to 99 sequentially

NEW_fnc_arrayShuffle = {
	_this = []+_this;

	private _cnt = count _this;

	for "_i" from 1 to _cnt do 
	{
		_this pushBack (_this deleteAt floor random (_cnt + 1 - _i));
	};
	_this 
};

for "_i" from 0 to 99 do
{
  some_array pushBack _i;
};
zero_on_first = 0;
tests = 10000;
for "_i" from 0 to (tests-1) do
{
  some_array_copy = some_array call NEW_fnc_arrayShuffle;
  if (0 == (some_array_copy select 0)) then {
    zero_on_first = zero_on_first + 1;
  };
};
systemChat format ["First element unchanged %1 times out of %2", zero_on_first, tests];

//prints "First element unchanged 90 times out of 10000"

Cheers

  • Like 4

Share this post


Link to post
Share on other sites

i thought for awhile it must not have been working well, but never bothered to look into it after the KK “optimization”

 

thanks for the heads up

Share this post


Link to post
Share on other sites
44 minutes ago, Tankbuster said:

Ouch. So it's not really a good random shuffle.

Time to look for an alternative, like @Grumpy Old Man

 version

 

what i noticed was when gathering building positions in a large area for spawning units, then applying arrayShuffle to it, the units would still end up grouped in the same area/buildings instead of spread out evenly.

  • Like 1

Share this post


Link to post
Share on other sites

Three more performance considerations addressed in some form in wiki page and linked topic:

1. It is actually not necessary to randomise picking last item. By the time there's only one left, the whole sequence is already randomized enough, and moving item from front to back does not add or substrct from its randomness. So you can save one iteration.

2. Removing and inserting items usually considered expensive for arrays (and quite cheap for lists for example). That is for real arrays of items placed consequently in memory. Therefore modern Fisher-Yates algo uses swapping of items (which for lists is quite similar in terms of operations cost as removing and inserting). A3 arrays, however, very well might not be real arrays, so better measure here too. Also, arrays in A3 usually not big enough for algorithmical differences to be significant.

3. Shuffling in place is probably a better option to have rather than returning a shuffled copy. You can always do a copy yourself and shuffle it in-place. BIS_fnc_arrayShuffle was returning shuffled copy from the beginning afair, so it better stay so (people expect it to work that way and no modify passed array). So the best thing is to have other function to shuffle in place.

  • Like 1

Share this post


Link to post
Share on other sites
13 minutes ago, pedeathtrian said:

Two more performance considerations addressed in some form in wiki page and linked topic:

1. It is actually not necessary to randomise picking last item. By the time there's only one left, the whole sequence is already randomized enough, and moving item from front to back does not add or substrct from its randomness. So you can save one iteration.

2. Removing and inserting items usually considered expensive for arrays (and quite cheap for lists for example). That is for real arrays of items placed consequently in memory. Therefore modern Fisher-Yates algo uses swapping of items (which for lists is quite similar in terms of operations cost as removing and inserting). A3 arrays, however, very well might not be real arrays, so better measure here too. Also, arrays in A3 usually not big enough for algorithmical differences to be significant.

 

2 hours ago, Grumpy Old Man said:

 

Neat, was about to do something similar but this really showcases of how broken it actually is. Looks like I got to rework a few scripts then...

 

Also for completion's sake:

 


some_array = [];
// filling array with 100 numbers from 0 to 99 sequentially

NEW_fnc_arrayShuffle = {
	_this = []+_this;

	private _cnt = count _this;

	for "_i" from 1 to _cnt do 
	{
		_this pushBack (_this deleteAt floor random (_cnt + 1 - _i));
	};
	_this 
};

for "_i" from 0 to 99 do
{
  some_array pushBack _i;
};
zero_on_first = 0;
tests = 10000;
for "_i" from 0 to (tests-1) do
{
  some_array_copy = some_array call NEW_fnc_arrayShuffle;
  if (0 == (some_array_copy select 0)) then {
    zero_on_first = zero_on_first + 1;
  };
};
systemChat format ["First element unchanged %1 times out of %2", zero_on_first, tests];

//prints "First element unchanged 90 times out of 10000"

Cheers

 

does _cnt really need to be "private" in the function?

 

also thanks for testing this stuff, looks like its time to update. also a good case-in-point for creating our own alias of BIS functions incase they fix (break) something.

 

can see some of the dumb stuff id tried before, lol

 

https://github.com/auQuiksilver/Apex-Framework/blob/master/Apex_framework.terrain/code/functions/fn_spawnAmbientCivilians.sqf#L121-L123

Share this post


Link to post
Share on other sites
15 minutes ago, fn_Quiksilver said:

 

what i noticed was when gathering building positions in a large area for spawning units, then applying arrayShuffle to it, the units would still end up grouped in the same area/buildings instead of spread out evenly.

That's the weird thing. I use it exactly the same way, and never noticed the same building being used often.

But I'm not going to argue with those findings. Yet again, community betters developers.

Share this post


Link to post
Share on other sites
16 minutes ago, fn_Quiksilver said:

does _cnt really need to be "private" in the function?

 

Functions have access to variables of the scope where they were called.

See:

func1 = {
  _cnt = _cnt + 1;
};

func2 = {
  private _cnt = 2;
  systemChat format ["_cnt = %1", _cnt];
  [] call func1;
  systemChat format ["_cnt = %1", _cnt];
};

[] call func2;

will print 
 

Quote

_cnt = 2
_cnt = 3

even though _cnt was declared private in func2. func1's author might never know how and where it's used and what variable names are used there. So to avoid name clashes local variables in functions MUST be declared private.

 

Now this

func1 = {
  private _cnt /* this one is to be private after this line */ = _cnt /* this is not private */ + 1;
  systemChat format ["f1: _cnt = %1", _cnt];
};

func2 = {
  private _cnt = 2;
  systemChat format ["f2: _cnt = %1", _cnt];
  [] call func1;
  systemChat format ["f2: _cnt = %1", _cnt];
};

[] call func2;

prints what everyone would expect

Quote

f2: _cnt = 2

f1: _cnt = 3

f2: _cnt = 2

 

  • Like 1

Share this post


Link to post
Share on other sites
21 minutes ago, pedeathtrian said:

Three more performance considerations addressed in some form in wiki page and linked topic:

1. It is actually not necessary to randomise picking last item. By the time there's only one left, the whole sequence is already randomized enough, and moving item from front to back does not add or substrct from its randomness. So you can save one iteration.

2. Removing and inserting items usually considered expensive for arrays (and quite cheap for lists for example). That is for real arrays of items placed consequently in memory. Therefore modern Fisher-Yates algo uses swapping of items (which for lists is quite similar in terms of operations cost as removing and inserting). A3 arrays, however, very well might not be real arrays, so better measure here too. Also, arrays in A3 usually not big enough for algorithmical differences to be significant.

3. Shuffling in place is probably a better option to have rather than returning a shuffled copy. You can always do a copy yourself and shuffle it in-place. BIS_fnc_arrayShuffle was returning shuffled copy from the beginning afair, so it better stay so (people expect it to work that way and no modify passed array). So the best thing is to have other function to shuffle in place.

 

As far as 2 goes, some binary or xor swap would be nice to have, yeah. Probably not possible from within .sqf I guess.

18 minutes ago, fn_Quiksilver said:

 

 

does _cnt really need to be "private" in the function?

 

also thanks for testing this stuff, looks like its time to update. also a good case-in-point for creating our own alias of BIS functions incase they fix (break) something.

 

can see some of the dumb stuff id tried before, lol

 

https://github.com/auQuiksilver/Apex-Framework/blob/master/Apex_framework.terrain/code/functions/fn_spawnAmbientCivilians.sqf#L121-L123

 

I just threw this together to get a quick glance at distribution.

 

Cheers

Share this post


Link to post
Share on other sites

You guys rock for noticing this and providing an alternative.   That BI developer probably was a coder on the Video Poker machines in Vegas.  He owes me some money.

  • Like 1

Share this post


Link to post
Share on other sites
5 hours ago, pedeathtrian said:

As of today (A3 v1.80), BIS_fnc_arrayShuffle looks like this

 

Broken shuffle reported in 2016. No big deal.

Still not fixed in 2018... :shhh:

 

I'm not exactly sure why at least the simple stuff can't get fixed in a timely manner, but something (organisation? processes? ...) is just broken/not functional over at BIS.

Isn't it?

 

:toilet:

 

  • Like 3

Share this post


Link to post
Share on other sites

king of DABU code struck again :down:

 

you should dont waste your time on this bunny problem, cause the random internal function is certainly broken (in term of distribution) as the shuffle function. But all give some acceptable but not best results for arma usage.

 

KK wrote a fair simply read / compact code.

 

New_fnc_shuffle that i wrote top, should fix most of problems as it shuffles all entries and not pushback them, i already used some kind of stuff to generate cipher.

 

 

 

Share this post


Link to post
Share on other sites

Welcome to ArmA

  • Haha 1

Share this post


Link to post
Share on other sites

Please sign in to comment

You will be able to leave a comment after signing in



Sign In Now

×