Text-handling experiment in Design Philosophy

ID:151644
 
Oct 30 2009, 4:39 am (Edited on Nov 1 2009, 4:33 am)
I have been doing a little experimenting with text-handling and I've managed to create two functions: reversing text and scrambling text. I wanted to know if these functions are fine the way they are, or if they could be improved.

proc
    text_scramble(string)

        if(string)
            var
                oldstring = string
                newstring
                copy_pos
                rand_character

            for(var/textleft = length(oldstring), textleft, textleft --)
                copy_pos = rand(1,textleft)
                rand_character = copytext(oldstring, copy_pos, copy_pos+1)

                newstring += rand_character
                oldstring = copytext(oldstring, 1, copy_pos) + copytext(oldstring, copy_pos+1, 0)

            return newstring


    text_reverse(string)

        if(string)
            var/newstring

            for(var/textleft = length(string), textleft, textleft --)
                newstring += copytext(string, textleft, textleft+1)

            return newstring
#1 Oct 30 2009, 5:53 am
 
proc/reverse_text(var/string)
    var/newString = ""
    for(var/i = length(string) to 1)
        newString += copytext(string, i, i+1)
    return newString

proc/scramble_text(var/string)
    var
        list/oldStringList[0]
        newString = ""
        char

    for(var/i = 1 to length(string))
        oldStringList.Add(copytext(string, i, i+1)
    while(oldStringList.len)
        char = pick(oldStringList)
        newString += char
        oldStringList.Remove(char)

    return newString

That's probably what I would do. Not much different to what you have. I don't know if you would call it much improved, even if you optimized a bit more. It's fine.
#2 Oct 31 2009, 3:32 pm
You don't need to include the special case for copying the last character, as length+1 is the same as 0.

Additionally, scramble() doesn't need two loops. You can do it in-place by repeatedly picking a random number between 1 and length and appending that to the result.
#3 Oct 31 2009, 5:31 pm
In response to Garthor (#2)
The reason I decided to go with a list, which required two loops (one to create the list and one to use it) is that otherwise you end up with 3 calls to copytext().

If I recall correctly, the source for Byond is mostly (if not entirely) in C++, and, according to my understanding of it, C++ uses null terminated strings. This means that each call to copytext is O(n) and you have three calls to it for every randomly chosen number.

I'm not sure how Byond handles removing elements from lists, but as long as picking an element is O(n) and removing it is O(c) (which might not be the case), then that's O(n) twice over instead of three times.

Normally I'm not so picky about efficiency, but text manipulation can bog things down if you do a lot of it. If this does give a 30% efficiency increase, it might be worth it.
#4 Oct 31 2009, 6:16 pm
Would you mind if I used these as a sort of password/name generator for personal use?
#5 Nov 1 2009, 3:05 am
In response to Vic Rattlehead (#4)
Vic Rattlehead wrote:
Would you mind if I used these as a sort of password/name generator for personal use?

OK, I guess
#6 Nov 1 2009, 3:11 am
In response to Garthor (#2)
Garthor wrote:
You don't need to include the special case for copying the last character, as length+1 is the same as 0.

Okay, done

Garthor wrote:
Additionally, scramble() doesn't need two loops. You can do it in-place by repeatedly picking a random number between 1 and length and appending that to the result.

I'll see what I can do
#7 Nov 1 2009, 4:17 am (Edited on Nov 1 2009, 4:33 am)
In response to Garthor (#2)
Indeed as Loduwijk said, it took three uses of copytext to have only one loop in the scramble_text function:

proc
    text_scramble(string)

        if(string)
            var
                oldstring = string
                newstring
                copy_pos
                rand_character

            for(var/textleft = length(oldstring), textleft, textleft --)
                copy_pos = rand(1,textleft)
                rand_character = copytext(oldstring, copy_pos, copy_pos+1)

                newstring += rand_character
                oldstring = copytext(oldstring, 1, copy_pos) + copytext(oldstring, copy_pos+1, 0)

            return newstring


    text_reverse(string)

        if(string)
            var/newstring

            for(var/textleft = length(string), textleft, textleft --)
                newstring += copytext(string, textleft, textleft+1)

            return newstring


Is this truly more efficient than using two loops and one call for copytext, though?
#8 Nov 1 2009, 4:56 am
In response to Nielz (#7)
Nah, I prefer the one with two loops.
It is simpler, really.
#9 Nov 1 2009, 5:05 am
In response to Jemai1 (#8)
In the end, efficiency in processing power is more important, though
#10 Nov 1 2009, 8:40 am
In response to Nielz (#9)
That depends on how often these functions will be used.

As for if it's more efficient, I talked about that in my post as well. That depends on various things which I'm unsure of.

In the end though, the difference is not very significant. It's certainly not worth wasting your time pondering over which is better. At that point, it's not worth it even if you did figure it out. For things this small (again, that is assuming it's not getting used 1000 times every second all the time), you generally just pick one and move on and don't look back.