35 réponses à ce sujet

[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

 

[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

[meaglyn]

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

 

I never said it didn't.

[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.

[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) 
 

[Shadooow]

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) 
 

Yes I know about this and it could lead to very exciting results. The question in this implementation is how big can the list must be to adding+sorting new element produced TMI. I was bit busy to test this case but its on my schedule.

 

Of course since adding elements would be usually done in a iteration or recursion, there still must be delay if someone would want to store more than 1000 elements, but in the end, this method should provide best results from all.

[_Guile]

I think I saw some code somewhere that the TMI kicks out at a set number, meaning if the code reaches X loops, it kicks out TMI by default...

(Is that true or false?)

 

Nevertheless, I'm curious if hardware would effect the test results, (e.g., a dual core @ 2.8 GHz vs a Quad Core @ 4.3 GHz) 

[meaglyn]

It's not X loops, it's simply the number of instructions. You can hit TMI without loops but it takes some work. Loops are generally the easiest way to get the instruction count high enough to hit the limit. 

 

This  has nothing to do with the underlying hardware. This is NWScript running in the game engine's virtual machine and we are not measuring time, just instructions.

[meaglyn]

 

Of course since adding elements would be usually done in a iteration or recursion, there still must be delay if someone would want to store more than 1000 elements, but in the end, this method should provide best results from all.

 

That's why I was asking what your real world (so to speak) use case is.  If you are adding all the elements at once and they are not random you could sort them before hand and be done with it.  But if this is some list that is built up over time then you can do the sorted insert.

[Shadooow]

That's why I was asking what your real world (so to speak) use case is.  If you are adding all the elements at once and they are not random you could sort them before hand and be done with it.  But if this is some list that is built up over time then you can do the sorted insert.

Im creating a list of 2-4 elements, containing only integer type, in one fashion and need this to be sorted by highest and then looping all elements until i get a match. And Ive already rescripted it to sort with adding.

[FunkySwerve]

It's not X loops, it's simply the number of instructions. You can hit TMI without loops but it takes some work. Loops are generally the easiest way to get the instruction count high enough to hit the limit. 

 

This  has nothing to do with the underlying hardware. This is NWScript running in the game engine's virtual machine and we are not measuring time, just instructions.

Bingo. It's called the 20k rule, for 0x20000. That's 131,072 instructions before you hit the limit, by default. A function can be one or more instructions. The NWNX tmi plugin allows you to up the limit to 8,000,000 instructions.

 

Funky