Author Topic: scramble_array()  (Read 4265 times)

Offline cratylus

  • Your favorite and best
  • Administrator
  • ***
  • Posts: 1024
  • Cratylus@Dead Souls <ds> np
    • View Profile
    • About Cratylus
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

Offline cratylus

  • Your favorite and best
  • Administrator
  • ***
  • Posts: 1024
  • Cratylus@Dead Souls <ds> np
    • View Profile
    • About Cratylus
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

Offline wodan

  • BFF
  • ***
  • Posts: 434
  • Drink and code, you know you want to!
    • View Profile
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 :)

Offline cratylus

  • Your favorite and best
  • Administrator
  • ***
  • Posts: 1024
  • Cratylus@Dead Souls <ds> np
    • View Profile
    • About Cratylus
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

Offline chaos

  • BFF
  • ***
  • Posts: 291
  • Job, school, social life, sleep. Pick 2.5.
    • View Profile
    • Lost Souls
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;
}

Offline Aidil

  • Friend
  • **
  • Posts: 50
    • View Profile
    • Way of the Force
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

Offline chaos

  • BFF
  • ***
  • Posts: 291
  • Job, school, social life, sleep. Pick 2.5.
    • View Profile
    • Lost Souls
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;
}

Offline Ave

  • Acquaintance
  • *
  • Posts: 2
    • View Profile
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.

How about:
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

Offline Archaegeo

  • Acquaintance
  • *
  • Posts: 33
    • View Profile
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.

Offline wodan

  • BFF
  • ***
  • Posts: 434
  • Drink and code, you know you want to!
    • View Profile
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.

How about:
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