From 24996416c11942abe22b1e3c1dee29243fd55fd1 Mon Sep 17 00:00:00 2001 From: Paul Buetow Date: Mon, 24 Aug 2020 14:44:34 +0100 Subject: benchmark of pq --- queue/pq_test.go | 37 +++++++++++++++++++++++++++++++++++-- 1 file changed, 35 insertions(+), 2 deletions(-) (limited to 'queue/pq_test.go') diff --git a/queue/pq_test.go b/queue/pq_test.go index 35e12fd..0b13144 100644 --- a/queue/pq_test.go +++ b/queue/pq_test.go @@ -7,8 +7,8 @@ import ( ) const minLength int = 1 -const maxLength int = 1000 -const factor int = 10 +const maxLength int = 10000 +const factor int = 100 func TestElementaryPQ(t *testing.T) { q := NewElementaryPQ(1) @@ -40,3 +40,36 @@ func test(q PQ, l int, t *testing.T) { } t.Run(fmt.Sprintf("%d", l), cb) } + +func BenchmarkElementaryPQ(b *testing.B) { + q := NewElementaryPQ(1) + for i := minLength; i <= maxLength; i *= factor { + benchmark(q, i, b) + } +} + +func benchmark(q PQ, l int, b *testing.B) { + r := ds.NewRandomArrayList(l, -1) + aux := ds.NewArrayList(l) + + b.Run(fmt.Sprintf("randomInsert(%d)", l), func(b *testing.B) { + for i := 0; i < b.N; i++ { + q.Clear() + for _, a := range r { + q.Insert(a) + } + } + }) + + b.Run(fmt.Sprintf("randomInsertAndDeleteMax(%d)", l), func(b *testing.B) { + for i := 0; i < b.N; i++ { + q.Clear() + for _, a := range r { + q.Insert(a) + } + for i := 0; !q.Empty(); i++ { + aux[i] = q.DeleteMax() + } + } + }) +} -- cgit v1.2.3