35 réponses à ce sujet

[Shadooow]

When I was making a DEMO module for my Pseudo-List scripting library I just uploaded on new vault, I found out the problematic of a sorting in NWN. I already had a function for this but I found out it TMIs when used on a list with more values. After some effort, I was able to improve it but realized this might be beyond the limits of the NWN actually.

 

This however inspired me to make a contest. There are lots of scripters who believe they are better than the others, so this might be a way how to prove it. But the main goal is to have fun finding and beating new challenges and to learn new things.

 

Rules of the contest:

 

1. Everyone needs the same environment so I suggest to use my pseudo-list and DEMO module for that (link above). If you don't like me and refuse to work with something I've created, thats your problem. I am not aware of any other "list" implementation in NWN so thats it. This isn't mean to promote my library, scripting isn't popular anyway and I actually expect that scripters who find the list structure usefull in NWN will actually make their own libraries.

 

2. No kind of delays or passing to other objects (DelayCommand,AssignCommand,SignalEvent, ExecuteScript), no external compillers and no NWNX. The point is to make the most efficient alghorithm in a vanilla NWN environment that will handle to sort the most integer elements in a list structure (from highest to lowest) without TOO MANY INSTRUCTIONS error.

 

3. Everything else is allowed as long as the result will be printable by the "Print illithid mechanism" in the DEMO module. It is not needed to use any of the native List* functions that my library offers.

 

4. Participants will send their script for the sorting, that will be used in an OnUsed event for the placeable to me via PM on these forums (where you provide link for pastebin etc.), latest at the 16th March 2014 (23:59 outer limit ofc). Then, I will put all the scripting into one module, generate a list of random integer elements and run each sorting alghorithm send to me to find out which is able to sort most values without TMI. This test will be repeated five (or maybe 10?) times to avoid a lucky initial sets to influence the results. Results of this test with the source codes and the module itself will be post here in this topic.

 

PS. I would like to participate too if its not a problem that I am the one who will make the tests - if it is we need someone else who can do this.

 

EDIT: there is a question if the sorting alghorithm must provide stable sort order or not. I would vote for yes.

 

Suggestions, questions an subscriptions into contest welcome.

[henesua]

I don't know if I will participate, but I think this is a great idea, ShaDoOoW.

 

I have almost no experience with writing sorts but was thinking about this problem on the bus today. The only proper sort I've done was a sort I was using on an implementation of A* pathfinding in JavaScript. I can't recall what method I used for that. Most of the time in NWN I only look for the lowest or highest number in a stream of numbers rather than a static list, and that is a situation where you don't have to sort so much as store the latest lowest or highest value in a loop of ruse when the loop is finished. (Very primitive).

 

Anyway, as I said I was thinking about the problem of extracting a list of rows from a 2da and then later sorting them so that you can select one using a random number. And the more I thought about it, the more I thought that this was something I'd want to do outside of nwscript. Amongst the scripters on this forum, I know I am not particularly good at coding because for the past 14 years I have no professional experience and I never had any classes.

 

For the best sort… I'm looking at lightfoot. But we shall see. If I have time I will try this, because I have a lot to learn about sorting algorithms.

[Shadooow]

because for the past 14 years I have no professional experience and I never had any classes.

Neither I have. My function for sorting that I made some time ago only managed to sort 50 integers without TMI. That started all of this as I realized this is quite poor result and tried to get better and better. If you can invent a code that will sort more than fifty I think you dont have to shame for your coding, especially if you do it without reading articles and how-tos on web and do it your way.

[meaglyn]

Many of the really efficient sorting algorithms are recursive.  I believe there's a limit other them just TMI in nwn of how deeply you can recurse.

 

There are also different measures of efficiency,  memory, program size, runtime etc.  

 

And sometimes knowing the range of potential inputs or the size of N makes a difference. For smaller numbers or known ranges it may be faster to use one of the slower worst case algorithms.

 

I guess what I'm asking is for a bit more clarification... You mention 50 numbers, but what element count are you hoping for?

 

 

Cheers,

 

meaglyn

[meaglyn]

Nevermind some of that... I see now where you mention the algorithm that can sort the most w/o TMI...

[Shadooow]

Many of the really efficient sorting algorithms are recursive.  I believe there's a limit other them just TMI in nwn of how deeply you can recurse.

 

There are also different measures of efficiency,  memory, program size, runtime etc.  

 

And sometimes knowing the range of potential inputs or the size of N makes a difference. For smaller numbers or known ranges it may be faster to use one of the slower worst case algorithms.

 

I guess what I'm asking is for a bit more clarification... You mention 50 numbers, but what element count are you hoping for?

 

 

Cheers,

 

meaglyn

Yes and thats exactly what makes this interesting. Its not just a "find the best sorting alghorithm on wiki and implement it in nwn", one must think of many issues and technical limitations in NWN and adjust to that

 

the numbers to sort are result of d100() function as implemented in my DEMO module for list

they are stored as local integers on a module and the variable names are put into string which is how my pseudo-list works, it looks this way:

string LIST_TESTLIST "0123456789abcdefghijk...."

int LIST_TESTLIST_0 [result of d100()]

int LIST_TESTLIST_1 [result of d100()]

int LIST_TESTLIST_2 [result of d100()]

int LIST_TESTLIST_3 [result of d100()]

int LIST_TESTLIST_4 [result of d100()]

...

 

 

I give this a few days, when becomes clear that peoples are not interested in this challenge, which is what I suspect, I will publish how many I was able to sort then and perhaps someone takes this and try to beat that result.

Modifié par Shadooow, 01 mars 2014 - 12:52 .

[FunkySwerve]

 I am not aware of any other "list" implementation in NWN so thats it.

Any dynconvo system is ikely to have one. Pspeed's z-dialogue does, at a minimum, if you want something else to look at.

 

I get the challenge aspect of this, but really, if you care about efficient sorts, and you have NWNX, SQL is probably your best bet. I spent quite a bit of time toying with this when I was working out the best way to sort 2016 feats alphabetically into folders according to

'master' groupings, and there's just no other good way.

 

That said, I'll leave you to your intellectual pursuits.

 

Funky

[Shadooow]

Any dynconvo system is ikely to have one. Pspeed's z-dialogue does, at a minimum, if you want something else to look at.

Funky

You are right, I looked there and PSPeed has a "list" implementation there. But it is actually an array which elements are moved manually every time. This is something I described in my project - it is possible solution with some advantages (unlimited storage) but not so efficient which would become clear especially with an attempt to sort it.

 

So I cant really say it is a (pseudo)list. Its an (pseudo)array with extended functionality that moves all the elements' position after one being removed manually to simulate a list behavior, huge difference.

 

 

I get the challenge aspect of this, but really, if you care about efficient sorts, and you have NWNX, SQL is probably your best bet.

 

Funky

Ya, but not always you can use NWNX and not always it is needed. If it can be done without NWNX, why to do it in a first place? Makes it harder to test, makes it nontransferable etc. Specifically, Im always trying to avoid NWNX if I can, so me and anyone else working on my module can test it from toolset easily via F9. But there are other cases like singleplayer where the NWNX is simply not an option. With an use of the delays, it is possible to sort any number of valus without NWNX.

[FunkySwerve]

You are right, I looked there and PSPeed has a "list" implementation there. But it is actually an array which elements are moved manually every time. This is something I described in my project - it is possible solution with some advantages (unlimited storage) but not so efficient which would become clear especially with an attempt to sort it.

 

So I cant really say it is a (pseudo)list. Its an (pseudo)array with extended functionality that moves all the elements' position after one being removed manually to simulate a list behavior, huge difference.[/quote]

I don't think that distinction can withstand scrutiny in nwscript,  but I'm not willing to argue the point. Half the reason I'm posting is to figure out if separate quote sections still work the same way. FWIW, pspeed clearly thought he was implementing lists. He named his include pg_lists_i, and described it as "Some list APIs that work with local object variables."

 

Ya, but not always you can use NWNX and not always it is needed. If it can be done without NWNX, why to do it in a first place? Makes it harder to test, makes it nontransferable etc.

 

Mainly because it's more efficient in the end, per my original post. As for testing, there are ways around that. HG uses linux and I dev in windows, but I have a VM set up that can load the mod, with plugins, faster than it loads natively with F9 - not that I CAN F9 test anymore (crash city).  As for transferability, I have to concede that - I generally try to do things without it where it's feasible. Consider, however, trying to do this in nwscript natively:

Alpha feat sort with master folders

You'd have to be a real masochist to even consider it (note that the version of that code without sorting WAS done in nwscript with delays).

 

SQL is just the right tool for that job.

 

But I digress. I look forward to seeing what you all come up with for pseudolists, as this is one of the areas where I still have some room to learn.

 

[Edit]

Damn, will have to play with the controls a bit more to get the new quoting setup down.

 

Funky

[Shadooow]

I just said it would be possible. Its really masochism to sort something that big in nwn, but it would be possible to do. I agree that SQL is the best tool for sorting but on the contrary to the large number of values when the number of values to sort is smaller, then the NWNX/SQL is like a nuclear warhead to get rid of ants (quoting Zebranky ) and thats something Ive used it for so far, just to sort 4 values only.

[meaglyn]

It's not really possible to sort something with 2000 items in a single NWN script.  Best average case sorting algorithms work in nlogn time so that's roughly 22000 (2000 * 11) pieces of work.  Given a limit of 65000 or so instructions before TMI, you'd need your loop to be about 3 instructions long, which isn't going to happen. 

 

For smaller numbers you can do well enough in NWN. I'm not going to go into details while people may be working on this. I do have one observation I'll share at this point.  Shadooow, your List code is not as efficient as you might think from a number of instructions point of view. All those string operations take their toll on your instruction count. I found that I could not even initialize the starting array to 115 without TMI after adding the extra characters. (I took out the ; as well since that's can be an issue with SQL as well).

 

@Funky: That looks like something you do once to a list on module load. Why are you even bothering to have code in the module to sort it? Just sort it once outside the module and be done with it. Am I missing something?

[Shadooow]

It's not really possible to sort something with 2000 items in a single NWN script.  Best average case sorting algorithms work in nlogn time so that's roughly 22000 (2000 * 11) pieces of work.  Given a limit of 65000 or so instructions before TMI, you'd need your loop to be about 3 instructions long, which isn't going to happen.

Sure it is, you can avoid TMI with delays. Which is why I disallowed them from the contest. And it still can be done in a single script

 

I do have one observation I'll share at this point.  Shadooow, your List code is not as efficient as you might think from a number of instructions point of view. All those string operations take their toll on your instruction count. I found that I could not even initialize the starting array to 115 without TMI after adding the extra characters. (I took out the ; as well since that's can be an issue with SQL as well).

yes i found it myself very recently and fixed, some of the functions are badly written, but the concept is well designed

 

I was aware of this so that why I stated that the scripter doing this doesnt need to use any of my native functions.

 

also, I decided to change the list into object as I outlined in the description on vault - improved efficiency by 100% itself, will update this on vault soon

[Shadooow]

Uploaded, the new version treats list as on object which eliminated the need to parse strings.

 

Thus instead of previous:

 

int val = GetLocalInt(oListHolder,"LIST_"+sListName+"_"+sElementName);

 

came to the

 

int val = GetLocalInt(oList,sElementName);

 

Also I increased the pattern string to 160 characters and initializing the list with this ammount of elements (without delay) no longer throws the TMI.

[meaglyn]

Sure it is, you can avoid TMI with delays. Which is why I disallowed them from the contest. And it still can be done in a single script

 

I suppose I should have said "script execution". As per the rules of your challenge. I wasn't counting delays as being part of the same script execution.

 

Yes, you could write something which would get around that and sort more. But at that point I'd have to go with Funky.  Also, once you introduce delays you have to deal with locking. You've now got the possibility of having your state messed up by other things happening. It's sort of fake multithreading...

 

I'll try out your new version.

[Shadooow]

I suppose I should have said "script execution". As per the rules of your challenge. I wasn't counting delays as being part of the same script execution.

 

Yes, you could write something which would get around that and sort more. But at that point I'd have to go with Funky.  Also, once you introduce delays you have to deal with locking. You've now got the possibility of having your state messed up by other things happening. It's sort of fake multithreading...

I know, but thats not what I claimed, only that it can be done .

[Shadooow]

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

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

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

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

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

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

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

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

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

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