A scripting competition - a sorting alghorithm

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

               
               

               
            

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

               
               

               
            

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

               
               

               
            

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

               
               

               
            

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

               
               

               
            

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