Attract-Mode Support Forum

Attract-Mode Support => Scripting => Topic started by: zpaolo11x on August 18, 2020, 01:03:54 AM

Title: Squirrel sorting speed
Post by: zpaolo11x on August 18, 2020, 01:03:54 AM
I was playing with array sorting in squirrel, and I discovered some interesting things.

Sorting an array using just ARRAY.sort() is much faster (an order of magnitude) than sorting using ARRAY.sort(@(a,b) a <=> b), and this is clearly visible for very large arrays (10'000 items or more). I don't know why this happens.

If you have an array of table items, like an array where every element is {name ="blablabla", val="120"} and you want to sort this array by the "val" table field using ARRAY.sort(@(a,b) a.val <=> b.val) this is even slower, more or less takes twice the time of a normal array sort ARRAY.sort(@(a,b) a <=> b).

I implemented my own TimSORT algorithm and sometimes it gets better results than the standard squirrel sorting using custom sort functions, but overall the improvement is marginal, it seems the overhead of using custom functions is very high.

Anyone has a suggestion on how to avoid this issue? The difference between simple sort() and all the other is striking, I need to find a way to leverage this speed in some way :O
Title: Re: Squirrel sorting speed
Post by: zpaolo11x on August 18, 2020, 08:12:14 AM
I found a nice trick to sort an array of tables. Let's say I have an array like this:

ARR = [ {id ="example",val=10}, {id = "sort", val = 5}, {id = "routine", val = 15}, etc... ]

What I do is I generate an array of string values, then append to each value a "000001","000002" etc. I sort the array using simple sort() function and then "extract" the rightmost number from the string, so I can repopulate the array of tables with the elements.

Let's say I want to sort the top array by "id", I create this array

TEMPARR = ["example000000","sort000001","routine000002"]

sort it

TEMPARR = ["example000000","routine000002","sort000001"]

and then extract the new "order" array: [0,2,1]. This is the order of the elements of the original array that will be regenerated.

This is not perfect, I'll have to put some null characters before the leading zeros to avoid the zeros to be part of the sorting, but overall it works and it's a bit faster than the array sorting with external function. It's more than twice as fast as squirrel sorting using @(a,b) <=> which is not bad at all.