Algorithm to find matching real values in a list

Algorithm to find matching real values in a list

I have a complex algorithm which calculates the result of a function f(x). In the real world f(x) is a continuous function. However due to rounding errors in the algorithm this is not the case in the computer program. The following diagram gives an example:

Furthermore I have a list of several thousands values Fi.

I am looking for all the x values which meet an Fi value i.e. f(xi)=Fi

I can solve this problem with by simply iterating through the x values like in the following pseudo code:

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])

Of course it is necessary to use a high number of checks. Otherwise I will miss some x values. The higher the number of checks the more complete and accurate is the result. It is acceptable that the list is 90% or 95% complete.

The problem is that this brute force approach takes too much time. As I mentioned before the algorithm for f(x) is quite complex and with a high number of checks it takes too much time.

What would be a better solution for this problem?

Answer by Tomer W for Algorithm to find matching real values in a list

the best methods will relay on the nature of your function f(x).

1. The best solution is if you can create the reversing to F(x) and use it

2. as you said F(x) is continuous:
   therefore you can start evaluating small amount of far points, then find ranges that makes sense, and refine your "assumption" for x that f(x)=Fi
   it is not bullet proof, but it is an option.

   e.g. Fi=5.7; f(1)=1.4 ,f(4)=4,f(16)=12.6, f(10)=10.1, f(7)=6.5, f(5)=5.1, f(6)=5.8, you can take 5 < x < 7

3. on the same line as #1, and IF F(x) is hard to calculate, you can use Interpolation, and then evaluate F(x) only at the values that are probable.

Answer by samgak for Algorithm to find matching real values in a list

1. Sort the list, producing an array SortedListValues that contains the sorted ListValues and an array SortedListValueIndices that contains the index in the original array of each entry in SortedListValues. You only actually need the second of these and you can create both of them with a single sort by sorting an array of tuples of (value, index) using value as the sort key.

2. Iterate over your range in 0..NumberOfChecks-1 and compute the value of the function at each step, and then use a binary chop method to search for it in the sorted list.

Pseudo-code:

// sort as described above  SortedListValueIndices = sortIndices(ListValues);    for i=0 to NumberOfChecks-1 do  begin      //calculate the function result with the algorithm    x=i*(xmax-xmin)/NumberOfChecks;    FunctionResult=CalculateFunctionResultWithAlgorithm(x);      // do a binary chop to find the closest element in the list    highIndex = NumberOfValuesInTheList-1;    lowIndex = 0;    while true do    begin       if Abs(FunctionResult-ListValues[SortedListValueIndices[lowIndex]])

numberofvaluesinthelist-1="" do="" if="" abs(functionresult-listvalues[sortedlistvalueindices[j]])="">=Epsilon then break //mark that element SortedListValueIndices[j] of the list matches //and store the corresponding x value in the list end // break out of the binary chop loop break end // break out of the loop once the indices match if highIndex <= lowIndex then break // do the binary chop searching, adjusting the indices: middleIndex = (lowIndex + 1 + highIndex) / 2; if ListValues[SortedListValueIndices[middleIndex] < FunctionResult then lowIndex = middleIndex; else begin highIndex = middleIndex; lowIndex = lowIndex + 1; end end end

Possible complications:

• The binary chop isn't taking the epsilon into account. Depending on your data this may or may not be an issue. If it is acceptable that the list is only 90 or 95% complete this might be ok. If not then you'll need to widen the range to take it into account.
• I've assumed you want to be able to match multiple x values for each FunctionResult. If that's not necessary you can simplify the code.

Answer by Jim Mischel for Algorithm to find matching real values in a list

Another way to do this is in two parts: generate all of the results, sort them, and then merge with the sorted list of existing results.

First step is to compute all of the results and save them along with the x value that generated them. That is:

results = list of     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  

Now, sort the results list by FunctionResult, and also sort the FunctionResult-ListValues array by result.

You now have two sorted lists that you can move through linearly:

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      }  }  

Answer by Stormwind for Algorithm to find matching real values in a list

Naturally this depends very much on the data, and especially on the numeric distribution of Fi. Another problem is that the f(x) looks very jumpy, eliminating the concept of "assumption of nearby value".

But one could optimise the search.

Picture below.

1. Walking through F(x) at sufficient granularity, define a rough min (red line) and max (green line), using suitable tolerance (the "air" or "gap" in between). The area between min and max is "AREA".
2. See where each Fi-value hits AREA, do a stacked marking ("MARKING") at X-axis accordingly (can be multiple segments of X).
3. Where lots of MARKINGs at top of each other (higher sum - the vertical black "sum" arrows), do dense hit tests, hence increasing the overall chance to get as many hits as possible. Elsewhere do more sparse tests.
4. Tighten this schema (decrease tolerance) as much as you dare.
5. EDIT: Fi is a bit confusing. Is it an ordered array or does it have random order (as i assumed)?

Answer by Ravi for Algorithm to find matching real values in a list

Jim Mischel's solution would work in a O(i+j) instead of the O(i*j) solution that you currently have. But, there is a (very) minor bug in his code. The correct code would be :

    diff = ListValues[j] - results[i]; //no abs() here      if (abs(diff) < Episilon) //add abs() here      {          // mark this one with the x value          // and move to the next result          i = i + 1      }  

Fatal error: Call to a member function getElementsByTagName() on a non-object in D:\XAMPP INSTALLASTION\xampp\htdocs\endunpratama9i\www-stackoverflow-info-proses.php on line 72