User:Strife Onizuka/String Tree
This is just a bit of silliness, it's sanity has not been vetted. The purpose of this code is to look at the costs of splitting a string into chunks of a specific size. The problem with getting all sequential chunks of a specific set size is that doing so is O(N2). This script hopes to reduce that. As previously stated, I have no idea if it does. It probably doesn't. I'm hoping for something like O(N*log2(N)).
Results: It works! At 25 chunks you break even between just doing flat llGetSubString vs this. Changing how split is done will improve that. Weather or not it's faster I don't know, I've been running this in LSLEditor. My goal has been to reduce read bottlenecks on the string. The cost equation appears to be N * (2.5 * log2(N) + 1) <lsl> integer chunk = -1; list buffer; string last; integer cost; //DEBUG
string getNext() {
last = llList2String(buffer, -1);
buffer = llDeleteSubList(buffer, -1, -1);
integer size = llStringLength(last);
cost += ((size + chunk - 1) / chunk); //DEBUG
if(size > chunk) {
//The advantage of keeping the tree unbalanced this way is that split only needs to be cleverly calculated once.
integer split = (1 << (llCeil(llLog((size + chunk - 1) / chunk) * 1.4426950408889634073599246810019) - 1)) * chunk;
do {
cost += ((size + chunk - 1) / chunk) * 2; //DEBUG
buffer += llGetSubString(last, split, -1);
last = llDeleteSubString(last, split, -1);
size = split;
split = split >> 1;
} while(size > chunk);
} else if (!size)
chunk = -1;
return last;
}
setup(string str, integer size) {
if(~chunk) llOwnerSay("Warning: Buffer may still be in use!"); //DEBUG
buffer = [str];
chunk = size;
cost = 0; //DEBUG
size = (llStringLength(str) + chunk - 1) / chunk; //DEBUG
llOwnerSay("Flat: " + ((size * (size + 1)) / 2) + " Chunks: " + chunk); //DEBUG
}
clear() {
chunk = -1;
}
default {
state_entry()
{
setup("12341234123412341234123412341234123412341234123412341234123412341234123412341234123412341234123412341234123412341234123412341234", 1);
string value;
while(value = getNext())
;//llOwnerSay(value);
llOwnerSay("Cost: " + cost);
}
} </lsl>