0 votes

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.

in Engine by (55 points)

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

1 Answer

+1 vote
Best answer

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: https://docs.godotengine.org/en/stable/tutorials/optimization/general_optimization.html#principles

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?

by (1,114 points)
selected by

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 :)

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.

Welcome to Godot Engine Q&A, where you can ask questions and receive answers from other members of the community.

Please make sure to read How to use this Q&A? before posting your first questions.
Social login is currently unavailable. If you've previously logged in with a Facebook or GitHub account, use the I forgot my password link in the login box to set a password for your account. If you still can't access your account, send an email to webmaster@godotengine.org with your username.