A scripting competition - a sorting alghorithm

[Legacy_Shadooow]

               

BTW I made a different approach to create a "list". Called it linked list. See here for details.

               
               

               
            

[Legacy_Shadooow]

               

Okay, not a surprise to me that nobody took the challenge.

 

There are my results:

 

improved bubble sort by me: 95(+-5) elements before TMI

insert sort: 385(+-10) elements before TMI

 

Some remarks:

 

The "linked list" implementation which I made later for unlimited number of elements in list seems to be bit less efficient than my first version as it needs to re-link swapped elements and also join strings which the character one does not. I used same bubble sort algorithm on both "character list" and "linked list" with the same values and the linked list sorted 1-2 less elements before TMI.

 

Due to this result, it seems that the TMI error works on NWScript basic rather than low-level, because the string operations should be more expensive than bunch of GetLocals and SetLocals.

 

The "linked list" implementation doesn't allow insert sort at all. EDIT: The linked list doesn't allow the halvening insert sort algorithm which is what I used. I didn't tried it but I expect significant drop there.

 

Since the insert sort overcome the maximum number of elements my "character list" allowed I had to improve it by using two characters for single element. This increased the maximum size to be something around 25-40k elements based on how many characters is nwn able to use. While not unlimited I think this new implementation surpass the "linked list" and makes it redundant as its more efficient and allows indexed access without any loops.

               
               

               
            

[Legacy_meaglyn]

               

I was working on this. Actually, I did most of what I was going to do already.  

 

I'm impressed with the insertion sort results.

 

I went with a non-recursive merge sort.

 

With your list code (the 160 character one - which is actually 159.), by copying to a plain array  A0...AN on the module I get 159 and can't go farther. due to the data structure's limit. 

 

I did the same thing with pg_list_i lists (from Paul Speed's zdlg code). This topped out at 191. 

 

If I change the initialization and start with the data in the A0 array and print it from that instead of putting it back into the list it does 240. So while being more efficient in average time the merge sort is clearly longer in terms of instructions.

 

I was planning to do one more test where I use a hybrid approach using the data in the list and just the B array as an array. The initial mergesort using the list code directly and a list for temporary storage failed fairly quickly, 62 I think, but that was with the first pseudo list code.

 

 

>Due to this result, it seems that the TMI error works on NWScript basic rather than low-level, because the string operations should be more >expensive than bunch of GetLocals and SetLocals.

 

I'm not sure what you mean by NWNScript basic rather than low-level. Instructions are instructions.  But I think it depends on the particular string operation. Some of them are system calls, it's the ones that aren't, that are in string libraries, that cost a lot in instruction count.

 

This was fun though. Thanks, and nice job on the insertion sort.

               
               

               
            

[Legacy_Shadooow]

               

What is really interesting is how small optimizations affect the result.

 

Ive tried to improve my insert sort alghorithm and optimize it to get better results. Instead however, I end up with worse result. See the code below:

 

my initial insert sort alghorith:

void SortListIntegerValues6(object oList)
{
string list = GetLocalString(oList,"LIST");
int num = GetStringLength(list)/2;
string list_new = GetStringLeft(list,2);
int num_new = 1;
string char_new, charthis;
int valthis;
int min,max,th, n = 1;
 while(n < num)
 {
 charthis = GetSubString(list,n++*2,2);
 valthis = GetLocalInt(oList,charthis);
 min = 0;
 max = num_new;
  while(TRUE)
  {
  th = (max+min+1)/2;
  char_new = GetSubString(list_new,(th-1)*2,2);
   if(valthis > GetLocalInt(oList,char_new))
   {
    if(th == 1 || valthis < GetLocalInt(oList,GetSubString(list_new,(th-2)*2,2)))
    {
    list_new = GetStringLeft(list_new,(th-1)*2)+charthis+char_new+GetStringRight(list_new,(num_new-th)*2);
    break;
    }
   max = th;
   }
   else
   {
    if(th == num_new || valthis > GetLocalInt(oList,GetSubString(list_new,th*2,2)))
    {
    list_new = GetStringLeft(list_new,(th-1)*2)+char_new+charthis+GetStringRight(list_new,(num_new-th)*2);
    break;
    }
   min = th;
   }
  }
 num_new++;
 }
//SetLocalString(oList,"LIST",list_new);
SpeakString("FINISHED");
}

First attempt to optimize it:

void SortListIntegerValues7(object oList)
{
string list = GetLocalString(oList,"LIST");
int num = GetStringLength(list);
string list_new = GetStringLeft(list,2);
int num_new = 1;
string char_new, charthis;
int valthis;
int min,max,th, n = 2;
 while(n < num)
 {
 charthis = GetSubString(list,n,2);
 valthis = GetLocalInt(oList,charthis);
 min = 0;
 max = num_new;
  while(TRUE)
  {
  th = (max+min+1)/2;
  char_new = GetSubString(list_new,(th-1)*2,2);
   if(valthis > GetLocalInt(oList,char_new))
   {
    if(th == 1 || valthis < GetLocalInt(oList,GetSubString(list_new,(th-2)*2,2)))
    {
    list_new = GetStringLeft(list_new,(th-1)*2)+charthis+char_new+GetStringRight(list_new,(num_new-th)*2);
    break;
    }
   max = th;
   }
   else
   {
    if(th == num_new || valthis > GetLocalInt(oList,GetSubString(list_new,th*2,2)))
    {
    list_new = GetStringLeft(list_new,(th-1)*2)+char_new+charthis+GetStringRight(list_new,(num_new-th)*2);
    break;
    }
   min = th;
   }
  }
 num_new++;
 n+= 2;
 }
//SetLocalString(oList,"LIST",list_new);
SpeakString("FINISHED");
}

Because this failed I tried different approach:

void SortListIntegerValues8(object oList)
{
string list = GetLocalString(oList,"LIST");
int num = GetStringLength(list)/2;
string list_new = GetStringLeft(list,2);
string char_new, charthis;
int valthis;
int num_new,min,max,th, n = 1;
 while(n < num)
 {
 charthis = GetSubString(list,n++*2,2);
 valthis = GetLocalInt(oList,charthis);
 min = 0;
 max = ++num_new;
  while(TRUE)
  {
  th = (max+min+1)/2;
  char_new = GetSubString(list_new,(th-1)*2,2);
   if(valthis > GetLocalInt(oList,char_new))
   {
    if(th == 1 || valthis < GetLocalInt(oList,GetSubString(list_new,(th-2)*2,2)))
    {
    list_new = GetStringLeft(list_new,(th-1)*2)+charthis+char_new+GetStringRight(list_new,(num_new-th)*2);
    break;
    }
   max = th;
   }
   else
   {
    if(th == num_new || valthis > GetLocalInt(oList,GetSubString(list_new,th*2,2)))
    {
    list_new = GetStringLeft(list_new,(th-1)*2)+char_new+charthis+GetStringRight(list_new,(num_new-th)*2);
    break;
    }
   min = th;
   }
  }
 }
//SetLocalString(oList,"LIST",list_new);
SpeakString("FINISHED");
}

And just for curiosity I tried what happens if I use subroutine function instead of direct system call see here:

string GetElement(string list, int nTh)
{
return GetSubString(list,nTh*2,2);
}

void SortListIntegerValues9(object oList)
{
string list = GetLocalString(oList,"LIST");
int num = GetStringLength(list)/2;
string list_new = GetStringLeft(list,2);
string char_new, charthis;
int valthis;
int num_new,min,max,th, n = 1;
 while(n < num)
 {
 charthis = GetElement(list,n++);
 valthis = GetLocalInt(oList,charthis);
 min = 0;
 max = ++num_new;
  while(TRUE)
  {
  th = (max+min+1)/2;
  char_new = GetSubString(list_new,(th-1)*2,2);
   if(valthis > GetLocalInt(oList,char_new))
   {
    if(th == 1 || valthis < GetLocalInt(oList,GetSubString(list_new,(th-2)*2,2)))
    {
    list_new = GetStringLeft(list_new,(th-1)*2)+charthis+char_new+GetStringRight(list_new,(num_new-th)*2);
    break;
    }
   max = th;
   }
   else
   {
    if(th == num_new || valthis > GetLocalInt(oList,GetSubString(list_new,th*2,2)))
    {
    list_new = GetStringLeft(list_new,(th-1)*2)+char_new+charthis+GetStringRight(list_new,(num_new-th)*2);
    break;
    }
   min = th;
   }
  }
 }
//SetLocalString(oList,"LIST",list_new);
SpeakString("FINISHED");
}

Ive initialized a list of 380 elements and ran each of these scripts on it, removing one random element at the time till it write FINISHED.

 

And the results were:

 

sort8: 379

sort6: 377

sort7: 374

sort9: 373

 

The bad result of the 7 really troubles me, I expected a save of a (1+number_of_elements) number of instructions and its actually even worse...

 

Can someone brought some light to this?

               
               

               
            

[Legacy_meaglyn]

               

After I saw your results it occurred to me that the function call depth allowed by NWN script (32 I think) is plenty to handle recursion for the number of items we're talking about. There are generally logN calls so that's around 8 for lists this size.  So I put in a simple quicksort, using the integer arrays not any of the list implementations.   This gets me 439 before TMI (interestingly if I sort in ascending order I get 441, there was a similar difference with merge sort). 

               
               

               
            

[Legacy_Shadooow]

               

After I saw your results it occurred to me that the function call depth allowed by NWN script (32 I think) is plenty to handle recursion for the number of items we're talking about. There are generally logN calls so that's around 8 for lists this size.  So I put in a simple quicksort, using the integer arrays not any of the list implementations.   This gets me 439 before TMI (interestingly if I sort in ascending order I get 441, there was a similar difference with merge sort). 

Well in this case, when the array/list holds only one value, the array implementation is going to produce better results most of the time, as long as it uses alghorithm that doesnt need to insert and therefore renumber elements - which is a case of the InsertSort. So you cannot really compare the results on an array with result on the list. As each works differently. When there would be array in an element, the array implementation wouldnt be an option at all.

 

But, we could make the challenge to be also "choose implementation and algorithm that will sort most elements of this content without TMI" within the same script execution in which case you are a winner now and its interesting that it trumps the insertsort.

 

Anyway, can you post your code for the mergesort and quicksort?

               
               

               
            

[Legacy_meaglyn]

               

Well in this case, when the array/list holds only one value, the array implementation is going to produce better results most of the time, as long as it uses alghorithm that doesnt need to insert and therefore renumber elements - which is a case of the InsertSort. So you cannot really compare the results on an array with result on the list. As each works differently. When there would be array in an element, the array implementation wouldnt be an option at all.

 

But, we could make the challenge to be also "choose implementation and algorithm that will sort most elements of this content without TMI" within the same script execution in which case you are a winner now and its interesting that it trumps the insertsort.

 

Anyway, can you post your code for the mergesort and quicksort?

 

I can't quite parse what you are saying about arrays and single values above. Yes, I know it's not in the list format given. If I have time I'll setup a copy version and see what it does starting with the list and putting it back into the list. There's nothing in the rules about actually using the given list in the algorithm, just starting with it and ending with it '>

 

It's not too surprising that quicksort is shorter than insertion sort.  The average case time complexity for insertion sort is N-squared, whereas it's NlogN for quicksort. (so is mergesort, but the non-recursive version does more instructions per iteration).

 

I'll work on posting the code.

               
               

               
            

[Legacy_meaglyn]

               

Where do I get your list code that handles enough entries? I tried basic list library v3, but that just removes the find stuff.

               
               

               
            

[Legacy_Shadooow]

               

There's nothing in the rules about actually using the given list in the algorithm, just starting with it and ending with it '>

Oh yes, if thats what you are doing its absolutely fine and allowed! Good catch. Would love to see your script.

 

It's not too surprising that quicksort is shorter than insertion sort.  The average case time complexity for insertion sort is N-squared, whereas it's NlogN for quicksort. (so is mergesort, but the non-recursive version does more instructions per iteration).

Well but im using the "halving the interval" method which should be way better than that.

And yes due to the result i posted the recursive method will be always bit worse due to the overhead costs for the calling new function and passing arguments.

 

Where do I get your list code that handles enough entries? I tried basic list library v3, but that just removes the find stuff.

 

It wasnt there yet, I uploaded my project just now: http://neverwinterva...-pseudo-list-v4 its separate there, I havent updated the module yet.

               
               

               
            

[Legacy_Shadooow]

               

Was continuing with optimizing my insertsort script. I took the time and I made a comparsion screenshots to easier see whats going on there. Thus Im reposting old results in this format as well.

 

My first insertsort on 2char element list is a version 6. This version was able to sort list of 377 elements without TMI, 378th produced TMI error. (This result vary because the number of checks is dependant on a numbers in list and their position. But I compared this on the same values in list starting with 400 removing one random element each time till one script passed.

 

Ok, my first attempt to optimize it was v7. Image:

 

this produced worse result than v6, a 374 elements without TMI so I tried different approach.

 

v8: (comparing with v6 as v7 is worse)

 

This was suprisingly better and sorted 379 elements without TMI, that is 2 more then v6.

 

Today I continued and used v8 as a base.

 

Now see what Ive done in v10.

 

This version compares bit differently. Ive calculated the number of cycles it does and it differs between v8 and once is much lesser second time bit bigger, usually lesser but produces the same result, I tried it on on a list of 40 numbers and re-inicialized it ten times and at average the v10 version used -3cycles to sort the whole list. But even if the average was same, due to the secondary optimalizations coming from the fact that it hass less methematical instructions in it, this provides always better result than v8.

 

Then I though of changing n == 0 to !n, i didn't expected better result but it proved to be better, sorted 2 more elements than v10 before TMI see image:

 

Then I saw the possibility to simplyfied the string comparsion when the n == 0 or n == last. But went that direction by steps, see v12:

This boosted the result significally, sorted amazing 8 more elements before TMI! Seems the logical or costs a lot. But that was only first step towards what I had in mind:

 

V13:

and last step to what I wanted to do is v14:

What I don't understand is that v12, v13 and v14 all sorts the same number of elements. The optimalization in the string operation didn't affected the result at all.

 

Though, Ive tried it on multiple value sets and few times the v12 threw the TMI. Problem is that the placeable that ran the script also printed FINISHED. (I dont know now whether it sorted the list correctly because in order to test them between each other I had to uncomment the last command that replaces old list with new sorted one. However in 1 of 10 cases it resulted on the same number of elements like v13 and v14 to TMI so basically v13 and v14 are a +1element better. But the v13 and v14 both always sorted the same number of elements. Never less never more.

 

Exact results made on random number inicializations:

 

v6: 377 elements without TMI

v7: 374

v8: 379

v9: 373 (v9 is not showed on screenshots there, its a v8 with a call to the GetNthElement(string list, int th) function instead using direct system call GetSubString(list,th,2); - the bad result was expected in this case

 

Comparsion of 8 with 10,11,12,13,14 was done on different number inicialization set:

 

v8: 379

v10: 392

v11: 394

v12,13,14: 402

 

EDIT: just made a new optimalization that sorted amazing 20 more elements than v14 without TMI.

EDIT2: okay, my final optimized version can sort now around 440 elements

EDIT3: since the stable sort wasn't in a rules and I expect your alghorithm doesn't produce stable sort I made simple adjustion into my insertsort alghorithm and it can sort around 550 elements this way.

               
               

               

                     Modifié par Shadooow, 09 mars 2014 - 12:00 .
                     
                  

            

[Legacy_meaglyn]

               

I have not done the copy from list to array code with this one because I did not have your list code which did enough elements. Probably won't bother at this point. I've already spent more time on this than I had planned.  Yes, quickstort does not produce a stable sort.

 

Here's the quicksort code itself. I spent about 10 minutes testing this to see what using a very short recursive algorithm would do. This assumes the input is stored as "AX" ints on the module (for X = 0 ... N-1).

object oModule = GetModule();

int partition(int l, int r) {
   int pivot, i, j, t;

   pivot = GetLocalInt(oModule, "A" + IntToString(l));
   i = l; j = r+1;
   while( 1) {
        do ++i; while( GetLocalInt(oModule, "A" + IntToString(i)) >= pivot && i <= r );
        do --j; while( GetLocalInt(oModule, "A" + IntToString(j)) < pivot );
        if( i >= j ) break;
        t = GetLocalInt(oModule, "A" + IntToString(i));
        SetLocalInt(oModule, "A" + IntToString(i), GetLocalInt(oModule, "A" + IntToString(j)));
        SetLocalInt(oModule, "A" + IntToString(j),t);
   }
   t = GetLocalInt(oModule, "A" + IntToString(l));
        SetLocalInt(oModule, "A" + IntToString(l), GetLocalInt(oModule, "A" + IntToString(j)));
        SetLocalInt(oModule, "A" + IntToString(j), t);
   return j;
}

void quickSort(int l, int r) {
   int j;

   if( l < r )  {
        j = partition(l, r);
       quickSort(l, j-1);
       quickSort(j+1, r);
   }
}

I thought you were using a basic insertion sort. If you got an NlogN variant then that explains a lot (isn't that a shell sort?). Plus you've tailored the algorithm to your data structure and vice-versa. How does your algorithm work if you do use the actual interfaces to the data structure instead of directly accessing the internal structure?

 

One thing you might try just for grins is using shifts instead of *2 and /2.  Depending on how nwnscript implements those math operations it may be shorted to use <<1 and >>1 instead. Or it might not. With a real compiler with optimization it won't matter, but in this case it might.

 

Anyway, I concede '>

 

               
               

               
            

[Legacy_Shadooow]

               

Hmm no its not shell sort afaik and my first versions provides stable sort.

 

Im doing this:

 

A1,A2,A3,A4,A5 = 50, 1, 10, 95, 33

 

step by step

 

A1,

A1,A2

A1,A3,A2

A4,A1,A3,A2

A4,A1,A5,A3,A2

               
               

               
            

[Legacy_meaglyn]

               

Hmm no its not shell sort afaik and my first versions provides stable sort.

 

I never said it didn't.

               
               

               
            

[Legacy_Shadooow]

               

 

How does your algorithm work if you do use the actual interfaces to the data structure instead of directly accessing the internal structure?

Haven't tried yet but I expect very significal drop - based on the comparsion Ive made with v8 vs v9. Basically, if you are working on some include, its better to use only direct NWScript functions than relying on other scripted functions you've made. Of course - this makes modifying the scriptsets harder so I think it has sense only in loops where the function would be called multiple times.

 

One thing you might try just for grins is using shifts instead of *2 and /2.  Depending on how nwnscript implements those math operations it may be shorted to use <<1 and >>1 instead. Or it might not. With a real compiler with optimization it won't matter, but in this case it might.

 

Anyway, I concede '>

 

Tried it but didnt provided any better result. Anyway here is my last stable insertsort script v 21:

void SortListIntegerValues21(object oList)
{
string list = GetLocalString(oList,"LIST");
int num = GetStringLength(list)/2;
string charthis, list_new = GetStringLeft(list,2)+" ";//workaround to deal with bug in InsertString function
int valthis,num_new,min,max,th, n = 1;
 while(n < num)
 {
 charthis = GetSubString(list,n++*2,2);
 valthis = GetLocalInt(oList,charthis);
 min = 0;
 max = ++num_new;
 th = num_new/2;
  do
  {
   if(valthis > GetLocalInt(oList,GetSubString(list_new,th*2,2)))
   {
    if(!th)
    {
    list_new = charthis+list_new;
    break;
    }
    else if(valthis < GetLocalInt(oList,GetSubString(list_new,(th-1)*2,2)))
    {
    list_new = InsertString(list_new,charthis,th*2);
    break;
    }
   max = th;
   }
   else
   {
    if(th == num_new)
    {
    list_new+= charthis;
    break;
    }
    else if(valthis > GetLocalInt(oList,GetSubString(list_new,(th+1)*2,2)))
    {
    list_new = InsertString(list_new,charthis,(th+1)*2);
    break;
    }
   min = th;
   }
  th = (max+min)/2;
  }while(TRUE);
 }
SetLocalString(oList,"LIST",GetStringLeft(list_new,num*2));//workaround to deal with bug in InsertString function
SpeakString("FINISHED");
}

This is able to sort around 440 elements without TMI (average, best scenario where the values in list are random, it has much worse results on already sorted list)

 

And the unstable one:

void SortListIntegerValues22(object oList)
{
string list = GetLocalString(oList,"LIST");
int num = GetStringLength(list)/2;
string charthis, list_new = GetStringLeft(list,2)+" ";//workaround to deal with bug in InsertString function
int valthis,num_new,min,max,th, n = 1;
 while(n < num)
 {
 charthis = GetSubString(list,n++*2,2);
 valthis = GetLocalInt(oList,charthis);
 min = 0;
 max = ++num_new;
 th = num_new/2;
  do
  {
   if(valthis > GetLocalInt(oList,GetSubString(list_new,th*2,2)))
   {
    if(!th)
    {
    list_new = charthis+list_new;
    break;
    }
    else if(valthis <= GetLocalInt(oList,GetSubString(list_new,(th-1)*2,2)))
    {
    list_new = InsertString(list_new,charthis,th*2);
    break;
    }
   max = th;
   }
   else
   {
    if(th == num_new)
    {
    list_new+= charthis;
    break;
    }
    else if(valthis >= GetLocalInt(oList,GetSubString(list_new,(th+1)*2,2)))
    {
    list_new = InsertString(list_new,charthis,(th+1)*2);
    break;
    }
   min = th;
   }
  th = (max+min)/2;
  }while(TRUE);
 }
SetLocalString(oList,"LIST",GetStringLeft(list_new,num*2));//workaround to deal with bug in InsertString function
SpeakString("FINISHED");
}

Which is able to sort over 550 elements before TMI.

 

I can't see any way to optimize further so Im done I guess (mean, I do but I tried already and it has no effect on result so the gain is redundant if there is any). But it was very fun and the gain of ~80 elements after optimalization is very good result.

               
               

               
            

[Legacy_meaglyn]

               

Fwiw, to help with maintaining things I'd just put the sort code in the list include file, i.e. make it part of the data structure itself.

 

That leads me to a different solution entirely. In your actual use case for this sorting where does the data come from?   One thing  you could do is make the list sorted all the times. You could do that with the current test as well. It just depends on how you implement insert.  If you assume the list is sorted (which it is by definition when empty) you can use a binary search (logN) to insert new elements in the right place. This means you no longer ever need to sort the whole list. Your list implementation is designed to handle insert and removal eficiently.  Also you get benefits of a sorted list for general finds as well.   I should have done that for the challenge, then the sort operation is a no-op and would never TMI no matter how many elements you put in (within practical reason)  '>