piecewiselinear

package module
v1.2.0 Latest Latest

This package is not in the latest version of its module.

Go to latest
Published: Dec 9, 2023 License: MIT

README ¶

piecewiselinear

A tiny library for linear interpolation. `O(log(N))` per evaluation for `N` control points.

``````import "github.com/sgreben/piecewiselinear"
``````

Get it

``````go get -u "github.com/sgreben/piecewiselinear"
``````

Use it

``````import "github.com/sgreben/piecewiselinear"

func main() {
f := piecewiselinear.Function{Y:[]float64{0,1,0}} // range: "hat" function
f.X = []float64{0, 0.5, 1}                        // domain: equidistant points along X axis
fmt.Println(
f.At(0),      // f.At(x) evaluates f at x
f.At(0.25),
f.At(0.5),
f.At(0.75),
f.At(1.0),
f.At(123.0),  // outside its domain X the function is constant 0
f.At(-123.0), //

f.Area(),
f.AreaUpTo(0.5),
)
// Output:
// 0 0.5 1 0.5 0 0 0 0.5 0.25
}
``````
Fast special case

If the control points are uniformly spaced, `piecewiselinear.FunctionUniform` is much faster (no search required):

``````import "github.com/sgreben/piecewiselinear"

func main() {
f := piecewiselinear.FunctionUniform{Y: []float64{0, 1, 0}} // range: "hat" function
f.Xmin, f.Xmax = 0, 1                                       // domain: equidistant points along X axis
fmt.Println(
f.At(0), // f.At(x) evaluates f at x
f.At(0.25),
f.At(0.5),
f.At(0.75),
f.At(1.0),
f.At(123.0),  // outside its domain X the function is constant 0
f.At(-123.0), //

f.Area(),
f.AreaUpTo(0.5),
)
// Output:
// 0 0.5 1 0.5 0 0 0 0.5 0.25
}
``````

Benchmarks

On an Apple M1 Pro:

• 6ns per evaluation (`.At(x)`) for 10 control points
• 320ns per evaluation for 10 million control points.

and, for `FunctionUniform`, 2ns per evaluation regardless of the number of control points.

``````goos: darwin
goarch: arm64
pkg: github.com/sgreben/piecewiselinear
BenchmarkAt4-10                 230890022                5.499 ns/op           0 B/op          0 allocs/op
BenchmarkAt8-10                 199668106                6.084 ns/op           0 B/op          0 allocs/op
BenchmarkAt10-10                192352903                6.206 ns/op           0 B/op          0 allocs/op
BenchmarkAt100-10               138742411                8.613 ns/op           0 B/op          0 allocs/op
BenchmarkAt1k-10                46360660                25.50 ns/op            0 B/op          0 allocs/op
BenchmarkAt10k-10               16649996                70.02 ns/op            0 B/op          0 allocs/op
BenchmarkAt100k-10              11696936               100.4 ns/op             0 B/op          0 allocs/op
BenchmarkAt1M-10                 8512652               140.6 ns/op             0 B/op          0 allocs/op
BenchmarkAt10M-10                3769648               320.4 ns/op             0 B/op          0 allocs/op
BenchmarkUniformAt10M-10        571224222                2.185 ns/op           0 B/op          0 allocs/op
``````

Documentation ¶

Overview ¶

Package piecewiselinear is a tiny library for linear interpolation.

Example
```f := Function{Y: []float64{0, 1, 0}} // range: "hat" function
f.X = []float64{0, 0.5, 1}           // domain: equidistant points along X axis
fmt.Println(
f.At(0), // f.At(x) evaluates f at x
f.At(0.25),
f.At(0.5),
f.At(0.75),
f.At(1.0),
f.At(123.0),  // outside its domain X the function is constant 0
f.At(-123.0), //

f.Area(),
f.AreaUpTo(0.5),
)
```
```Output:

0 0.5 1 0.5 0 0 0 0.5 0.25
```

Constants ¶

This section is empty.

Variables ¶

This section is empty.

Functions ¶

func Span ¶

`func Span(min, max float64, nPoints int) []float64`

Span generates `nPoints` equidistant points spanning [min,max]

Types ¶

type Function ¶

```type Function struct {
X []float64
Y []float64
}```

Function is a piecewise-linear 1-dimensional function

func (Function) Area ¶

`func (f Function) Area() (area float64)`

Area returns the definite integral of the function on its domain X.

Time complexity: O(N), where N is the number of points. Space complexity: O(1)

func (Function) AreaUpTo ¶

`func (f Function) AreaUpTo(x float64) (area float64)`

AreaUpTo returns the definite integral of the function on its domain X intersected with [-Inf, x].

Time complexity: O(N), where N is the number of points. Space complexity: O(1)

func (Function) At ¶

`func (f Function) At(x float64) float64`

At returns the function's value at the given point. Outside its domain X, the function is constant at 0.

The function's X and Y slices are expected to be the same legnth. The length property is _not_ verified. The function's X slice is expected to be sorted in ascending order. The sortedness property is _not_ verified.

Time complexity: O(log(N)), where N is the number of points. Space complexity: O(1)

func (Function) IsInterpolatedAt ¶

`func (f Function) IsInterpolatedAt(x float64) bool`

IsInterpolatedAt returns true if x is within the given range of points, false if outside of that range

type FunctionUniform ¶ added in v1.2.0

```type FunctionUniform struct {
Xmin, Xmax float64
Y          []float64
}```

Function is a piecewise-linear 1-dimensional function with uniformly spaced control points. Faster to interpolate than the equivalent `Function`.

func (FunctionUniform) Area ¶ added in v1.2.0

`func (f FunctionUniform) Area() (area float64)`

Area returns the definite integral of the function on its domain X.

Time complexity: O(N), where N is the number of points. Space complexity: O(1)

func (FunctionUniform) AreaUpTo ¶ added in v1.2.0

`func (f FunctionUniform) AreaUpTo(x float64) (area float64)`

AreaUpTo returns the definite integral of the function on its domain X intersected with [-Inf, x].

Time complexity: O(N), where N is the number of points. Space complexity: O(1)

func (FunctionUniform) At ¶ added in v1.2.0

`func (f FunctionUniform) At(x float64) float64`

At returns the function's value at the given point. Outside its domain X, the function is constant at 0.

Time complexity: O(1) Space complexity: O(1)

Keyboard shortcuts

 ? : This menu / : Search site f or F : Jump to y or Y : Canonical URL