Общее решение для отображения значений в массив

Question

Каков общий способ «сопоставить» произвольные значения (с точностью до определенного диапазона) до дискретных значений массива?

В основном то, что я хотел бы сделать, это предвычисление комплексной функции x = f(x) для диапазона дискретных входных значений x и хранить каждое значение выходного f(x) в другом массиве fx, так что есть два вектора:

• x - дискретные значения входных и
• fx - соответствующие дискретные выходные значения

Теперь для произвольное значение с диапазоном x Я хотел бы получить соответствующий результат от fx, e. г. для значения x1 = 42 и векторов

x = [ 30, 35, 40, 45, 50]; 
fx = [1.3, 1.8, 2.9, 4.5, 7.3]; 

функция, возможно, может вернуться

1. fx1 = 4.5 - отображение на fx, принимая x в качестве верхней границы
2. fx1 = 2.9 - отображение, чтобы fx принимать ближайшее значение из x
3. fx1 = 3.54 - картографирование fx проведение сим PLE линеаризация
   
   • fx1 = fxa + (fxb-fxa)/(xb-xa) * (x1-xa)
   • fx1 = 2.9 + (4.5-2.9)/(45-40) * (42-40)

Функция * должна быть очень быстро, так как он заменяет призвание "реальной" функции в тугой петлей. Первая попытка, которая используется, чтобы поместить в PRACTIVE случай один из верхнего списка выглядит следующим образом:

%% GET AT 
% Retrieve f(x). 
% 
% * Synopsis: getAt (x, input_map, output_map) 
% * Input : x   - function input 
%   : input_map - array with precomputed input values 
%   : output_map - array with precomputed output values 
% 
% * Output : fx   - function output 
%     
function fx = getAt (x, input_map, output_map) 
    n = length(input_map); 
    jj = length(find(input_map < x)); 

    if (jj >= n) 
     fx = 0; 
    else 
     fx = output_map(jj+1); 
    end 
end 

Однако я еще ищу решение C, поскольку цикл будет также в С.

* .. Просто ищет способ сделать это не для функция как в языке конструкция.

Answer 1

Я бы использовал линейную интерполяцию (ваше решение 3) с постоянной экстраполяцией, т. Е. Все ниже 30 карт до 1,3 и все за пределами от 50 до 7.3. Критически важной частью будет, вероятно, поиск правильного индекса массива.

Точная реализация зависит от того, насколько велики ваши дискретизированные массивы и как распределяются ваши входные значения. Например:

• Если ваши массивы малы или вы ожидаете, что многие значения находятся в нижнем конце диапазона ввода, линейный поиск может быть достаточно быстрым.
• Если ваши массивы большие и ваш вход равномерно распределен по диапазону, бинарный поиск может быть лучше.
• Если ваши входные образцы являются эквидистантными, поиск выполняется только одним делением с функцией пола или целочисленным преобразованием, поэтому это может быть наилучшим подходом.
• Вы можете заранее просчитать наклон каждого сегмента, поэтому вам не нужно каждый раз вычислять константу (fxb-fxa)/(xb-xa) * (x1-xa).

Множество «mays». Профилирование некоторых реализаций с использованием вашего прецедента должно помочь вам решить, как точно реализовать свою функцию поиска.

Answer 2

Сделайте двоичный поиск в массиве x, чтобы найти точное совпадение или две записи, которые дают интервал, содержащий ваш ввод. Для точного соответствия результатом является соответствующий (с тем же индексом) элемент fx как элемент x. Для неточного соответствия сделайте линейную интерполяцию, основанную на том, где вход лежит в интервале x0 ... x1 и применяет это к двум соответствующим элементам fx. Альтернативно, имея два параллельных массива, вы можете иметь один массив элементов, который содержит как значения x, так и fx.

Есть множество источников в Интернете для того, как сделать бинарный поиск массива, например,

Binary Search in Array

Это легко адаптировать их, чтобы получить правильную пару записей, когда нет точного соответствия. Вы должны быть осторожны с границами, хотя ... входные значения меньше, чем первый элемент массива x или больше, чем последний элемент.

Вы можете также рассмотреть поиск интерполяции:

http://en.wikipedia.org/wiki/Interpolation_search

, а не бинарный поиск, так как она требует линейной интерполяции между низкими и высокими пределами в любом случае. После того, как вы перейдете только к двум элементам x и не нашли точное совпадение, просто примените интерполяцию к соответствующим значениям fx.