Author Topic: scramble_array()  (Read 4265 times)

cratylus

• Posts: 1024
scramble_array()
« on: January 04, 2008, 11:04:30 pm »
In response to a discussion on intermud, array scrambling code that works for me:

Code: [Select]
`mixed *scramble_array(mixed *arr){    mixed *ret = copy(arr);    size_of_array = sizeof(arr);    ret = sort_array(ret, (:random(size_of_array)-1:) );    return ret;}`
-Crat

cratylus

• Posts: 1024
Re: scramble_array()
« Reply #1 on: January 04, 2008, 11:06:08 pm »
PS: size_of_array is a global int. sorry bout that...

-Crat

wodan

• BFF
• Posts: 434
• Drink and code, you know you want to!
Re: scramble_array()
« Reply #2 on: January 05, 2008, 10:08:53 am »
considering that sort_array expect -1, 0 and 1 from the functional, i have some doubts about the randomness you get with random(size)-1

cratylus

• Posts: 1024
Re: scramble_array()
« Reply #3 on: January 05, 2008, 10:37:59 am »
Quote
considering that sort_array expect -1, 0 and 1 from the functional, i have some doubts about the randomness you get with random(size)-1

Agreed. This is an example of why you should never
code while drunk.

-Crat

chaos

• BFF
• Posts: 291
• Job, school, social life, sleep. Pick 2.5.
Re: scramble_array()
« Reply #4 on: January 07, 2008, 10:03:25 am »
Code: [Select]
`mixed array shuffle(mixed array list) {    mixed array out = ({});    for(int ix = sizeof(list); ix > 0; ix--) {        int which = random(ix);        out += ({ list[which] });        list[which..which] = ({});    }    return out;}`

Aidil

• Friend
• Posts: 50
Re: scramble_array()
« Reply #5 on: January 08, 2008, 03:33:28 pm »
That might be quite a bit more efficient, esp on large arrays, considering how sort_array scales.

Code: [Select]
`mixed array shuffle(mixed array list) {    mixed array out = ({});    for(int ix = sizeof(list); ix > 0; ix--) {        int which = random(ix);        out += ({ list[which] });        list[which..which] = ({});    }    return out;}`
Way of the Force

A Star Wars LPMud
wotf.org port 23

chaos

• BFF
• Posts: 291
• Job, school, social life, sleep. Pick 2.5.
Re: scramble_array()
« Reply #6 on: January 08, 2008, 06:54:04 pm »
Test results would be fascinating.  If you want actual efficiency, though, this is better:

Code: [Select]
`mixed array shuffle(mixed array list) {    mixed array out = allocate(sizeof(list));    for(int ix = sizeof(list); ix > 0; ix--) {        int which = random(ix);        out[ix - 1] = list[which];        list[which..which] = ({});    }    return out;}`

Ave

• Acquaintance
• Posts: 2
Re: scramble_array()
« Reply #7 on: January 09, 2008, 04:29:10 pm »
Right... if you want some better efficiency, get rid of what you don't need.

Code: [Select]
`mixed array shuffle(mixed array list){    mixed array out = allocate(sizeof(list));    for(int ix = sizeof(list); ix > 0; --ix)    {        out[ix - 1] = list[which];    }    return out;}`
Get rid of the creation of variables within the loop, my testcase shaved 100ms from removing the int which, and the assignments for it. But the biggest save is the new array for every iteration created by ({}) (is there any reason to fill the original array with empty arrays?)
Removing list[which..which] = ({}); also cuts away 68000ms... yes, 68 seconds!
The code example above runs in 630ms on my slow machine.
My testcase:
Integer array of size 30000, randomized 10 times in a row. (so a total of 300,000 iterations).

// Ave

Archaegeo

• Acquaintance
• Posts: 33
Re: scramble_array()
« Reply #8 on: January 09, 2008, 09:00:20 pm »
You might save even more if you moved away from mixed and called made a scamble_int_array, scramble_string_array, etc. Mixed has to get analyzed.

wodan

• BFF
• Posts: 434
• Drink and code, you know you want to!
Re: scramble_array()
« Reply #9 on: January 10, 2008, 05:14:59 am »
Right... if you want some better efficiency, get rid of what you don't need.

Code: [Select]
`mixed array shuffle(mixed array list){    mixed array out = allocate(sizeof(list));    for(int ix = sizeof(list); ix > 0; --ix)    {        out[ix - 1] = list[which];    }    return out;}`
Get rid of the creation of variables within the loop, my testcase shaved 100ms from removing the int which, and the assignments for it. But the biggest save is the new array for every iteration created by ({}) (is there any reason to fill the original array with empty arrays?)
Removing list[which..which] = ({}); also cuts away 68000ms... yes, 68 seconds!
The code example above runs in 630ms on my slow machine.
My testcase:
Integer array of size 30000, randomized 10 times in a row. (so a total of 300,000 iterations).

// Ave

how did you get those times? that bit of code won't compile
also you'll find that your resulting array isn't a shuffled variant from the start one even if you replaced the which with random(ix).
this is because list[which..which] = ({}); actually removes the item being placed, well, i think it does, can't test that from work. anyway removal is needed otherwise you just keep copying the same values in multiple places.

removing from arrays is also very expensive, so it's actually better to do it a bit differently

see f_shuffle() in packages/dwlib.c in your fluffos release, it'll be in contrib.c instead in 2.9