diff options
| -rw-r--r-- | Makefile | 4 | ||||
| -rw-r--r-- | queue/elementarypq.go | 9 | ||||
| -rw-r--r-- | queue/pq.go | 1 | ||||
| -rw-r--r-- | queue/pq_test.go | 37 |
4 files changed, 47 insertions, 4 deletions
@@ -4,9 +4,11 @@ run: go run main.go test: go test ./... -v -bench: sortbench +bench: sortbench queuebench sortbench: go test -run=xxx -bench=. ./sort | tee sortbench.out +queuebench: + go test -run=xxx -bench=. ./queue | tee queuebench.out profile: go test -run=xxx -bench=BenchmarkQuickSort ./sort -memprofile memprofile.out -cpuprofile cpuprofile.out go tool pprof cpuprofile.out 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() + } + } + }) +} |