Nastiest hack of my career

Imagine, you have a list of N variables, some of which are marked empty. You need to randomly select an empty one and return it’s number so that code elsewhere may use it as a slot to put in a non-empty one.

The obvious approach: Make a list of the numbers of the empty ones, randomly select one of these.

Well, it doesn’t work, cause there may be hundreds of them and we’re operating close to memory limits as it is, and a list of 100 integers will chew up 1521 bytes of memory. (…yes, it’s already in Mono, without Mono it wouldn’t be feasible at all.)

The less obvious approach: Keep selecting a random one until you bump into an empty one.

Doesn’t work either, because recursively selecting it takes even more memory, and if you do a while loop instead, with LSL random number generator being what it is, it might stall forever and you’ll never know.

The dirty hack approach: Behold and stare what these bloody people made me do.


integer findspot() {
    string empties = "";
    integer i;
    for (i=0;i<llGetListLength(items);++i) {
        if (llList2Key(items,i) == BLANK) {
            empties += llGetSubString("00"+(string)i,-3,-1);
        }
    }
    integer index = randInt(llStringLength(empties)/3);
    return (integer)llGetSubString(empties,index*3,(index+1)*3-1);
}

That only needs 338 bytes of memory to find an empty spot among 100 items, and actually works. 🙂

Advertisements

2 thoughts on “Nastiest hack of my career

  1. I just find your blog today. Is very good. I always wondered about the copy thingy so I was pleased to read here all about it. So thanks for that =)

    I was looking at this problem here and I not really up with lsl coding to fully understand how your code works. But I think you wanting to work with a permutation set ya ???

    I do a lab last year about this kinda thing and end up using a feistal network to try solve this problem. I not sure if will be useful for you but is quite efficient because you can just start with an empty list and add to it as you go and just use the list index to get ‘encode’ a randomish unique value within the set to pair with the index. And can reverse ‘decode’ the value to return the index of the list item if you want.

    Is in BASIC though =) and I dont know if can be coded in LSL or if it will be at all useful to you. Anyways I copy here just in case. Hope the indenting works)

    [php]
    ‘ a simple arithmetic feistal network
    ‘ to make reversible sets of permutations
    ‘ – can be any factors of maxitems including 1
    ‘ – lofactor can be greater than hifactor
    ‘ – fudge is in the range 0<maxitems
    ‘ – fudge can come from any source
    ‘ – rounds can be anything. more = slower
    ‘ – decoding requires same values as encoding

    global lofactor, hifactor, fudge, rounds

    maxitems = 100 ‘ items to permutate
    lofactor = 5 ‘ a factor of maxitems
    hifactor = 20 ‘ the other factor
    fudge = 43 ‘ add some fudge
    rounds = 4 ‘ number of mixing rounds

    ‘ *** begin test ***

    for i = 0 to maxitems-1
    value = encode (i)
    index = decode (value)
    print i, value, index
    next i

    ‘ *** end test ***

    function encode (index)
    lo = index mod lofactor
    hi = INT (index / lofactor)
    for r = 1 to rounds
    m = hi mod lofactor
    lo = (lo + m * m + fudge) mod lofactor
    m = lo mod hifactor
    hi = (hi + m * m + fudge) mod hifactor
    next r
    encode = hi * lofactor + lo
    end function

    function decode (value)
    lo = value mod lofactor
    hi = INT (value / lofactor)
    for r = 1 to rounds
    m = lo mod hifactor
    hi = (hi – m * m – fudge) mod hifactor
    if hi < 0 then hi = hi + hifactor
    m = hi mod lofactor
    lo = (lo – m * m – fudge) mod lofactor
    if lo < 0 then lo = lo + lofactor
    next r
    decode = hi * lofactor + lo
    end function
    [/php]

Comments are closed.