Improve array.sort_custom

[iconberg]

I was sorting enemies in an array by x, y coordinates and by debugging i see that the custom sorting function "pos_sort" is called very often. Sorting 10 enemies calls the sorting function 192 times. I guess the cause is the custom sorting function can only give boolean back. The same sorting in python where the sorting function can give a sorting value back instead of boolean takes only 10 calls.

I did no timing measures and have actual no performing problems but i would like to see the sorting like in python via value instead of boolean. The sorting via value gives also more control so you can sort by multiple criteria at once.

gdscript (pos_sort is called 192 times)

# sorting by x, y coords
func pos_sort(a: QuestionTarget, b: QuestionTarget):
	print(100000 * a.position.x + a.position.y)
	if (100000 * a.position.x + a.position.y) > (100000 * b.position.x + b.position.y):
		return false
	return true

# get questions in current scene
func get_active_questions():
	var t: Array = get_tree().get_nodes_in_group(Constants.active_questions)
	for q: QuestionTarget in t:
		t.sort_custom(pos_sort)
	return t

python (pos_sort is called 10 times)

txt = """Icon:<Sprite2D#28017951954>	1	い	i	112	88
Icon6:<Sprite2D#28856812813>	1	お	o	127	312
Icon3:<Sprite2D#28353496303>	1	あ	a	324	123
Icon7:<Sprite2D#29024584983>	1	え	e	329	431
Icon5:<Sprite2D#28689040643>	1	あ	a	492	270
Icon2:<Sprite2D#28185724133>	2	あ	a	631	80
Icon9:<Sprite2D#29360129323>	1	い	i	680	395
Icon4:<Sprite2D#28521268473>	1	お	o	890	113
Icon8:<Sprite2D#29192357153>	1	え	e	905	273
Icon10:<Sprite2D#29527901493>	1	え	e	931	431"""
test = []


for line in txt.split('\n'):
    test.append((line.split('\t')))


def pos_sort(a):
    print(100000 * int(a[4]) + int(a[5]))
    return 100000 * int(a[4]) + int(a[5])


test.sort(key=pos_sort)

[Calinou]

Changing a method's return type breaks compatibility, so this would need to be implemented as a new method without changing the existing one.

[iconberg]

Yes, i understand,
so maybe a new one called "sort_custom_key" or so.

[AThousandShips]

But this python code isn't necessarily easy to work with, it requires you to be able to encode your sorting scheme as a 64 bit integer

How would you, for example, sort Vector3, Vector4, or even Vector3i (or on a double precision build, a Vector2)?

This scheme is very specific, and isn't trivial to apply to general situations

How, for example, would you handle sorting arrays lexicographically? Or sort different data types where you'd want to sort by type as well?

Edit: While this sorting method can run faster (with specific data, it's very limited) it requires a lot of extra storage so it's costly still, so unless we just sort the returned keys by normal means (which doesn't run any faster) we need a lot of extra memory and to add algorithms we are not currently supporting

[AThousandShips]

Those counts are likely wrong if you're just sorting once, please confirm, it should be around ~33

But what I'm saying is that it's mathematically impossible to sort fully general data of the kind like Vector3i, it's all specific and you need to design things very specifically, so this isn't a replacement, and it's of relatively limited use in general I'd say, but regardless it's not a replacement

Edit: Ran a few shuffled tests and the highest number of comparisons I got was 38, which is slightly higher than expected but nowhere near the ones you got

[iconberg]

Yes, you are right. I have the array.sort_custom in a loop. That my fault. A leftover from changing to working with groups.
Sorry for the trouble.

# get questions in current scene
func get_active_questions():
	var t: Array = get_tree().get_nodes_in_group(Constants.active_questions)
	for q: QuestionTarget in t:
		t.sort_custom(pos_sort)
	return t

I would see Vector3i as 3 separate values x,y,z. I did not see a reason why these should not be sortable by x, y and z.
But right it is not a replacement.

[AThousandShips]

I would see Vector3i as 3 separate values x,y,z. I did not see a reason why these should not be sortable by x, y and z.

I mean by your method using a key, you can't encode every possible Vector3i with this method, that's mathematically impossible as it would require you to encode 96 bits in 64 bits, which by fundamental reasons of information theory is impossible.

You can see here for some details on such algorithms, but the fundamental factor is that the sorting of them, using non-comparison methods (which is really the main reason you'd convert to a key, otherwise it doesn't really help sorting at all), requires some limitations on the data, and also requires quite a bit of additional memory to work, unlike comparison sorts which generally require very little additional memory.

I'd say we shouldn't add a non-comparison based sort because their usefulness is limited and they're hard to use for general purpose data, and maintaining the algorithm etc. might be difficult since the methods are harder to use for users who aren't well versed in them. They're powerful but for very limited use cases, along with their memory requirements, I'd argue they generally work best when the specific parameters are well known and you can fine tune them well, with a general purpose key you get very inefficient stuff because of the large key size I'd suspect

[iconberg]

Ok, memory consumption is more for the key method. But the godot method has a big growing factor even used right. As an disadvantage is the sorting takes different times depending how already sorted the source is. A second sort for 10 elements takes the calls down for example from 30 to 10. Sorting with key takes everytime the same calls.

Sorting
enemies -> calls
5 -> 11 (x2)
10 -> 30 (x3)
15 -> 71 (x4)
30 -> 250 (x8)

How would you sort a vector3i with the current "sort_custom"?
I cant imagine how you sort a vector3i with a compare based sorting without using generating a key like i have done. So the problem "to encode 96 bits in 64 bits" still a problem with compare sort too!?

I tried comparison solution for my current x,y coords an it is not given the same correct result.

func pos_sort2(a: QuestionTarget, b: QuestionTarget):
	if (a.position.x > b.position.x) and (a.position.y > b.position.y) :
		return false
	return true



Sorting key gives correct result
Icon	112	88
Icon3	324	123
Icon5	324	296
Icon2	631	80
Icon4	890	113

Sorting compare (none is right, tried all variants for x,y >>,<<,><,<>)
Icon2	631	80
Icon	112	88
Icon4	890	113
Icon5	324	296
Icon3	324	123
----------------------
Icon:<Sprite2D#28017951954>	1	い	i	112	88
Icon3:<Sprite2D#28353496303>	1	え	e	324	123
Icon5:<Sprite2D#28689040643>	1	あ	a	324	296
Icon2:<Sprite2D#28185724133>	2	い	i	631	80
Icon4:<Sprite2D#28521268473>	1	え	e	890	113

So it is not possible to sort this with compare?

[AThousandShips]

How would you sort a vector3i with the current "sort_custom"?

You just compare lexicographically, x, then y, then z, or what ever you wish, this is standard, you don't need a key with a compare sort:

func cmp(lhs: Vector3i, rhs: Vector3i) -> bool:
    if lhs.x < rhs.x:
        return true
    elif lhs.x > rhs.x:
        return false
    else:
        if lhs.y < rhs.y:
            return true
        elif lhs.y > rhs.y:
            return false
        else:
            return lhs.z < rhs.z

Assuming you want to sort from lower to higher

This is standard

But the point is:
You can't sort data with keys when the data type has more possible values than there are keys

A Vector3i has 2^96 different combinations, but an int in GDScript has only 2^64, this means that with a limited range for Vector3i, like only [-10, 10] you can absolutely use a key sort, but you have to know the data you're using more precisely, which requires filtering etc., and several algorithms require that the keys are unique, i.e. that there's only one of each value when sorting

How you design your comparison operation is up to you, but you can sort all kinds of data with a comparison sort, as long as you define how you want to sort them well, which is kind of an unavoidable requirement