Text substitution

Is there a better way? I have this feeling in the back of my head that there is. Ignore corner cases for now. I'm more concerned with run-time efficiency, not memory savings. The objective is to replace all occurrences of 'token' in 'input' with 'value'. And there might be off-by-one errors in here, I haven't compiled this yet

string Substitute(string input, string token, string value)
{
integer inLen = llStringLength(token);
integer index;

while ((index = llSubStringIndex(input, token)) != -1)
{
input = llGetSubString(input, 0, index - 1) + value + llGetSubString(input, index + inLen, -1);
}

return input;
}

I don't know about better, but instead of concatenating the substrings, you could use Delete- and InsertString:

input = llInsertString( llDeleteSubString( input, index, index + inLen - 1 ), index, value );

Though if you use this method, you might as well just subtract 1 from inLen when assigning, so the extra math won't need to be done each time through the loop. Yes, I too have occasionally lamented the absence of an llReplaceSubString function, as there is already one for lists.

OK, that's another approach, but you're right, it's basically the same idea. I guess I could benchmark both and see if there's any difference in internal efficiency/implementation in the LSL functions.

I considered walking the string myself character by character, but without C-like array-index-access-to-string-characters semantics, I think that could be much more expensive, since I'll have to call llGetSubString(input, i, i) repeatedly, and I don't know if that's implemented internally as O(1) or O(n). The current way is probably better, assuming the token occurs rarely in the input string.

Thanks.

deanna's if the method I've used, not sure if it's any faster, still 2 calls...

another possible way is to parse the string to a list, with token as a kept seperator, then use list find (or walk the list), and replace token with value, then dump the whole slit back to string...

my thinking was substring index would be faster than all that conversion, but it could make for a nice multi replace function (allowing multiple tokens to be replaced with one, or multiple values)

I'm pretty sure accessing a list element is an O(n) operation within LSL (it walks the list from the front), so I'm guessing that would be more efficient only for the more complex replacements scenarios you described.

I had this nagging feeling that I was missing something obvious (like a built-in string replacement function), so I thought I'd check

I can't remember where I got this, but I've used it with good results. Haven't used it in a while though.

//replaces all occurrences of 'from' with 'to' in 'src'.
string strReplace(string src, string from, string to)
{
integer len = (~-(llStringLength(from)));
if(~len)
{
string buffer = src;
integer b_pos = -1;
integer to_len = (~-(llStringLength(to)));
@loop; //instead of a while loop, saves 5 bytes (and run faster).
integer to_pos = ~llSubStringIndex(buffer, from);
if(to_pos)
{
buffer = llGetSubString(src = llInsertString(llDeleteSubString(src, b_pos -= to_pos, b_pos + len), b_pos, to), (-~(b_pos += to_len)), 0x8000);
jump loop;
}
}
return src;
}

That has Strife Onizuka written all over it

yup.... it's in the combined library on the SL wiki, with a CC_by license but no author listed... still it looks classically Strife, jump loops, -~, hex variables, and naming conventions all fit

Here's a two-function-call method of doing this, but it's kind of ugly:

string Substitute(string input, string token, string value) {
return llDumpList2String(llParseStringKeepNulls(input, [token], []), value);
}

In short, it treats the token as a delimiter when turning the string into a list, and then dumps the list back out, using the replacement value as an output delimiter. Ugly, but efficient. You can also replace multiple tokens with the same replacement value without any extra function calls.

Lex, now that's a different idea. Have you tested this? Have you found it to be more efficient than the string operations approaches? I wonder if that depends on how frequently the token appears in the input string.

And I can never understand Strife's code. I can see there's a delete and an insert. The rest of it seems to be designed to avoid recursion errors where the value contains the token within it, so once a token has been replaced with a value, the next search starts after that match.

I thought about the list approach, but I think it will be less efficient because LSL is notoriously slow handling lists versus other variable types. A benchmark could determine that, though.

Ultimately, it depends on how often you need it to run. Once a second or less often, and it's really moot.

Agreed, and my expected use will be way less than that.

ooo I like neva's approach, a much nicer take on the delimiter problem than I suggested above, and it WILL be going in a script that I'm using that requires list style replacements (for non-obvious reasons)

the reasoning in strifes code was to be able to replace null values according to the combined library page, so it may still be useful even if testing proves other methods faster

I haven't tested my code for efficiency versus string operations, but I have to think it's more efficient. The reason list operations in LSL are so slow is that we're constantly requiring the system to seek through a linked list as if it's an array. Trying to iterate through a list in LSL is O(n^2) because you're requiring the runtime to repeatedly follow the links in the internal linked list. It seems to me (and this is just an educated guess) that my code will be fairly efficient because functions like llParseStringKeepNulls() can be written in C in a much more efficient manner than an LSL function that did the same thing, through the use of pointers and such.

I'd love to see someone test my method, but I'd be willing to bet that, especially on lists with many occurrences of the string to be replaced, and even more in situations where you want to replace two source strings with the same replacement string, my code will win hands-down.

Now that I think about it, I did have a situation at one point where I replaced some code that did string operations with a rather hairy series of four or five calls of code like I posted above, and it made my code run at least ten times as fast.

I tried measuring that once and wasn't able to detect any difference in the amount of time for short lists versus long ones. I might try again; I was measuring more than one thing and might not have got it quite right to single out that aspect.

I used an algorithm that would be O(N^2) but the result was linear. It might have been O(N^2) but overwhelmed by the linear overhead of the LSL for-loops.

IIRC, I went up to hundreds of elements, but not thousands.

Based on measurements I've made, LSL string functions are very fast compared to LSL-coded algorithms, even when the LSL algorithms are in principle much more efficient.

List implementations are supposedly linked lists, so operations will be O(n). Some of the list functions are rather quick, though. I'm particularly fond of llListFindList.

Everything coded in LSL will be sloooooow, there's not really any way around it.

If I understood the code correctly, lists are arrays of pointers, not linked lists.