Fast Array/Dictionary lookup containing ranges

Unity Engine
1

Hi, I’m trying to figure out a fast way to lookup an array/dictionary that contains a series of ranges/times.

Here’s an image to better illustrate:

each vertical line represents a frame. Each white diamond is an object and the horizontal bars represent their range if any.

given a time value of 10, how can I perform a quick lookup that would return every object that contains that time?

Possible solutions:

  • Generate some hashing algorithm for time values / ranges - don’t think it’s possible
  • Generate 2 arrays, 1 contains objects, the other contains the index of those objects at a particular frame. In other words, if I have 100 frames and 10 objects, I’ve got an 100 sized array of ints and a 10 sized array of objects - high memory usage
  • Brute force, iterate through the list of objects collecting valid items as you go
  • Interval tree - Interval tree - Wikipedia

The hashing algorithm would be ideal, unless the hashing algorithm was very complex. And I’m not sure if it’s even possible, how can you generate a number or string that can represent all of these numbers: 0,1,2,3,4,5,6,7 at once?

Currently, I’m leaning towards the 2 array approach.

*Wondering how unity handles this with its Animation, given a time, unity needs to figure out what keyframes exist and how far along their curves the time is at.

Thanks

2

I would just do brute force. It’s simple to implement and probably plenty fast, as long as you don’t have thousands of ranges. If you wanted to make it faster from there, you could do some very basic bucketing, just have an array of buckets where each bucket represents a range of frames and the intervals that overlap that range. Then you only need to search through that list of intervals and not all of the intervals in the timeline. The Interval Tree is probably the most correct solution, but also the most involved to implement.

In general, though, don’t speculatively optimize. Optimize this code if and when it becomes a bottleneck. Chances are, it never will be.

3

Thanks, I agree with your point about premature optimization, but this is part of a custom editor which allows a user to add as many objects and ranges as they please. So I would like to investigate more efficient options. These queries will be happening every frame so I’d like to have the system perform as best it can.