Binary search

Hi!
Has anyone implemented a binary search (or any search method faster than linear search) over a list of strings?

Is llListFindlist the only option?

Rael

Well, AFAIK even accessing a single element of a list is essentially linear, because the internal code walks the list from the front. So you can't really implement a binary search on top of that... well you could have the LSL code for it, but I don't think you'd get O(log(n)) performance. I could be wrong though.

Sigh I feared that.

Let's say you have a chat operated object and a long list of commands (not an unusual situation). I would like to minimize the time spent in matching the input with the commands list.

I thought of one possible solution, I'd welcome any feedback!

I create a file in RL with the list of commands and parse it with an AWK script that emits lsl code that implement a binary search on that list.

The basic idea is to hash the commands, sort them according that hash and emit lsl code to be embedded into the script manually.

PRO: faster than searching on long (say 200 elements) lsl lists.
CON: needs manual activity in RL, making harder to update/modify/read the code.
hash may collide (well if we hash even 1000 strings on 2^32 hash code we have to be very very unlucky to get a collision, provided the hash function is a decent one)!

Any comments?

I have found llListFindList adequate for lists of upto 200-300 items.
If you get really complex / long input you could try using seperate lists or even seperate scripts.

IMHO you'll get more speed out of your code by not using lists at all, but by repeatedly matching against a set of string constants. I normally do this in a separate function. As soon as I find a match I do the associated action and exit that function. You put the most often used string constants first. Not the way taught in programming 101 but it works in sl.

If you use lists, you need to watch available memory. Also, when you do get your value, you still need to determine what action to take.

OTOH ll list manipulation calls should be running at full speed and should be used where ever possible. Any implementation using equivalent script code runs at a very small fraction of the native code. Hopefully mono will change all that.

Yep I now have this long sequence of if (each with its own return to avoid the nasty if/else limitation!
I think it's just myself, but having to go through 200 if conditions rather than 7/8 somehow seems wrong to me.

I'm not that happy that LL is planning to move toward C# (my preference would be toward LUA or at least Python or Ruby) but I'm starting thinking that anything will be better than LSL!

Rael

C# ???? when/where was that mentioned?

I have used the lenght on long command lists.

    integer msgLen = llStringLength(command);
    if (msgLen == 3){
          if (command == "one"){
                    //do something
          }else if (command == "two"){
                    //do something
          }else if (command == "six"){
                    //do something
          };
    }else if (msgLen == 4){
          if (command == "four"){
                    //do something
          }else if (command == "five"){
                    //do something
          }else if (command == "nine"){
                    //do something
          }else if (command == "zero"){
                    //do something
          };
    }else if (msgLen == 5){
          if (command == "three"){
                    //do something
          }else if (command == "seven"){
                    //do something
          }else if (command == "eight"){
                    //do something
          };
    }; //msgLen 

edit:


They have said they plan on converting the interperter (in the sim) into a mono converter and compiler.

My initial intention was to generate binary search as:

   if (cmd < "four") {
  }
  else if (cmd > "four") {
  }
  else // handle cmd four

Than I've been told that strings can only be compared for equality with == that's why I reverted to hashing the commands.


I can't remember exactly but I'm pretty sure I've heard it (possibly the lisbsl site?).

I can imagine every nasty things happening for not having C# correctly sandboxed that's why I would have preferred a proper, fast, well established in the gaming industry scripting language!!

But I'm not a C# expert so I leave it to those who know it better then me!

Rael

There are a couple of script library functions for string compares.

Another idea is to generate an integer value for each string (similar to a hash really) and use numeric compares.

Where the data is fixed I usually generate integer ID's for each item for that very purpose.

Going to Mono doesn't mean going towards C#. C# is one front-end language into the .NET/Mono Common Language Runtime framework, and is not required to use it. LSL will still be pretty much the same LSL we all know and love after the switch to Mono.

It *MAY* mean that you will be able to use C#, or Python, or Object Pascal, or whatever your favorite language is instead, but that may not be one of the first capabilities available, as it will require additional work to provide the capability to us.