Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Resolved Fastest way to sample a float collection in ascending order

Discussion in 'Scripting' started by ADNCG, Jul 21, 2022.

  1. ADNCG

    ADNCG

    Joined:
    Jun 9, 2014
    Posts:
    992
    In the process of creating a replay system. I have a "Point" struct that stores position/rotation, which I then map to a time value.

    Interested classes can access a Dict<float, Point> where the float is the time at which the point was recorded.

    Entries keys will always be in ascending order.

    I'm trying to come up with a fast method that will return the point closest to a given time parameter. These dicts will typically contain around 1800-3600 entries and will be sampled 4-6 times per frame ideally.

    As of right now, my best bet is to come up with an algorithm that will break down the replay and recreate it with points set at fixed time intervals so that I can use basic arithmetic to fetch the index.

    I am however hoping I won't have to do that and some of you wizards out there might have an idea of how I could structure things to have this be a really fast op
     
  2. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,514
    I'm going to start by saying a Dict<float, X>, where a float (or double) is the key... is generally not a good idea.

    Due to the behaviour in regards to accuracy of floats, that's asking for problems when attempting to get an entry by float.

    Also, I wonder what you mean by this statement:
    Entries keys of what? Are you talking about the keys in the dictionary... the floats in <float, Point>?

    Cause uh, Dictionary's are inherent unsorted since they're hash tables. It uses the hash of the key to place it in the underlying collection... this way retrieving entries is an O(1) operation. It's just... not sorted.

    Are you maybe intending to say you desire for it to be sorted?

    Because there is a SortedDictionary that sorts based on the Key:
    https://docs.microsoft.com/en-us/do...tions.generic.sorteddictionary-2?view=net-6.0
    (note - it lacks the O(1) access, instead it's O(log(n)))

    SortedDictionary is implemented as a binary tree underneath giving its sorted nature.

    But I go back to the entire thing about the accuracy of floats impacting its use as a "key". That is unless you're implementing your own equality comparer that does a more fuzzy comparison of floats to account for the potential of float error.

    With this all said... a binary search is likely one of your best options for finding nearest neighbors in a large collection. It's similar to how in 3-space we might use an octree to find near points. The octree is just the 3d version of the 1d binary tree (2^3=8... bi=2, oct=8). And your situation is 1-dimensional (time).

    As for getting that...

    C# actually has a binary search built into List<T>.BinarySearch:
    https://docs.microsoft.com/en-us/do...ions.generic.list-1.binarysearch?view=net-6.0

    If you had a list of all your times, calling this will return a 0+ value if the time was found. Otherwise it returns a -/negative value that is the compliment of the nearest positive.

    Meaning if you take the ~ of the index... you got the index.

    Code (csharp):
    1. int index = timelist.BinarySearch(5.96f);
    2. if (index < 0)
    3. {
    4.     index = ~index; //convert index to the nearest index
    5. }
    6. //use index to use the nearest/direct match
    Note that timelist must be previously sorted... but you only have to sort any time an entry is added. And if you add them in sequence as you likely would in a timeline you can just assume it's sorted.

    Oh and I should point out... by 'nearest', I really mean "entry just larger than. So nearest AFTER.
     
    Last edited: Jul 21, 2022
    mopthrow, ADNCG and TheDevloper like this.
  3. Kurt-Dekker

    Kurt-Dekker

    Joined:
    Mar 16, 2013
    Posts:
    38,520
    Have you done the math on just storing the playback data linearly each frame?

    You might be surprised how small it would be, just structs packed into an array.

    For my Jetpack Kurt Space Flight game flight path replay and flight controls data log, I store some 36 bytes of data per frame at 60fps and that only works out to about 130k per minute of gameplay, which is only 7mb per HOUR of gameplay for the player. Most games are under a few minutes long, so it barely even shows up.

    Obviously if you have hundreds or thousands of entities things start to add up, but you can always do data compression tricks such as only storing every 10 frames, or vastly decreasing the precision of the data, or packing it into bitfields or sub-fields within integers.

    This is my struct: nine (9) 32-bit fields (either int or float) and I could have easily packed the flight controls into a single integer, since -100 to +100 would be adequate for each flight control channel.

    Code (csharp):
    1. using UnityEngine;
    2.  
    3. // @kurtdekker - a single flight datapoint in time, part of Jetpack Kurt Space Flight
    4.  
    5. public struct FlightDataDatapoint
    6. {
    7.     // We are NOT storing timeStamp. We are inferring this
    8.     // from using Time.fixedDeltaTime and the index number.
    9.  
    10.     public FlightDataEventFlags flags;
    11.  
    12.     public Vector3 position;
    13.  
    14.     //public Quaternion rotation;
    15.  
    16.     // control inputs, not orientation:
    17.     public float power, pitch, yaw, roll;
    18.  
    19.     // radar altimeter readout; this is not simply position.y!
    20.     public float altitude;
    21. }
    Simplest solution for the win.
     
    Last edited: Jul 21, 2022
    ADNCG and lordofduct like this.
  4. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,514
    Agreed with Kurt.

    Of course you can still tap that BinarySearch for a slight speed improvement if you are so concerned.

    Here's a trivial implementation and example of use:

    Code (csharp):
    1.    public class zTest02 : MonoBehaviour
    2.     {
    3.  
    4.         private void Start()
    5.         {
    6.             var coll = new ReplayCollection();
    7.             for (int i = 0; i < 10; i++)
    8.             {
    9.                 coll.Insert(new ReplayData()
    10.                 {
    11.                     Time = i,
    12.                     Position = Vector3.one * i,
    13.                     Rotation = Quaternion.Euler(i, i, i),
    14.                 });
    15.             }
    16.  
    17.             var entry = coll.FindNearest(4.2f);
    18.             Debug.Log(entry.Time + " : " + entry.Position.ToString());
    19.             entry = coll.FindNearest(4.6f);
    20.             Debug.Log(entry.Time + " : " + entry.Position.ToString());
    21.             entry = coll.FindNearest(12.2f);
    22.             Debug.Log(entry.Time + " : " + entry.Position.ToString());
    23.         }
    24.  
    25.     }
    26.  
    27.     public struct ReplayData
    28.     {
    29.  
    30.         public float Time;
    31.         public Vector3 Position;
    32.         public Quaternion Rotation;
    33.  
    34.     }
    35.  
    36.     public class ReplayCollection : IReadOnlyList<ReplayData>
    37.     {
    38.  
    39.         #region Fields
    40.  
    41.         private List<ReplayData> _keyframes = new List<ReplayData>();
    42.  
    43.         #endregion
    44.  
    45.         #region Methods
    46.  
    47.         public void Insert(ReplayData data)
    48.         {
    49.             if (_keyframes.Count == 0 || _keyframes[_keyframes.Count - 1].Time <= data.Time)
    50.             {
    51.                 _keyframes.Add(data);
    52.             }
    53.             else
    54.             {
    55.                 int index = _keyframes.BinarySearch(data, BinarySearchComparer.Default);
    56.                 if (index < 0) index = ~index;
    57.  
    58.                 _keyframes.Insert(index, data);
    59.             }
    60.         }
    61.  
    62.         public void InsertRange(IEnumerable<ReplayData> data)
    63.         {
    64.             _keyframes.AddRange(data);
    65.             _keyframes.Sort(BinarySearchComparer.Default);
    66.         }
    67.  
    68.         public ReplayData FindNearest(float time)
    69.         {
    70.             if (_keyframes.Count == 0) return default;
    71.  
    72.             int index = _keyframes.BinarySearch(SearchToken(time), BinarySearchComparer.Default);
    73.             if (index < 0) index = ~index;
    74.  
    75.             if (index == 0) return _keyframes[0];
    76.             if (index >= _keyframes.Count) return _keyframes[_keyframes.Count - 1];
    77.  
    78.             //actually get nearest rather than the one just after
    79.             var a = _keyframes[index - 1];
    80.             var b = _keyframes[index];
    81.             return (time - a.Time) < (b.Time - time) ? a : b;
    82.         }
    83.  
    84.         #endregion
    85.  
    86.         #region IReadOnlyList Interface
    87.  
    88.         public int Count => _keyframes.Count;
    89.  
    90.         public ReplayData this[int index] => _keyframes[index];
    91.  
    92.         public IEnumerator<ReplayData> GetEnumerator()
    93.         {
    94.             return _keyframes.GetEnumerator();
    95.         }
    96.  
    97.         IEnumerator IEnumerable.GetEnumerator()
    98.         {
    99.             return _keyframes.GetEnumerator();
    100.         }
    101.  
    102.         #endregion
    103.  
    104.         #region Utils
    105.  
    106.         private ReplayData SearchToken(float time) => new ReplayData() { Time = time };
    107.  
    108.         private class BinarySearchComparer : IComparer<ReplayData>
    109.         {
    110.  
    111.             public static readonly BinarySearchComparer Default = new BinarySearchComparer();
    112.  
    113.             public int Compare(ReplayData x, ReplayData y)
    114.             {
    115.                 return x.Time.CompareTo(y.Time);
    116.             }
    117.         }
    118.  
    119.         #endregion
    120.  
    121.     }
     
    ADNCG and Kurt-Dekker like this.
  5. ADNCG

    ADNCG

    Joined:
    Jun 9, 2014
    Posts:
    992
    @lordofduct Phew, thanks!

    I was not trying to get an entry by equal comparison of floats but rather get the entries immediately above and below the input time value and interpolate between them.

    I did however believe the order of dicts was persistent.

    Your solution is absolutely ideal. After your first comment, I attempted to implement it but was struggling with figuring out a way to compare time values whilst having a collection of type Point. Just saw your implementation and the dummy token's a far better idea than maintaining 2 parallel collections :oops:

    Thank you for the run-through and the implementation!

    @Kurt-Dekker I actually am! Problem is our market is hypercasual. Large portion of our users have obscure devices that will play the game at a lower/irregular frame rate. It's not a typical replay system in the sense that it replays dev sessions as pretend bots and thus needs to be in-sync with where the player would be at that time since the player can bump the bots into oblivion. Hence the need for some kind of time sampling.
     
    Kurt-Dekker likes this.