From 24996416c11942abe22b1e3c1dee29243fd55fd1 Mon Sep 17 00:00:00 2001
From: Paul Buetow <pbuetow@mimecast.com>
Date: Mon, 24 Aug 2020 14:44:34 +0100
Subject: benchmark of pq

---
 queue/elementarypq.go |  9 ++++++++-
 queue/pq.go           |  1 +
 queue/pq_test.go      | 37 +++++++++++++++++++++++++++++++++++--
 3 files changed, 44 insertions(+), 3 deletions(-)

(limited to 'queue')

diff --git a/queue/elementarypq.go b/queue/elementarypq.go
index 31cab9f..1155cb4 100644
--- a/queue/elementarypq.go
+++ b/queue/elementarypq.go
@@ -5,10 +5,12 @@ import "algorithms/ds"
 type ElementaryPQ struct {
 	a    ds.ArrayList
 	size int
+	// Initial capacity
+	capacity int
 }
 
 func NewElementaryPQ(capacity int) ElementaryPQ {
-	return ElementaryPQ{make(ds.ArrayList, 0, capacity), 0}
+	return ElementaryPQ{make(ds.ArrayList, 0, capacity), 0, capacity}
 }
 
 func (q ElementaryPQ) Insert(a int) {
@@ -43,6 +45,11 @@ func (q ElementaryPQ) Size() int {
 	return q.size
 }
 
+func (q ElementaryPQ) Clear() {
+	q.size = 0
+	q.a = make(ds.ArrayList, 0, q.capacity)
+}
+
 func (q ElementaryPQ) max() (ind, max int) {
 	for i, a := range q.a {
 		if a > max {
diff --git a/queue/pq.go b/queue/pq.go
index ecf54c8..5f2079a 100644
--- a/queue/pq.go
+++ b/queue/pq.go
@@ -6,4 +6,5 @@ type PQ interface {
 	DeleteMax() int
 	Empty() bool
 	Size() int
+	Clear()
 }
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