Возьми некоторые данные, верни чистую кусочную функцию

Question

Учитывая список точек данных {x, y}, верните чистую функцию f (от действительных значений до действительных), такую, что f [x] == y для каждого {x, y} в данных. Если x не является одним из значений x, тогда возвращает значение y для предыдущей точки (значение со значением x меньше, чем x). Если функция получает значение меньше значения первого значения x в данных, т. Е. Предыдущая точка отсутствует, то возвращается 0.

Например, данные {{1,20}, {2,10}} возвращают чистую функцию, которая выглядит следующим образом:

График заданной функции {{1,20}, {2,10}} http://yootles.com/outbox/so/piecewise.png

Я написал что-то, используя Function и Piecewise, которые я включу в качестве ответа, но кажется, что это может быть неэффективно, особенно для большого списка пунктов. [ОБНОВЛЕНИЕ: мой ответ на самом деле может быть приличным сейчас. Я, наверное, пойду с этим, если у кого-то нет идей получше.

Для ясности, мы ищем функцию, которая принимает один аргумент - список пар чисел - и возвращает чистую функцию. Эта чистая функция должна принимать число и возвращать число.

Answer 1

Двоичный поиск с ручным кодированием

Если кто-то готов пожертвовать краткостью ради производительности, тогда подход императивного двоичного поиска работает хорошо:

stepifyWithBinarySearch[data_] :=
  With[{sortedData = SortBy[data, First], len = Length @ data}
  , Module[{min = 1, max = len, i, x, list = sortedData}
    , While[min <= max
      , i = Floor[(min + max) / 2]
      ; x = list[[i, 1]]
      ; Which[
          x == #, min = max = i; Break[]
        , x < #, min = i + 1
        , True, max = i - 1
        ]
      ]
    ; If[0 == max, 0, list[[max, 2]]]
    ]&
  ]

Оборудованнекоторые испытательные леса ...

test[s_, count_] :=
  Module[{data, f}
  , data = Table[{n, n^2}, {n, count}]
  ; f = s[data]
  ; Timing[Plot[f[x], {x, -5, count + 5}]]
]

... мы можем протестировать и рассчитать различные решения:

test[stepifyWithBinarySearch, 10]

На моей машине следующеевремя получено:

test[stepify (*<a href="/6410513/vozmi-nekotorye-dannye-verni-chistuy-kusochnuy-funktsiy#6410535">version 1</a>*), 100000]      57.034 s
test[stepify (*<a href="https://stackoverflow.com/questions/6853787/take-some-data-return-a-pure-piecewise-function/6853819#6853819">version 2</a>*), 100000]      40.903 s
test[stepifyWithBinarySearch, 100000]     2.902 s

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

Еще лучше: предварительно вычисленная интерполяция (ответ на комментарий дривов)

Удивительно, что некомпилированный двоичный поиск с ручным кодированием превзошел бы встроенную функцию Mathematica.Возможно, это не так удивительно для Piecewise, поскольку, за исключением оптимизаций, на самом деле это просто прославленные выражения цепочки тестирования IF-THEN-ELSEIF произвольной сложности.Тем не менее, можно ожидать, что Interpolation будет намного лучше, так как он специально создан для этой задачи.

Хорошая новость заключается в том, что Interpolation действительно обеспечивает очень быстрое решение,при условии, что кто-то организует вычисление интерполяции только один раз:

stepifyWithInterpolation[data_] :=
  With[{f=Interpolation[
            {-1,1}*#& /@ Join[{{-9^99,0}}, data, {{9^99, data[[-1,2]]}}]
            , InterpolationOrder->0 ]}
    , f[-#]&
  ]

Это невероятно быстро, для выполнения test[stepifyWithInterpolation, 100000].

на моей машине требуется всего 0,016 секунды.

Answer 2

Вы также можете сделать это с Interpolation (с InterpolationOrder->0), но это интерполирует, используя значение следующей точки вместо предыдущей.Но потом я понял, что вы можете изменить это с помощью простого трюка с двойным отрицанием:

stepify[data_] := Function[x,
  Interpolation[{-1,1}*#& /@ Join[{{-9^99,0}}, data, {{9^99, data[[-1,2]]}}],
                InterpolationOrder->0][-x]]

Answer 3

Мои предыдущие попытки не работали должным образом (они были в порядке только для двух шагов).

Я думаю, что следующий, в том же духе, работает:

g[l_] := Function[x, 
  Total[#[[2]] UnitStep[x - #[[1]]] & /@ 
    Transpose@({First@#, Differences[Join[{0}, Last@#]]} &@ Transpose@l)]]

Plot[g[{{1, 20}, {2, 10}, {3, 20}}][x], {x, 0, 6}]

Answer 4

Компиляция ответа WReach действительно приводит к значительному ускорению. Использование всех функций, определенных в ответе WReach, но переопределение с test на

test[s_,count_]:=Module[{data,f},
    data=Table[{n,n^2},
        {n,count}];
        f=s[ToPackedArray[N@data]];
        Timing[Plot[f[x],{x,-5,count+5}]]]

(это необходимо для упаковки полученных массивов; спасибо Sjoerd de Vries за указание на это) и определение

ClearAll[stepifyWRCompiled];
stepifyWRCompiled[data_]:=With[{len=Length@data,sortedData=SortBy[data,First]},
Compile[{{arg,_Real}},Module[{min=1,max=len,i,x,list=sortedData},
            While[
                min<=max,
                i=Floor[(min+max)/2];
                    x=list[[i,1]];
                    Which[
                        x\[Equal]arg,min=max=i;Break[],
                        x<arg,min=i+1,True,max=i-1
                    ]
            ];
            If[0==max,0,list[[max,2]]]
        ],CompilationTarget->"WVM",RuntimeOptions\[Rule]"Speed"]]

(блок With необходим для явной вставки sortedData в блок кода, подлежащего компиляции), мы получаем результаты быстрее, чем решение, использующее Interpolation, хотя лишь незначительно, так:

Monitor[
tbl = Table[
    {test[stepifyWRCompiled, l][[1]],
        test[stepifyWithInterpolation, l][[1]],
        test[stepifyWithBinarySearch, l][[1]]},
        {l, 15000, 110000, 5000}], l]
tbl//TableForm
(*
0.002785    0.003154    0.029324
0.002575    0.003219    0.031453
0.0028      0.003175    0.034886
0.002694    0.003066    0.034896
0.002648    0.003002    0.037036
0.00272     0.003019    0.038524
0.00255     0.00325     0.041071
0.002675    0.003146    0.041931
0.002702    0.003044    0.045077
0.002571    0.003052    0.046614
0.002611    0.003129    0.047474
0.002604    0.00313     0.047816
0.002668    0.003207    0.051982
0.002674    0.00309     0.054308
0.002643    0.003137    0.05605
0.002725    0.00323     0.06603
0.002656    0.003258    0.059417
0.00264     0.003029    0.05813
0.00274     0.003142    0.0635
0.002661    0.003023    0.065713
*)

(первый столбец - скомпилированный бинарный поиск, вторая интерполяция, третий, не скомпилированный бинарный поиск).

Обратите внимание, что я использую CompilationTarget->"WVM", а не CompilationTarget->"C"; это происходит потому, что функция компилируется с большим количеством «встроенных» точек данных, и, если я использую компиляцию в C с 100000 точек данных, я вижу, что gcc работает долго и занимает много памяти (Я полагаю, что полученный файл C огромен, но я не проверял). Поэтому я просто использую компиляцию для "WVM".

Я думаю, что общий вывод здесь заключается в том, что Interpolation также просто выполняет поиск в постоянном времени (бинарный поиск или что-то подобное, предположительно), и способ с ручным кодированием оказывается немного быстрее, потому что он менее общий.

Answer 5

работают следующие работы:

stp0[x_][{{x1_,y1_}, {x2_,y2_}}] := {y1, x1 <= x < x2}
stepify[{}] := (0&)
stepify[data_] := With[{x0 = data[[1,1]], yz = data[[-1,2]]},
  Function[x, Piecewise[Join[{{0, x<x0}}, stp0[x] /@ Partition[data, 2,1]], yz]]]

Обратите внимание, что без With в возвращаемой функции останутся такие, как {{1,10},{2,20}}[[1,1]], что выглядит немного расточительно.

Кстати, я решил назвать это stepify , поскольку он превращает список точек в пошаговую функцию.