A scripting competition - a sorting alghorithm

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

               
               

               
            

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

               
               

               
            

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

               
               

               
            

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

               
               

               
            

[Legacy_meaglyn]

               

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

               
               

               
            

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

            

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

               
               

               
            

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

               
               

               
            

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

               
               

               
            

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

               
               

               
            

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

               
               

               
            

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

               
               

               
            

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

               
               

               
            

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

               
               

               
            

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