Commits

Anonymous committed 04898d6

Benchmarks!

Comments (0)

Files changed (2)

+// The set package implements efficient integer sets
 package set
 
 import (
 	"rand"
 )
 
+// IntSet provides an interface for general integer set operations.
 type IntSet interface {
+	// Initialize the set with elements from an array slice.
+	// Duplicates are ignored, of course.
  	Init(a []int) *IntSet
- 	Add(x int) *IntSet
+
+	// Insert a new element into the set.
+	// Non-destructive at the moment.
+ 	Insert(x int) *IntSet
+
+	// Tests whether the given element is contained in the set.
  	Elem(x int) bool
+
+	// Takes the union of the two sets, non-destructive.
  	Union(y IntSet) *IntSet
- 	Intersection(y *IntSet) *IntSet
+
+	// Union (parallel version!)
+	UnionPar(y IntSet) *IntSet
+	
+	// Takes the intersection of the two sets, non-destructive.
+	Intersection(y *IntSet) *IntSet
+
+	// Takes the set difference of the two sets.
 	Diff(y *IntSet) *IntSet
+
+	// remove me
 	Display()
 }
 
 func Init(a []int) *IntTreap {
 	var s *IntTreap = nil
 	for i := 0; i < len(a); i++ {
-		s = s.Add(a[i])
+		s = s.Insert(a[i])
 	}
 	return s
 }
 
-func (s *IntTreap) Add(x int) *IntTreap {
+func (s *IntTreap) Insert(x int) *IntTreap {
 	if (s == nil) {
 		s := new(IntTreap)
 		s.x = x
 		return s
 	} else if (s.x > x) {
 		if s.left != nil {
-			s.left = s.left.Add(x)
+			s.left = s.left.Insert(x)
 		} else {
 			s.left = NewIntTreap()
 			s.left.x = x
 		}
 	} else if (s.x < x) {
 		if s.right != nil {
-			s.right = s.right.Add(x)
+			s.right = s.right.Insert(x)
 		} else {
 			s.right = NewIntTreap()
 			s.right.x = x
 
 // broken goroutine version
 
-// func (s *IntTreap) Union(t *IntTreap) *IntTreap {
-// 	ch := make(chan *IntTreap)
-// 	go s.UnionHelper(t, ch)
-// 	u := <- ch
-// 	return u
-// }
+func (s *IntTreap) UnionPar(t *IntTreap) *IntTreap {
+	ch := make(chan *IntTreap)
+	if (s == nil) { return t }
+	if (t == nil) { return s }
+	go s.UnionHelper(t, ch)
+	u := <- ch
+	return u
+}
 
-// func (s *IntTreap) UnionHelper(t *IntTreap, ch chan *IntTreap) {
-// 	u := new(IntTreap)
-// 	if (s == nil) { ch <- t }
-// 	if (t == nil) { ch <- s }
-
-// 	if (s.p >= t.p) {
-// 		Tl, _, Tr := t.Split(s.x)
-// 		u.x = s.x
-// 		u.p = s.p
-// 		chl := make(chan *IntTreap)
-// 		chr := make(chan *IntTreap)
-// 		go s.left.UnionHelper(Tl, chl)
-// 		go s.right.UnionHelper(Tr, chr)
-// 		u.left = <-chl
-// 		u.right = <-chr
-// 		ch <- u
-// 	} else {
-// 		Sl, _, Sr := s.Split(t.x)
-// 		u.x = t.x
-// 		u.p = t.p
+func (s *IntTreap) UnionHelper(t *IntTreap, ch chan *IntTreap) {
+	u := new(IntTreap)
+	if (s == nil) {
+		ch <- t
+	} else if (t == nil) {
+		ch <- s
+	} else if (s.p >= t.p) {
+		Tl, _, Tr := t.Split(s.x)
+		u.x = s.x
+		u.p = s.p
+//		chl := make(chan *IntTreap)
+//		chr := make(chan *IntTreap)
+//		go s.left.UnionHelper(Tl, chl)
+//		go s.right.UnionHelper(Tr, chr)
+//		u.left = <-chl
+//		u.right = <-chr
+		u.left = s.left.Union(Tl)
+		u.right = s.right.Union(Tr)
+		ch <- u
+	} else {
+		Sl, _, Sr := s.Split(t.x)
+		u.x = t.x
+		u.p = t.p
 // 		chl := make(chan *IntTreap)
 // 		chr := make(chan *IntTreap)
 // 		go t.left.UnionHelper(Sl, chl)
 // 		go t.right.UnionHelper(Sr, chr)
 // 		u.left = <-chl
 // 		u.right = <-chr
-// 		ch <- u
-// 	}
-// }
+		u.left = s.left.Union(Sl)
+		u.right = s.right.Union(Sr)
+		ch <- u
+	}
+}
+
 
 func NewIntTreap() *IntTreap {
 	return new(IntTreap)
 )
 
 const (
-	ELEM_TEST_TRIES = 1000
+	ELEM_TEST_TRIES = 10
+	UNION_TEST_TRIES = 10
 )
 
+func randomizeSet(n int) *IntTreap {
+	s := Init([]int{})
+	for i := 0; i < n; i++ {
+		p := rand.Int()
+		s = s.Insert(p)
+	}
+	return s
+}
+
 func TestSanity (t *testing.T) {
 	fmt.Printf("this works!\n")
 }
 
-func TestSuit (test *testing.T) {
+func TestAddElem (test *testing.T) {
+	fmt.Printf("Testing TestElem...\n")
 	s := Init([]int{})
-	t := Init([]int{})
-	fmt.Printf("\n")
-	for i := 0; i < 4; i++ {
-		x := rand.Int()
-		y := rand.Int()
-		s = s.Add(x)
-		fmt.Printf("s: ")
-		s.Display()
-		fmt.Printf("\n")
-		t = t.Add(y)
-		fmt.Printf("t: ")
-		t.Display()
-		fmt.Printf("\n")
+	for i := 0; i < ELEM_TEST_TRIES; i++ {
+		p := rand.Int()
+		s = s.Insert(p)
+		if !s.Elem(p) {
+			test.Fail()
+		}
 	}
+}
+
+func TestUnion (test *testing.T) {
+	s := randomizeSet(UNION_TEST_TRIES)
+	t := randomizeSet(UNION_TEST_TRIES)
 	u := s.Union(t)
-	fmt.Printf("u: ")
 	u.Display()
-	fmt.Printf("\n")
+}		
+
+func TestParUnion (test *testing.T) {
+	fmt.Printf("Testing parallelized union...")
+	s := randomizeSet(UNION_TEST_TRIES)
+	t := randomizeSet(UNION_TEST_TRIES)
+	u := s.UnionPar(t)
+	u.Display()
 }
+
+func BenchmarkUnion (b *testing.B) {
+	s := randomizeSet(b.N)
+	t := randomizeSet(b.N)
+	s.Union(t)
+}
+
+func BenchmarkParUnion (b *testing.B) {
+	s := randomizeSet(b.N)
+	t := randomizeSet(b.N)
+	s.UnionPar(t)
+}	
+