Use log LUT rather than binary search for last mouse move point

2 files changed, 70 insertions, 16 deletions

diff --git a/grapher/Models/Calculations/AccelCalculator.cs b/grapher/Models/Calculations/AccelCalculator.cs
index f2a6c7c..5d3582c 100644
--- a/grapher/Models/Calculations/AccelCalculator.cs
+++ b/grapher/Models/Calculations/AccelCalculator.cs
@@ -67,6 +67,10 @@ namespace grapher.Models.Calculations
             double maxSlope = 0.0;
             double minSlope = Double.MaxValue;
 
+            double log = -2;
+            int index = 0;
+            int logIndex = 0;
+
             foreach (var magnitudeDatum in magnitudeData)
             {
                 if (magnitudeDatum.magnitude <=0)
@@ -77,6 +81,22 @@ namespace grapher.Models.Calculations
                 var output = accel.Accelerate(magnitudeDatum.x, magnitudeDatum.y, MeasurementTime);
                 var outMagnitude = Magnitude(output.Item1, output.Item2);
 
+                if (!data.VelocityPoints.ContainsKey(magnitudeDatum.magnitude))
+                {
+                    data.VelocityPoints.Add(magnitudeDatum.magnitude, outMagnitude);
+                }
+                else
+                {
+                    continue;
+                }
+
+                while (Math.Pow(10,log) < outMagnitude)
+                {
+                    data.LogToIndex[logIndex] = index;
+                    log += 0.01;
+                    logIndex++;
+                }
+
                 var ratio = magnitudeDatum.magnitude > 0 ? outMagnitude / magnitudeDatum.magnitude : starter;
                 
                 if (ratio > maxRatio)
@@ -108,11 +128,6 @@ namespace grapher.Models.Calculations
                     data.AccelPoints.Add(magnitudeDatum.magnitude, ratio);
                 }
 
-                if (!data.VelocityPoints.ContainsKey(magnitudeDatum.magnitude))
-                {
-                    data.VelocityPoints.Add(magnitudeDatum.magnitude, outMagnitude);
-                }
-
                 if (!data.GainPoints.ContainsKey(magnitudeDatum.magnitude))
                 {
                     data.GainPoints.Add(magnitudeDatum.magnitude, slope);
@@ -120,9 +135,18 @@ namespace grapher.Models.Calculations
 
                 lastInputMagnitude = magnitudeDatum.magnitude;
                 lastOutputMagnitude = outMagnitude;
+                index += 1;
+            }
+
+            index--;
+
+            while (log <= 4.0)
+            {
+                data.LogToIndex[logIndex] = index;
+                log += 0.01;
+                logIndex++;
             }
 
-            data.OrderedVelocityPointsList.AddRange(data.VelocityPoints.Values.ToList());
             data.MaxAccel = maxRatio;
             data.MinAccel = minRatio;
             data.MaxGain = maxSlope;
@@ -143,6 +167,10 @@ namespace grapher.Models.Calculations
 
             Sensitivity = GetSens(ref settings);
 
+            double log = -2;
+            int index = 0;
+            int logIndex = 0;
+
             foreach (var magnitudeDatum in magnitudeData)
             {
                 var output = accel.Accelerate(magnitudeDatum.x, magnitudeDatum.y, MeasurementTime);
@@ -155,6 +183,17 @@ namespace grapher.Models.Calculations
                 {
                     data.Combined.VelocityPoints.Add(magnitudeDatum.magnitude, magnitudeWithoutSens);
                 }
+                else
+                {
+                    continue;
+                }
+
+                while (Math.Pow(10,log) < magnitudeWithoutSens)
+                {
+                    data.Combined.LogToIndex[logIndex] = index;
+                    log += 0.01;
+                    logIndex++;
+                }
 
                 var xRatio = settings.sensitivity.x * ratio;
                 var yRatio = settings.sensitivity.y * ratio;
@@ -241,9 +280,18 @@ namespace grapher.Models.Calculations
                 lastInputMagnitude = magnitudeDatum.magnitude;
                 lastOutputMagnitudeX = xOut;
                 lastOutputMagnitudeY = yOut;
+                index += 1;
+            }
+
+            index--;
+
+            while (log <= 4.0)
+            {
+                data.Combined.LogToIndex[logIndex] = index;
+                log += 0.01;
+                logIndex++;
             }
 
-            data.Combined.OrderedVelocityPointsList.AddRange(data.Combined.VelocityPoints.Values.ToList());
             data.Combined.MaxAccel = maxRatio;
             data.Combined.MinAccel = minRatio;
             data.Combined.MaxGain = maxSlope;
diff --git a/grapher/Models/Calculations/AccelChartData.cs b/grapher/Models/Calculations/AccelChartData.cs
index 54685a2..98d501b 100644
--- a/grapher/Models/Calculations/AccelChartData.cs
+++ b/grapher/Models/Calculations/AccelChartData.cs
@@ -13,8 +13,8 @@ namespace grapher.Models.Calculations
             AccelPoints = new SortedDictionary<double, double>();
             VelocityPoints = new SortedDictionary<double, double>();
             GainPoints = new SortedDictionary<double, double>();
-            OrderedVelocityPointsList = new List<double>();
             OutVelocityToPoints = new Dictionary<double, (double, double, double)>();
+            LogToIndex = new int[601];
         }
 
         #endregion Constructors
@@ -35,7 +35,7 @@ namespace grapher.Models.Calculations
 
         public SortedDictionary<double, double> GainPoints { get; }
 
-        public List<double> OrderedVelocityPointsList { get; }
+        public int[] LogToIndex { get; }
 
         public Dictionary<double, (double, double, double)> OutVelocityToPoints { get; }
 
@@ -48,8 +48,8 @@ namespace grapher.Models.Calculations
             AccelPoints.Clear();
             VelocityPoints.Clear();
             GainPoints.Clear();
-            OrderedVelocityPointsList.Clear();
             OutVelocityToPoints.Clear();
+            Array.Clear(LogToIndex, 0, LogToIndex.Length);
         }
 
         public (double, double, double) FindPointValuesFromOut(double outVelocityValue)
@@ -80,15 +80,21 @@ namespace grapher.Models.Calculations
 
         public int GetVelocityIndex(double outVelocityValue)
         {
-            var velIdx = OrderedVelocityPointsList.BinarySearch(outVelocityValue);
-
-            if (velIdx < 0)
+            var log = Math.Log10(outVelocityValue);
+            if (log < -2)
+            {
+                log = -2;
+            }
+            else if (log > 4)
+            {
+                log = 4;
+            }
+            else
             {
-                velIdx = ~velIdx;
+                log = log * 100 + 200;
             }
 
-            velIdx = Math.Min(velIdx, VelocityPoints.Count - 1);
-            velIdx = Math.Max(velIdx, 0);
+            var velIdx = LogToIndex[(int)log];
 
             return velIdx;
         }