Efficiency of FindFirstChild With Large Lists?
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.
0
0
1 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:FindFirstChildwasn'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.