math - 取一些数据，返回一个纯分段函数

Question

给定一个 {x,y} 数据点列表，返回一个纯函数 f(从实数到实数)，对于数据中的每个 {x,y}，f[x]==y。如果 x 不是 x 值之一，则返回前一点(x 值小于 x 的点)的 y 值。如果函数得到的值小于数据中第一个 x 值的值——即没有前一个点——则返回 0。

例如，给定数据 {{1,20}, {2,10}}，返回一个如下所示的纯函数:

Graph of the function given {{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 (*version 1*), 100000]      57.034 stest[stepify (*version 2*), 100000]      40.903 stest[stepifyWithBinarySearch, 100000]     2.902 s

I expect that further performance gains could be obtained by compiling the various functions, but I'll leave that as an exercise for the reader.

Better Still: Precomputed Interpolation(response To dreeves' comment)

It is baffling that a hand-coded, uncompiled binary search would beat a Mathematica built-in function. It is perhaps not so surprising for Piecewise since, barring optimizations, it is really just a glorified IF-THEN-ELSEIF chain testing expressions of arbitrary complexity. However, one would expect Interpolation to fare much better since it is essentially purpose-built for this task.

The good news is that Interpolation does provide a very fast solution, provided one arranges to compute the interpolation only once:

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

这非常快，在我的机器上只需要 0.016 秒即可执行 test[stepifyWithInterpolation, 100000] .