trees_bench_test.go

package tree_test

import (
	"math/rand"
	"sort"
	"testing"

	avl "github.com/emirpasic/gods/trees/avltree"
	"github.com/emirpasic/gods/utils"
)

func TestTrav(t *testing.T) {
	tree := avl.NewWith(utils.Int64Comparator)
	for i := 0; i < 10000; i++ {
		tree.Put(rand.Int63n(1000), nil)
	}

	floor, ok := tree.Floor(int64(1))
	if !ok {
		t.Fatal("Expected ok to be true")
	}

	var values []int64
	trav(floor, true, false, func(i int64) bool {
		values = append(values, i)
		return true
	})

	if values[0] <= 0 {
		t.Fatalf("Expected first value (%d) to be greater than floor (1)", values[0])
	}

	if !sort.IsSorted(int64s(values)) {
		t.Fatal("Expected ints to be sorted")
	}
}

type int64s []int64

func (i int64s) Len() int           { return len(i) }
func (i int64s) Less(a, b int) bool { return i[a] < i[b] }
func (i int64s) Swap(a, b int) {
	tmp := i[a]
	i[a] = i[b]
	i[b] = tmp
}

func trav(n *avl.Node, skipLeft, skipParent bool, f func(int64) bool) {
	if n == nil {
		return
	}

	if !skipLeft {
		trav(n.Children[0], false, true, f)
	}

	if !f(n.Key.(int64)) {
		return
	}

	trav(n.Children[1], false, true, f)

	if !skipParent {
		trav(n.Parent, true, false, f)
	}
}

func BenchmarkTreeInsertLinear(b *testing.B) {
	tree := avl.NewWith(utils.Int64Comparator)

	b.ResetTimer()

	var j int64
	for i := 0; i < b.N; i++ {
		j += rand.Int63n(2)
		tree.Put(j, nil)
	}
}

func BenchmarkTreeInsertLinearWhileBounded(b *testing.B) {
	tree := avl.NewWith(utils.Int64Comparator)

	for i := int64(0); i < 1000; i++ {
		tree.Put(i, nil)
	}

	b.ResetTimer()

	var j int64
	for i := 0; i < b.N; i++ {
		j += rand.Int63n(2)
		tree.Put(j, nil)

		// Always remove the oldest entry
		tree.Remove(tree.Left().Key)
	}
}

func BenchmarkTreeFloor_1000000(b *testing.B) {
	M := 1000000
	tree := avl.NewWith(utils.Int64Comparator)

	var j int64
	for i := 0; i < M; i++ {
		j += rand.Int63n(5)
		tree.Put(j, nil)
	}

	b.ResetTimer()

	for i := 0; i < b.N; i++ {
		floor, _ := tree.Floor(int64(i % M))
		_ = floor
	}
}

func BenchmarkTreeRange_10000(b *testing.B) {
	var M int64 = 100000
	tree := avl.NewWith(utils.Int64Comparator)

	for i := int64(0); i < M; i++ {
		tree.Put(i, nil)
	}

	b.ResetTimer()

	for i := 0; i < b.N; i++ {
		f := int64(i) % M
		floor, _ := tree.Floor(f)
		trav(floor, true, false, func(x int64) bool {
			return x <= f+10000
		})
	}
}

func BenchmarkTreeRange_1000(b *testing.B) {
	var M int64 = 100000
	tree := avl.NewWith(utils.Int64Comparator)

	for i := int64(0); i < M; i++ {
		tree.Put(i, nil)
	}

	b.ResetTimer()

	for i := 0; i < b.N; i++ {
		f := int64(i) % M
		floor, _ := tree.Floor(f)
		trav(floor, true, false, func(x int64) bool {
			return x <= f+1000
		})
	}
}

func BenchmarkTreeRange_100(b *testing.B) {
	var M int64 = 100000
	tree := avl.NewWith(utils.Int64Comparator)

	for i := int64(0); i < M; i++ {
		tree.Put(i, nil)
	}

	b.ResetTimer()

	for i := 0; i < b.N; i++ {
		f := int64(i) % M
		floor, _ := tree.Floor(f)
		trav(floor, true, false, func(x int64) bool {
			return x <= f+100
		})
	}
}

func BenchmarkTreeRange_10(b *testing.B) {
	var M int64 = 100000
	tree := avl.NewWith(utils.Int64Comparator)

	for i := int64(0); i < M; i++ {
		tree.Put(i, nil)
	}

	b.ResetTimer()

	for i := 0; i < b.N; i++ {
		f := int64(i) % M
		floor, _ := tree.Floor(f)
		trav(floor, true, false, func(x int64) bool {
			return x <= f+10
		})
	}
}