[MOD] quicksort (utility)

The place to discuss scripting and game modifications for X4: Foundations.

Moderators: Scripting / Modding Moderators, Moderators for English X Forum

Post Reply
Ramokthan
Posts: 103
Joined: Fri, 22. Apr 16, 21:25
x4

[MOD] quicksort (utility)

Post by Ramokthan » Sun, 7. Jul 19, 10:19

The plugin will provide a possibility for mod scripts to utilize the imo most efficient (in terms of speed and memory usage) sorting algorithm existing.

It will not change any parameter or things ingame.
This mod is solely ment for developer to work with.


Dear developer, please avoid implementing the files directly into your mod, rather then referencing it as a required mod if your mod utilizes this scripts to get fast updates and bugfixes.

Download links:
Quicksort (Nexusmods)
Quicksort (Steam Workshop)

Please be aware following decriptions is for developer which intend to use this mod:

Mod developer can use the sorter by calling the 'quicksort' script.
It will sort the given objects list by its given values ascending

Example of use:

Code: Select all

<run_script name="'quicksort'">
            <param name="objects" value="$UnsortedObjects"/>
            <param name="values" value="$UnsortedValues"/>
            <save_retval name="sortedobject" variable="$SortedObjects" />    
            <save_retval name="sortedvalue" variable="$SortedValues" />                
</run_script>
While $UnsortedObjects contain the Object which are not sorted $UnsortedValues contain the values after which are to be sorted.

$UnsortedObjects can contain any value, no matter which type.
$UnsortedValues has to contain a float or integer type value.

$UnsortedObjects and $UnsortedValues have to contain the same amount of entries.

$SortedObjects and $SortedValues contain the sorted values of the respective input after script has finished.


How does it work:

Lets give another example:
Lets assume $UnsortedObjects has following data [wareY,wareZ,wareX]
and $UnsortedValues has following data [2,3,1]

Each element of both lists on the same index are refering to each other, which means for the sort algorithm the first value of
$UnsortedObjects (wareY) has the value of the first element of $UnsortedValues (2) and so on.

This gets important when we know it all of them will be sorted ascending by their values.

Result in this case after running the sort script would be:
$SortedObjects [wareX,wareY,wareZ]
$SortedValues [1,2,3]

Elements are now sorted while $SortedValues contain their values ascending, and their respective objects in their partner list changed their order respectively.

This will work for lists of ANY size.

Example usecase:


You want to sort a bunch of stations for their cargo size (for example).

This is how:

First iterate your station list to set the value list to sort after:

Code: Select all

       <create_list name="$UnsortedStationValues" />
      <do_all exact="$UnsortedStations.count" counter="$b">
         <append_to_list name="$UnsortedStationValues" exact="$UnsortedStations.{$b}.cargo.capacity.all"/>
       </do_all>

Now we got all the values in the same order (important) then our $UnsortedStations in a seperate list.
The first element of $UnsortedStations will have its respective value in the first element of $UnsortedStationValues, the second element has its respective value in the second element of $UnsortedStationValues and so on.
Now we run the sort script:

Code: Select all

        <run_script name="'quicksort'">
            <param name="objects" value="$UnsortedStations"/>
            <param name="values" value="$UnsortedStationValues"/>
            <save_retval name="sortedobject" variable="$SortedStations" />    
            <save_retval name="sortedvalue" variable="$SortedStationValues" />                
        </run_script>

After that $SortedStationValues will contain the values sorted ascending and $SortedStations elements will have changed the same way.
If you iterate the resulting list now again and printing the StationObjects cargo.capacity you will find them sorted ascending.

strask412
Posts: 398
Joined: Thu, 29. Nov 07, 21:34
x4

Re: [MOD] quicksort (utility)

Post by strask412 » Mon, 8. Jul 19, 07:45

Ramokthan wrote:
Sun, 7. Jul 19, 10:19
The plugin will provide a possibility for mod scripts to utilize the imo most efficient (in terms of speed and memory usage) sorting algorithm existing.
Hey, thank you for creating and sharing this resource!

What is this "imo most efficient" algorithm? And if you feel like sharing why you selected it as compared to any other algorithm, that would be educational I bet. :)

I tried to read Knuth (vol. 1) once. It didn't go well, so when I encounter people with expertise with algorithms, I like to obtain a nugget. :lol:

Ramokthan
Posts: 103
Joined: Fri, 22. Apr 16, 21:25
x4

Re: [MOD] quicksort (utility)

Post by Ramokthan » Mon, 8. Jul 19, 09:40

it is quite debatable in developer community which sorting algorithm is best.

Why?
Because different sorting algorithm have special perks which make them fitting better as others in some cases.
After all the differences are so minor in most usecases personal preference comes into account.

I currently see 3 Perks to measure an algorithm with:
Performance: The number of iterations a algorithm needs till a given list is fully sorted in (best/usual/worst) case.
Memory usage: The amount of data the sorting algorithm holds in RAM while sorting and how much this amount grows as the amount of elements to sort grows.
Stability: Element original order is maintained if sorting meets same values. (Ask about that againif i need to explain more)

So if you see that in some environments performance is key and you don't care about memory usage, several sorting algorithms are better because they have a lower expected iteration count.
And in some systems where RAM is scarce you rather accept a less performant algorithm if he uses RAM more economic.

This is the main reason why i said it is the best sorting algorithm IN MY OPINION.
Quicksort has a medium to low Memory usage and is a fast sorting algorithm in usual cases.
I has a quite bad performance if the Data is really ****** up, but well lots of sorting algorithms have trouble with that.
I mean the more Data is messed up the more you have to sort.

Quicksort has following specs:

Iteration:
Best Case: n*log(n)
Average Case: n*log(n)
Worst Case: n²

lets assume we have n=10 elements then following iterations would be needed for the different scenarios:
Best Case: 10
Average Case: 10
Worst Case: 100

The maximum memory usage on Quicksort is n in worst case, but usually log(n) in average on best cases.
This means it holds 1 element in memory at a time when we have n=10.

Quicksort is not stable originally, but there are stable versions nowadays.

So far on the technical side.

After all there are more modern and state of the art sorting algorithms (lets be honest, quicksort is a pretty old/early algorithm) which are better then quicksort in all categories, but i am an old man, i know quicksort and i like it.
Additionally i don't think it makes much sense to learn and implement a more modern sorting algorithm for like almost 0 real benefit, since we are talking about a game and not a real time critical application, additionally it is coded in a script language wich has impact on performance anyway.

TL:DR why i used Quicksort and said its imho best:
Quicksort is fast in most cases, does not use up much memory in most cases and most important:
I already worked a lot of times with this algorithm and know its in and outs, knowing its fitting for this usecase.

strask412
Posts: 398
Joined: Thu, 29. Nov 07, 21:34
x4

Re: [MOD] quicksort (utility)

Post by strask412 » Tue, 9. Jul 19, 04:20

Ramokthan wrote:
Mon, 8. Jul 19, 09:40
TL:DR why i used Quicksort and said its imho best:
Quicksort is fast in most cases, does not use up much memory in most cases and most important:
I already worked a lot of times with this algorithm and know its in and outs, knowing its fitting for this usecase.
Thank you so much for that explanation!

And yes, I'm certain the result is far better than a novice like me selecting something more "modern" (but inappropriate for the task). :)

Ramokthan
Posts: 103
Joined: Fri, 22. Apr 16, 21:25
x4

Re: [MOD] quicksort (utility)

Post by Ramokthan » Tue, 9. Jul 19, 10:26

Note:
Currently the Tool is under heavy rework since it is very inperformant, this is not the algorithms fault but the X4 script environment is very slow invoking script calls, and due to this script is heavily relying on recursive sript calls it is quite slow at the moment. I am aware of this and work on it hard to get its calculation speed to what it should be.


For the record:
in the script he has different memory usage anyway because i cant work with the tools modern programming languages have, like references, lists etc and i don't kniw how memory is allocated in the background in X4 while scripts are executed.
So be aware it could use up much more memory then a vanilla algorithm would. In 99.999% of cases this amount will stay irrelevant anyway i think. I assume its only a difference of several kilobytes of RAM, depending on the list size and complexity to sort.


Update released on nexus and steam
Thanks for your patience

Its now 1 million times faster (not kidding)

Post Reply

Return to “X4: Foundations - Scripts and Modding”