在列表中查找匹配实值的算法

Question

我有一个复杂的算法来计算函数 f(x) 的结果。在现实世界中，f(x) 是一个连续函数。然而，由于算法中的舍入误差，计算机程序中的情况并非如此。下图给出了一个例子:

此外，我还有一个包含数千个值 Fi 的列表。

我正在寻找满足 Fi 值的所有 x 值，即 f(xi)=Fi

我可以通过像下面的伪代码一样简单地遍历 x 值来解决这个问题:

for i=0 to NumberOfChecks-1 do
begin

  //calculate the function result with the algorithm
  x=i*(xmax-xmin)/NumberOfChecks;
  FunctionResult=CalculateFunctionResultWithAlgorithm(x);

  //loop through the value list to see if the function result matches a value in the list
  for j=0 to NumberOfValuesInTheList-1 do
  begin
    if Abs(FunctionResult-ListValues[j])<Epsilon then
    begin
      //mark that element j of the list matches 
      //and store the corresponding x value in the list
    end
  end

end

当然要用到大量的检查。否则我会错过一些 x 值。检查的次数越多，结果就越完整和准确。列表完成 90% 或 95% 是可以接受的。

问题是这种蛮力方法需要花费太多时间。正如我之前提到的，f(x) 的算法非常复杂，并且需要大量检查，这会花费太多时间。

对于这个问题，什么是更好的解决方案？

Answer 1

另一种方法分为两部分:生成所有结果，对它们进行排序，然后与现有结果的排序列表合并。

第一步是计算所有结果并将它们与生成它们的 x 值一起保存。即:

results = list of <x, result>

for i = 0 to numberOfChecks
    //calculate the function result with the algorithm
    x=i*(xmax-xmin)/NumberOfChecks;
    FunctionResult=CalculateFunctionResultWithAlgorithm(x);
    results.Add(x, FunctionResult)
end for

现在，按 FunctionResult 对 results 列表进行排序，并按结果对 FunctionResult-ListValues 数组进行排序。

您现在有两个可以线性移动的排序列表:

i = 0, j = 0;
while (i < results.length && j < ListValues.length)
{
    diff = ListValues[j] - results[i];
    if (Abs(diff) < Episilon)
    {
        // mark this one with the x value
        // and move to the next result
        i = i + 1
    }
    else if (diff > 0)
    {
        // list value is much larger than result. Move to next result.
        i = i + 1
    }
    else
    {
        // list value is much smaller than result. Move to next list value.
        j = j + 1
    }
}