Scripting HelpersARCHIVE
A little piece of Roblox history. Preserved for everyone, one question at a time.Read about the archive →
All questions/Question #61971
✓ ANSWER ACCEPTED

Efficiency of FindFirstChild With Large Lists?

Asked 499 views1 answers

Hey guys,

This isn't really much of a question related to specific code, but I was wondering how efficient FindFirstChild is with massive data sets. To my current understanding - and please correct me if I am wrong - FindFirstChild conducts a simple sequential search, meaning it traverses through all of the children of an object until it finds one with the specified name. However, say for data sets with up to 600 objects, would implementing a binary search rather than using FindFirstChild be drastically more efficient? In other words, how many objects should there be before binary searches perform noticeably faster than FindFirstChild in regards to input lag?

If anyone has experience with this, I'd appreciate any sort of feedback.

AnonymousEdited

2 comments

0

Well you could test this yourself using a timer and a few test datasets to see which preforms faster, but honestly if this is a question of lag, the difference to the player would not be noticeable on either search it uses.

Anonymous#
0

Ah, I just needed some clarification. Thanks

Anonymous#

1 answer

✓ Accepted answer

Some stuff to watch out for which I'm not really sure about

  • Does :GetChildren() guarantee an order of returned items? A binary search is impossible without an ordered list. If it did, I'd be very surprised if :FindFirstChild wasn't already binary.
  • How expensive is :GetChildren(). If it's an O(n) operation, you're getting diminishing returns from implementing your binary search - no matter how fast you make your search, you're still running an O(n) to get there. On the other hand, if it's an O(1) operation or something, it could be worthwhile.

In terms of theory, a binary search takes at most log_2(n) steps to locate the index of the required value. The crossover point for where linear search is less efficient than a binary search is an array with a size of about 8. So you're correct that for 600 objects a binary search would be better.

However, is it worth it? It really depends what code you're running. If you're running FindFirstChild on large data sets several times a second, then yeah go for it if possible.

If not, is it worth it? If this runs even as often as 10 seconds, the difference between searching for a child among 600 and 10 is probably so minute you won't even notice it. In return, you might end up having to cache a whole bunch of stuff to maintain an ordering to make binary searching possible in the first place. You're also spending time you could be spending optimising other, hotter areas of your codebase.

If :GetChildren() isn't ordered, and you're really looking to improve things, I suppose you could look into search sentinels. However, I'm not sure how :FindFirstChild is implemented. If it involves any C, it probably doesn't matter how efficient you write your Lua, C will kick its arse anyway.

AnonymousPermalink

This discussion is preserved as it was. New answers, comments, and votes are closed.