取一些数据,返回一个纯粹的分段函数

Question

给定{x,y}数据点的列表,返回纯函数f(从实数到实数),使得数据中每个{x,y}的f [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

您也可以使用Interpolation(with InterpolationOrder->0)进行此操作,但是使用下一个点的值而不是之前的值进行插值.但后来我意识到你可以用一个简单的双否定技巧来扭转它:

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

Answer 2

我以前的尝试没有正常工作(只有两步才可以).

我认为下面的一行,按照相同的路线,有效:

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 3

手工编码二进制搜索

如果一个人愿意牺牲性能的简洁性,那么命令式二元搜索方法表现良好:

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 s
test[stepify (*version 2*), 100000]      40.903 s
test[stepifyWithBinarySearch, 100000]     2.902 s

我希望通过编译各种功能可以获得进一步的性能提升,但我会将其作为读者的练习.

更好的是:预先计算的插值 (响应dreeves的评论)

令人费解的是,手动编码的未编译二进制搜索将击败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[-#]&
  ]

这速度非常快,我的机器只需0.016秒即可执行test[stepifyWithInterpolation, 100000].