thirith 27 Posted March 21, 2018 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
beno_83au 1362 Posted March 21, 2018 What were your results when you tried it? Share this post Link to post Share on other sites
code34 248 Posted March 21, 2018 something like that, works like a charm 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]; 2 Share this post Link to post Share on other sites
thirith 27 Posted March 21, 2018 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
Grumpy Old Man 3540 Posted March 21, 2018 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
thirith 27 Posted March 21, 2018 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! 1 Share this post Link to post Share on other sites
Grumpy Old Man 3540 Posted March 21, 2018 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
pedeathtrian 99 Posted March 21, 2018 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. 3 Share this post Link to post Share on other sites
Tankbuster 1733 Posted March 21, 2018 I use it often. It was certainly working as expected yesterday Share this post Link to post Share on other sites
HazJ 1288 Posted March 21, 2018 @thirith - Are you talking about: https://forums.bohemia.net/forums/topic/188713-bis_fnc_arrayshuffle-broken/ Share this post Link to post Share on other sites
pedeathtrian 99 Posted March 21, 2018 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! 2 1 Share this post Link to post Share on other sites
Grumpy Old Man 3540 Posted March 21, 2018 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 4 Share this post Link to post Share on other sites
fn_Quiksilver 1633 Posted March 21, 2018 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
Tankbuster 1733 Posted March 21, 2018 Ouch. So it's not really a good random shuffle. Time to look for an alternative, like @Grumpy Old Man version Share this post Link to post Share on other sites
fn_Quiksilver 1633 Posted March 21, 2018 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. 1 Share this post Link to post Share on other sites
pedeathtrian 99 Posted March 21, 2018 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. 1 Share this post Link to post Share on other sites
fn_Quiksilver 1633 Posted March 21, 2018 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
Tankbuster 1733 Posted March 21, 2018 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
pedeathtrian 99 Posted March 21, 2018 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 1 Share this post Link to post Share on other sites
Grumpy Old Man 3540 Posted March 21, 2018 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
johnnyboy 3741 Posted March 21, 2018 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. 1 Share this post Link to post Share on other sites
rübe 127 Posted March 21, 2018 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... 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? 3 Share this post Link to post Share on other sites
code34 248 Posted March 22, 2018 king of DABU code struck again 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