custom_insert_test.go

package main

import (
  "fmt"
	"math/rand"
	"time"
	"github.com/sajari/regression"
	"gonum.org/v1/plot"
	"gonum.org/v1/plot/vg"
	"gonum.org/v1/plot/plotter"
)

func insert(a []int, c int, i int) []int {
	return append(a[:i], append([]int{c}, a[i:]...)...)
}

func benchmark(f func()) func() time.Duration {
	return func() time.Duration {
		now := time.Now() // before code execution
		f()
		return time.Since(now)
	}
}

func generate(N int) []int {
	var a []int
	for i := 0; i < N; i++ {
		a = append(a, rand.Intn(100))
	}
	return a
}

func testNOperations(N int) time.Duration {
	arr := generate(N)
	insertOps := N
	var t time.Duration
	for i := 0; i < insertOps; i++ {
		t = t + benchmark(func() {
			insert(arr, rand.Intn(100), rand.Intn(N))
		})()
	}
	var avg time.Duration = time.Duration(int64(float64(t) / float64(insertOps)))
	fmt.Printf("Test array size: %d, avg time spent inserting: %s\n", N, avg.String())
	return avg
}

type DataPoint struct {
	Avg time.Duration
	N   int
}

func buildModel() {
	ns := []int{10, 100, 200, 
		300, 400, 500, 
		600, 700, 800, 
		1_000, 2_000, 3_000, 
		5_000, 10_000, 20_000, 
		30_000, 40_000, 50_000,
	}
	obs := []DataPoint{}
	for _, N := range ns {
		obs = append(obs, DataPoint{Avg: testNOperations(N), N: N})
	}

	plotObs(obs)
	r := new(regression.Regression)
	r.SetObserved("Avg time spent inserting element in the array")
	r.SetVar(0, "N, size of array")
	dp := regression.DataPoints{}
	for _, o := range obs {
		dp = append(dp, regression.DataPoint(float64(o.Avg), []float64{float64(o.N)}))
	}
	r.Train(dp...)
	r.Run()

	fmt.Printf("Regression formula:\n%v\n", r.Formula)
	fmt.Printf("Regression:\n%s\n", r)
	c := r.GetCoeffs()
	fmt.Printf("Model coefficients %v", c)
}

func plotObs(vs []DataPoint) {
	p := plot.New()
	p.Title.Text = "Avg time spent inserting element in the slice"

	points := plotter.XYs{}
	for _, v := range vs {
		points = append(points, plotter.XY{X: float64(v.N), Y: float64(v.Avg)})
	}

	scatter, err := plotter.NewScatter(points)

	if err != nil {
		panic(err)
	}
	p.Add(scatter)

	if err := p.Save(3*vg.Inch, 3*vg.Inch, "avg_slice_insert.png"); err != nil {
		panic(err)
	}
}

func main() {
	buildModel()
}