Topic was automatically imported from the old Question2Answer platform.
Asked By
Diet Estus
I have two arrays, each containing a few thousand Vector2s.
I want to find out if they intersect, but don’t care about the intersection itself.
Currently, I do it this way.
func intersects(array1, array2):
var intersect = false
for item in array1:
if item in array2:
intersect = true
break
return intersect
I do not feel like this is the most optimal way to do it. In fact, I am experiencing performance issues doing it this way.
What is the fastest way to check arrays for intersection?
I am open to using a different data type, like dictionaries. I am even open to using a different type of object for my elements, for example, using subarrays rather than Vector2s.
Your solution is n^2 meaning that for each element of the first array it has to go through each element of the second array. As the array sizes grow the search times grow exponentially.
By using dictionaries, you can make this n log n which is much faster:
func intersects(arr1, arr2):
var arr2_dict = {}
for v in arr2:
arr2_dict[v] = true
for v in arr1:
if arr2_dict.get(v, false):
return true
return false
Or if you want to return the actual elements, change it like this:
func intersect_arrays(arr1, arr2):
var arr2_dict = {}
for v in arr2:
arr2_dict[v] = true
var in_both_arrays = []
for v in arr1:
if arr2_dict.get(v, false):
in_both_arrays.append(v)
return in_both_arrays
The reason this is faster, is because the lookup speed for dictionaries is much faster than the lookup speed for an element in an array (since that has to go over every single element). So this code should be able to handle much larger inputs.