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(N²). 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*log₂(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. Whether 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 * log₂(N) + 1)

Of course this comes at a huge memory cost. You should eliminate all "DEBUG:Self" lines. If you want you can chuck clear and setup. Remove "DEBUG:Usage" after your code works. <lsl> integer chunk = 0; list buffer; string last; integer cost; //DEBUG:Self

string getNext() {

   last = llList2String(buffer, -1); //This can be made local and the global "last" eliminated. Don't forget to mod setup and clear.
   buffer = llDeleteSubList(buffer, -1, -1);
   integer size = llStringLength(last);
   cost += ((size + chunk - 1) / chunk); //DEBUG:Self
   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:Self
           buffer += llGetSubString(last, split, -1);
           last = llDeleteSubString(last, split, -1);
           split = (size = split) >> 1;
       } while(size > chunk);
   }
   else if (!size) chunk = 0;//This line can be eliminated if you don't use chunk to test for readiness
   return last;

}

setup(string str, integer size) { //This function can be eliminated, just inline the setup of buffer and chunk.

   if(!chunk) llOwnerSay("Warning: Buffer may still be in use!"); //DEBUG:Usage
   buffer = [str];
   chunk = size;
   last = "";
   cost = 0; //DEBUG:Self
   size = (llStringLength(str) + chunk - 1) / chunk; //DEBUG:Self
   llOwnerSay("Flat: " + ((size * (size + 1)) / 2) + "   Chunks: " + chunk); //DEBUG:Self

}

clear() { //This function can be eliminated or inlined. If you don't depend upon chunk or last then you can eliminate it.

   chunk = 0;
   last = "";

}

default {

   state_entry()
   {
       setup("12341234123412341234123412341234123412341234123412341234123412341234123412341234123412341234123412341234123412341234123412341234", 1);
       string value;
       while(value = getNext())
           ;//llOwnerSay(value);
       llOwnerSay("Cost: " + cost);
   }

} </lsl>