list iteration

I've heard mention that lists in LSL are stored internally as linked lists, meaning that iterating over the list is an O(n^2) operation. I just hit upon what I htink is an O(n) list iteration method. Simply make a copy of the list to iterate (an O(n) operation, I hope), and go through it by repeatedly getting the first element and then removing the first element. I know the internals of the script interpreter are a black box, but I think it's pretty safe to say that accessing and deleting the first element in a list is an O(1) operation.

Thoughts?

Augh. Nightmares of Scheme are plaguing me even as we speak.

What's wrong with Scheme?

No offense, but there is one major flaw with this otherwise elegant idea:

(okay, two major flaws)...

1) This operation is only useful when you don't care that your original list is going to be destroyed.

2) More Importantly - LSL's pass-by-value implementation makes this inherently bad.

Let's say I have a list with 5 items in it.

list myList = [0,1,2,3,4];

I retrieve the first element.

integer myInt = llList2Integer(myList, 0);

Now I need to delete the first element.

myList = llDeleteSubList(myList, 0, 0);

This would seem to do just what we want, right? NOT REALLY!

LSL is a pass by value language. That means that every time we use the "=" sign, or we return a value from a function, an entire copy of the object must be created and handed out!

So when we make that "llDeleteSubList()" call, we are actually doing several things:

1) We create an entirely new, temporary list inside the "llDeleteSubList" function.

2) We pass in the contents of the entire list "myList".

3) We grab every item from the copy of "myList" except the first one, and append each one onto the temp list. We now have a temporary list containing "[1,2,3,4]".

4) We must pass that entire list back to our main code. The "myList" variable must be emptied and re-filled with the values returned from the function.

5) Repeat Steps 1 - 4 for every item in the list.

...So you see, we spend a lot of time creating and filling "temporary" structures and passing large amounts of data back and forth. This is much more time-consuming than iterating through a linked-list.

If LSL was a pass-by-reference sort of language, then perhaps a trick like this would work... However, passing by reference introduces the possibility of a lot of bugs and malicious manipulation of memory pointers; which is why IMHO they didn't do it with LSL.

Sorry to ruin the party.

Take care,

--Noel "HB" Wade
(Tread Whiplash)

That is, deleting the first element is not O(1), it is O(n).

Pass-by-value does not have to be inefficient. Lists are essentially immutable, so LL could possibly implement tail sharing (ala lisp/scheme) to make "deleting" the head of a list O(1), but right now, it does not seem to be the case.

I'd love to be proven wrong....

May i point out that LSL is pass by value? And that by doing so you haven't reduced the problem.

Lets chart it out.

//Set A
list a;
integer b = llGetListLength(a);
integer c;
while(b > c)
    llSay(0,llList2String(a,c++);

//Set B
list a;
integer b = llGetListLength(a);
integer c;
while(b > c)
{
    llSay(0,llList2String(a,0);
    c++
    a = llList2List(a,1,-1);
}

so we can write some equations for how many list entries we need to parse per list lenght.

Set A:
f(b) = b + //from the llGetListLength
((b+1)*b/2) + //the actual copying of that value from the linked list.
b*b //from the copy into llList2String for each iteration

Set B:
g(b) = b + //from the llGetListLength
((b+1)*b/2) + //from the copy into llList2List for each iteration
((b+1)*b/2) - b + //from the result of llList2List for each iteration
((b+1)*b/2) + //from the copy into llList2String for each iteration

//so to simplify
f(b) = (3*b + 3*b*b) / 2
g(b) = (3*b + 3*b*b) / 2

considering that Set A is made up of fewer commands (and less list copying) it should run faster.

temporary lists generated
Set A:
h(b) = 1 + ((b+1)*b/2)

Set B:
k(b) = 1 + 3 * ((b+1)*b/2);

So several of us came up with the same point about pass-by-value at the same time...
Love it!

Strife - I don't want to come off sounding like a pretentious ass, so please forgive me if I do... But I want to point out you're not initializing some variables before using them. I know LSL allows for this, but not a good practice, IMHO.

Flyingroc - Pass by value is inherently less-efficient, whenever you're dealing with data that is larger than a simple memory address would be. The very fact that you are copying these larger hunks of memory is what causes the inefficiency. Any trick or part of a language that "gets around" this, is not pass-by-value; but rather some alternative that's been woven into the language.

...But even if you mark the head of a list so its access is faster, deleting that list item changes everything - either you have to manually copy the values of the list items into the next one up the chain, to preserve the memory locations; or you have to re-calc the memory location of the head of the list. So you still run into inefficiencies with this scheme. *shrug* But now I'm getting way off-topic (and I'm not that familiar with Lisp or Scheme).

Take care,

--Noel "HB" Wade
(Tread Whiplash)

I should've said that because LSL lists are immutable, you could implement it in such a way that passing lists acts functionally equivalent to pass-by-value, but is efficient.

That is, if you had tail-sharing lists, like scheme, you can (internally and invisible to the end-programmer) pass pointers instead of actually copying values, without changing the semantics of the language at all.

In other words, because of how LSL lists behave, you could implement what looks exactly like pass-by-value, but have efficient parameter passing (and assignment!). You cannot do this if lists were mutable (e.g. if they acted like arrays).

Yeah it's a bad practice. But LSL isn't an optimised compiler. You only loose proformance by making code that breaks logic up across multiple lines. 90% of the time the less code that is run the faster your script will run. Script efficentcy is higher on my design goals then is readability of my scripts by others.

I learned to code on a TI-83; this calculator didn't support functions or sub-routines; only jumps (goto). All lables (targets for goto) could be no more then 2 characters. You only had global lettered variables. We are talking about a language that makes QBasic look like a high level language. I've never really lost the ability to keep lettered variables sorted in my head. I almost never use them for globals. Usualy they are temp varriables. I've never been good at naming varriables (on a semi related topic I had a cat that we all called "The grey cat" as we never did choose a name for him).

Strife - a TI-83? Hah! I was learning programming in 1983! Look up "TI-994A" in the history-books. It was a little larger than a calculator

Actually, I mostly learned on a Commodore64, with BASIC (before QBasic existed). At least it had 64kb of RAM - 4 times what we get for scripts.

Of course, at age 7, I wasn't exactly programming anything complex... But then again, having to manually set the value of each pixel individually with "POKE" and "PEEK" commands kinda stretched my patience, at that age.

*gets out his "old man cane"* At 27, I'll still show you whipper-snappers a thing or two!


Okay, really off-topic now, sorry...


Take care,

--Noel "HB" Wade
(Tread Whiplash)

Nah.. I said make a copy, and I said that'd take O(n). I was suggesting to make a copy of the list that would be chopped up.



Oop, right, there's O(n^2) again. Damn. Oh well. It was just a random idea that floated across my mind anyway.




Heh, no worries, I tossed it out here to see if anyone would find a hole in it. You've done an admirable job

OMG Tread! I still have my TI-994A.