What has best performance: Array.erase(x) or Array.pop_at(Array.find(x))?

Archive
1
:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By blobmcbarnum

To remove elements from arrays, I have been using pop_at and find methods combined.

Array.pop_at(Array.find(x))

I steered away from Array.erase(x) to remove elements because the documentation mention it being a slow method. However, combining two methods to achieve the same might be as slow, and maybe the difference is insignificant?
What would be better?

Test it. Run some code with a timer before and after, if it’s really an issue in your game. On the face of it, I’d assume Array.find(x) is O(n) while pop_at(x) could be O(n) too as, worse case, it has to touch every element.

If you’re looking up and then removing the found item, perhaps a dictionary work well? But as I wrote, test it!

spaceyjase | 2023-05-24 16:33

1 Like
2
:bust_in_silhouette: Reply From: jgodfrey

I haven’t looked at the implementation of either of these mechanisms, but I’d hazard a guess that erase() might be faster. Curious now, I hacked-together the following test code that processes 2 identical arrays (each with 100,000 elements) using each mechanism.

func _ready():
	var items = 100000
	var t1
	var t2
	var arr1 = []
	for i in items:
		arr1.push_back(i)
	arr1.shuffle()
	var arr2 = arr1.duplicate()
	
	t1 = Time.get_ticks_usec()
	for i in items:
		arr1.pop_at(arr1.find(i))
	t2 = Time.get_ticks_usec()
	print("Time for find/pop: %s" % (t2 - t1))
		
	t1 = Time.get_ticks_usec()
	for i in items:
		arr2.erase(i)
	t2 = Time.get_ticks_usec()
	print("Time for erase: %s" % (t2 - t1))

On my dev laptop, that results in this output:

Time for find/pop: 17376226
Time for erase: 13709720

So, yeah, that seems to indicate that erase() is faster, though the differences would be relatively negligible on typical arrays (depending on your definition of typical)…

1 Like