How to get closest value in array and interpolate real

Question

i have a text file with 10.000 lines and this content:

16500000000 -11.6560625775

16600000000 -11.99428283515

16700000000 -12.06410749998

16800000000 -11.81220239236

I want to create a function in c# where i pass the filename, and a number of the first column. Then the output is the value of the second column. In case that the number is not found in column1, it should interpolate the value.

Means, when i enter 16600000000 then function returns -11.99428283515.

When i enter 16650000000 then function should interpolate the value between 166.. and 167...

Currently i have this code, but without interpolation.

How can this be done better with interpolation(and fast):

public static int GetPw(string filePath, double Freq, out double power, out string errMsg)
    {
        power = Double.MinValue;
        errMsg = "No error";
        try
        {


            string[] lines = File.ReadAllLines(filePath);
            var filteredLines = lines.Where(line => !line.Contains("#") && !line.Contains("!") && !line.Contains("IND"));
            var splitLines = filteredLines.Select(line => line.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries));
            var validLines = splitLines.Where(parts => parts.Length >= 2);
            var sortedLines = validLines.OrderBy(parts => Math.Abs(float.Parse(parts[0]) - targetFrequency));
            string closestPower = sortedLines.Select(parts => parts[1]).FirstOrDefault();


            if (!Double.TryParse(closestPower, CultureInfo.InvariantCulture, out power))
            {
                power = Double.MinValue;
                throw new InvalidCastException($"{power} is not a valid power value");
            }
        }
        catch (Exception e)
        {
            errMsg=e.Message;
            return -1;
        }
        return 0;
    }

Answer 1

If you have read data into a ordered collection, say List<(double x, double y)>

var data = new List<(double x, double y)> {
  (1, 123),
  (2, 234),
  (3, 345),
};

and you are looing for linear interpolation, you can try binary search, i.e.

private static double Interpolate(List<(double x, double y)> list, double x) {
  if (list is null || list.Count == 0)
    return double.NaN; // or throw exception

  if (list.Count == 1)
    return list[0].y;

  var index = list.BinarySearch((x, 0),
    Comparer<(double x, double y)>.Create((left, right) => left.x.CompareTo(right.x)));

  if (index >= 0)
    return list[index].y;

  int leftIndex = ~index - 1;

  if (leftIndex < 0)
    leftIndex = 0;

  int rightIndex = leftIndex + 1;

  if (rightIndex == list.Count) {
    leftIndex -= 1;
    rightIndex -= 1;
  }

  double xa = list[leftIndex].x;
  double ya = list[leftIndex].y;

  double xb = list[rightIndex].x;
  double yb = list[rightIndex].y;

  return ya + (x - xa) / (xb - xa) * (yb - ya);
}

Let's have a look:

var y = Interpolate(data, 1.5);

// 178.5
Console.WriteLine(y);

Fiddle https://dotnetfiddle.net/zEDD5g

Answer 2

The OP has said that the dataset is in order and that it is tabulated at equal intervals in the first column. The only minor annoyance is that the first column has too many trailing zeroes to fit in a 32 bit integer so it will need to be either read into a long integer with 64 bits (or 64 bit floating point double). Since the data are tabulated at equal intervals we don't need to store them and it is sufficient to compute the index to lookup any input value x by knowing the baseindex value and stride for the first column.

This reduces to a simple array lookup with interpolation and is O(1).

eg.

 baseindex           data[0]
 baseindex+stride    data[1]
 baseindex+2*stride  data[2]
 ...
 baseindex+N*stride  data[N]

Assuming that the second column has been read into a suitable 0 index based array data[] then it is sufficient to compute the required entry as:

float index = ( x - baseindex)/stride;
result = data[ Math.Truncate(index) ];

If index is an exact integer then we are done otherwise linear interpolate:

result = data [index] + (index-Math.Truncate(index))*(data[index+1]-data[index])/stride;

I'm not sure of the semantics of C# so you may have to use Math.Truncate() make integer indices into your array or it might be OK by default rounding. You obviously have to use Truncate() or equivalent to obtain the fractional part for interpolating between two known data values from the table.

Based on the statement that the lookup is into a text file then the file will need to have the same record length for all entries so that the same logic can then be used to set the file pointer to the right start address (you will also need to read the first couple of entries to obtain baseindex and stride unless they are known).

For robust production code you might also want to consider what to do if x is less than baseindex or converts to an index beyond the length of the file.