Which is the most efficient way to get a specific value from an array in gdscript?

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

I have a pretty big array with unique values from which I need specific values pretty often. The obvious way to do this (at least obvious to me) is:

for value in my_array:
  if value == specific_value:
     return value

If my specific value is at position x , this needs x steps to find it. Simple.

But I also happened to stumble across the find() function in array. So I thought of another way:

var needed_value_index = my_array.find(specific_value)
var needed_value = my_array[needed_value_index]
return needed_value

I guess there are even more ways to achieve what I want, but what I would really like to know, is how I find an efficient (possibly the most efficient) one.
I appreciate any advice on the matter.

Maybe there is an even better data structure than array to store my values. Maybe I should put some time into looking into this.

Ciavarie | 2020-10-08 11:14

:bust_in_silhouette: Reply From: Bernard Cloutier

A note on efficiency:
Here’s a famous quote by the inventor of Quicksort: “We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.”

You can find a fuller quote in the docs: General optimization tips — Godot Engine (stable) documentation in English

But in short, focus on correctness (your code does the right thing), rather than speed (unless it causes noticeable frame drops).
(END OF RANT)

Now about your question:
your approach is basically what the find method does. It’s quite possible that the find method is faster because it is implemented in C++ rather than gdscript, but I didn’t measure it and unless your array contains at least a few hundred elements, I doubt you’ll see much difference.

However, I don’t really understand why you need to find the value if you already have it. What I mean is if the statement if value == specific_value: equates to true, why not just return specific_value instead of going through the array? You’ve already proven the two values are equal.

Maybe your example is incomplete. Maybe your code is more like this:

func get_item(item_name: String):
    for item in self.item_list:
        if item.name == item\_name:
            return item
    return null

Although calling the find method like this: self.item_list.find(item_name) wouldn’t work, since the item list contains items and not strings. I am a bit confused by what you want to do. Could you share your whole script where you handle the array?

I have an array with my currently active quests. The specific value is just the quest I am searching for and I don`t always know if that certain quest is active and thus inside the array.

The array can contain quiet a lot of active quests, which is, why I was worrying about performance. But I guess I should not mind this too much.
And thank you for explaining what the find() method does :slight_smile:

Ciavarie | 2020-10-11 10:56

Oh, I see.

If you are worried about performance, instead of an array try a dictionary. Each dictionaty entry has a key and a value. In your case, the key could be the quest name or quest id, and the value is the actual quest. Then instead of find you would simply check quest_dictionary.has(quest_name). Dictionary lookup is O(1), meaning it’s instantaneous basically, as it does not have to iterate over each entry.

Bernard Cloutier | 2020-10-12 04:45