sparse_test.go

Documentation: golang.org/x/tools/container/intsets

     1  // Copyright 2014 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package intsets_test
     6  
     7  import (
     8  	"fmt"
     9  	"log"
    10  	"math/rand"
    11  	"sort"
    12  	"strings"
    13  	"testing"
    14  
    15  	"golang.org/x/tools/container/intsets"
    16  )
    17  
    18  func TestBasics(t *testing.T) {
    19  	var s intsets.Sparse
    20  	if len := s.Len(); len != 0 {
    21  		t.Errorf("Len({}): got %d, want 0", len)
    22  	}
    23  	if s := s.String(); s != "{}" {
    24  		t.Errorf("String({}): got %q, want \"{}\"", s)
    25  	}
    26  	if s.Has(3) {
    27  		t.Errorf("Has(3): got true, want false")
    28  	}
    29  	if err := s.Check(); err != nil {
    30  		t.Error(err)
    31  	}
    32  
    33  	if !s.Insert(3) {
    34  		t.Errorf("Insert(3): got false, want true")
    35  	}
    36  	if max := s.Max(); max != 3 {
    37  		t.Errorf("Max: got %d, want 3", max)
    38  	}
    39  
    40  	if !s.Insert(435) {
    41  		t.Errorf("Insert(435): got false, want true")
    42  	}
    43  	if s := s.String(); s != "{3 435}" {
    44  		t.Errorf("String({3 435}): got %q, want \"{3 435}\"", s)
    45  	}
    46  	if max := s.Max(); max != 435 {
    47  		t.Errorf("Max: got %d, want 435", max)
    48  	}
    49  	if len := s.Len(); len != 2 {
    50  		t.Errorf("Len: got %d, want 2", len)
    51  	}
    52  
    53  	if !s.Remove(435) {
    54  		t.Errorf("Remove(435): got false, want true")
    55  	}
    56  	if s := s.String(); s != "{3}" {
    57  		t.Errorf("String({3}): got %q, want \"{3}\"", s)
    58  	}
    59  }
    60  
    61  // Insert, Len, IsEmpty, Hash, Clear, AppendTo.
    62  func TestMoreBasics(t *testing.T) {
    63  	set := new(intsets.Sparse)
    64  	set.Insert(456)
    65  	set.Insert(123)
    66  	set.Insert(789)
    67  	if set.Len() != 3 {
    68  		t.Errorf("%s.Len: got %d, want 3", set, set.Len())
    69  	}
    70  	if set.IsEmpty() {
    71  		t.Errorf("%s.IsEmpty: got true", set)
    72  	}
    73  	if !set.Has(123) {
    74  		t.Errorf("%s.Has(123): got false", set)
    75  	}
    76  	if set.Has(1234) {
    77  		t.Errorf("%s.Has(1234): got true", set)
    78  	}
    79  	got := set.AppendTo([]int{-1})
    80  	if want := []int{-1, 123, 456, 789}; fmt.Sprint(got) != fmt.Sprint(want) {
    81  		t.Errorf("%s.AppendTo: got %v, want %v", set, got, want)
    82  	}
    83  
    84  	set.Clear()
    85  
    86  	if set.Len() != 0 {
    87  		t.Errorf("Clear: got %d, want 0", set.Len())
    88  	}
    89  	if !set.IsEmpty() {
    90  		t.Errorf("IsEmpty: got false")
    91  	}
    92  	if set.Has(123) {
    93  		t.Errorf("%s.Has: got false", set)
    94  	}
    95  }
    96  
    97  func TestTakeMin(t *testing.T) {
    98  	var set intsets.Sparse
    99  	set.Insert(456)
   100  	set.Insert(123)
   101  	set.Insert(789)
   102  	set.Insert(-123)
   103  	var got int
   104  	for i, want := range []int{-123, 123, 456, 789} {
   105  		if !set.TakeMin(&got) || got != want {
   106  			t.Errorf("TakeMin #%d: got %d, want %d", i, got, want)
   107  		}
   108  	}
   109  	if set.TakeMin(&got) {
   110  		t.Errorf("%s.TakeMin returned true", &set)
   111  	}
   112  	if err := set.Check(); err != nil {
   113  		t.Fatalf("check: %s: %#v", err, &set)
   114  	}
   115  }
   116  
   117  func TestMinAndMax(t *testing.T) {
   118  	values := []int{0, 456, 123, 789, -123} // elt 0 => empty set
   119  	wantMax := []int{intsets.MinInt, 456, 456, 789, 789}
   120  	wantMin := []int{intsets.MaxInt, 456, 123, 123, -123}
   121  
   122  	var set intsets.Sparse
   123  	for i, x := range values {
   124  		if i != 0 {
   125  			set.Insert(x)
   126  		}
   127  		if got, want := set.Min(), wantMin[i]; got != want {
   128  			t.Errorf("Min #%d: got %d, want %d", i, got, want)
   129  		}
   130  		if got, want := set.Max(), wantMax[i]; got != want {
   131  			t.Errorf("Max #%d: got %d, want %d", i, got, want)
   132  		}
   133  	}
   134  
   135  	set.Insert(intsets.MinInt)
   136  	if got, want := set.Min(), intsets.MinInt; got != want {
   137  		t.Errorf("Min: got %d, want %d", got, want)
   138  	}
   139  
   140  	set.Insert(intsets.MaxInt)
   141  	if got, want := set.Max(), intsets.MaxInt; got != want {
   142  		t.Errorf("Max: got %d, want %d", got, want)
   143  	}
   144  }
   145  
   146  func TestEquals(t *testing.T) {
   147  	var setX intsets.Sparse
   148  	setX.Insert(456)
   149  	setX.Insert(123)
   150  	setX.Insert(789)
   151  
   152  	if !setX.Equals(&setX) {
   153  		t.Errorf("Equals(%s, %s): got false", &setX, &setX)
   154  	}
   155  
   156  	var setY intsets.Sparse
   157  	setY.Insert(789)
   158  	setY.Insert(456)
   159  	setY.Insert(123)
   160  
   161  	if !setX.Equals(&setY) {
   162  		t.Errorf("Equals(%s, %s): got false", &setX, &setY)
   163  	}
   164  
   165  	setY.Insert(1)
   166  	if setX.Equals(&setY) {
   167  		t.Errorf("Equals(%s, %s): got true", &setX, &setY)
   168  	}
   169  
   170  	var empty intsets.Sparse
   171  	if setX.Equals(&empty) {
   172  		t.Errorf("Equals(%s, %s): got true", &setX, &empty)
   173  	}
   174  
   175  	// Edge case: some block (with offset=0) appears in X but not Y.
   176  	setY.Remove(123)
   177  	if setX.Equals(&setY) {
   178  		t.Errorf("Equals(%s, %s): got true", &setX, &setY)
   179  	}
   180  }
   181  
   182  // A pset is a parallel implementation of a set using both an intsets.Sparse
   183  // and a built-in hash map.
   184  type pset struct {
   185  	hash map[int]bool
   186  	bits intsets.Sparse
   187  }
   188  
   189  func makePset() *pset {
   190  	return &pset{hash: make(map[int]bool)}
   191  }
   192  
   193  func (set *pset) add(n int) {
   194  	prev := len(set.hash)
   195  	set.hash[n] = true
   196  	grewA := len(set.hash) > prev
   197  
   198  	grewB := set.bits.Insert(n)
   199  
   200  	if grewA != grewB {
   201  		panic(fmt.Sprintf("add(%d): grewA=%t grewB=%t", n, grewA, grewB))
   202  	}
   203  }
   204  
   205  func (set *pset) remove(n int) {
   206  	prev := len(set.hash)
   207  	delete(set.hash, n)
   208  	shrankA := len(set.hash) < prev
   209  
   210  	shrankB := set.bits.Remove(n)
   211  
   212  	if shrankA != shrankB {
   213  		panic(fmt.Sprintf("remove(%d): shrankA=%t shrankB=%t", n, shrankA, shrankB))
   214  	}
   215  }
   216  
   217  func (set *pset) check(t *testing.T, msg string) {
   218  	var eltsA []int
   219  	for elt := range set.hash {
   220  		eltsA = append(eltsA, int(elt))
   221  	}
   222  	sort.Ints(eltsA)
   223  
   224  	eltsB := set.bits.AppendTo(nil)
   225  
   226  	if a, b := fmt.Sprint(eltsA), fmt.Sprint(eltsB); a != b {
   227  		t.Errorf("check(%s): hash=%s bits=%s (%s)", msg, a, b, &set.bits)
   228  	}
   229  
   230  	if err := set.bits.Check(); err != nil {
   231  		t.Fatalf("Check(%s): %s: %#v", msg, err, &set.bits)
   232  	}
   233  }
   234  
   235  // randomPset returns a parallel set of random size and elements.
   236  func randomPset(prng *rand.Rand, maxSize int) *pset {
   237  	set := makePset()
   238  	size := int(prng.Int()) % maxSize
   239  	for i := 0; i < size; i++ {
   240  		// TODO(adonovan): benchmark how performance varies
   241  		// with this sparsity parameter.
   242  		n := int(prng.Int()) % 10000
   243  		set.add(n)
   244  	}
   245  	return set
   246  }
   247  
   248  // TestRandomMutations performs the same random adds/removes on two
   249  // set implementations and ensures that they compute the same result.
   250  func TestRandomMutations(t *testing.T) {
   251  	const debug = false
   252  
   253  	set := makePset()
   254  	prng := rand.New(rand.NewSource(0))
   255  	for i := 0; i < 10000; i++ {
   256  		n := int(prng.Int())%2000 - 1000
   257  		if i%2 == 0 {
   258  			if debug {
   259  				log.Printf("add %d", n)
   260  			}
   261  			set.add(n)
   262  		} else {
   263  			if debug {
   264  				log.Printf("remove %d", n)
   265  			}
   266  			set.remove(n)
   267  		}
   268  		if debug {
   269  			set.check(t, "post mutation")
   270  		}
   271  	}
   272  	set.check(t, "final")
   273  	if debug {
   274  		log.Print(&set.bits)
   275  	}
   276  }
   277  
   278  func TestLowerBound(t *testing.T) {
   279  	// Use random sets of sizes from 0 to about 4000.
   280  	prng := rand.New(rand.NewSource(0))
   281  	for i := uint(0); i < 12; i++ {
   282  		x := randomPset(prng, 1<<i)
   283  		for j := 0; j < 10000; j++ {
   284  			found := intsets.MaxInt
   285  			for e := range x.hash {
   286  				if e >= j && e < found {
   287  					found = e
   288  				}
   289  			}
   290  			if res := x.bits.LowerBound(j); res != found {
   291  				t.Errorf("%s: LowerBound(%d)=%d, expected %d", &x.bits, j, res, found)
   292  			}
   293  		}
   294  	}
   295  }
   296  
   297  // TestSetOperations exercises classic set operations: ∩ , ∪, \.
   298  func TestSetOperations(t *testing.T) {
   299  	prng := rand.New(rand.NewSource(0))
   300  
   301  	// Use random sets of sizes from 0 to about 4000.
   302  	// For each operator, we test variations such as
   303  	// Z.op(X, Y), Z.op(X, Z) and Z.op(Z, Y) to exercise
   304  	// the degenerate cases of each method implementation.
   305  	for i := uint(0); i < 12; i++ {
   306  		X := randomPset(prng, 1<<i)
   307  		Y := randomPset(prng, 1<<i)
   308  
   309  		// TODO(adonovan): minimise dependencies between stanzas below.
   310  
   311  		// Copy(X)
   312  		C := makePset()
   313  		C.bits.Copy(&Y.bits) // no effect on result
   314  		C.bits.Copy(&X.bits)
   315  		C.hash = X.hash
   316  		C.check(t, "C.Copy(X)")
   317  		C.bits.Copy(&C.bits)
   318  		C.check(t, "C.Copy(C)")
   319  
   320  		// U.Union(X, Y)
   321  		U := makePset()
   322  		U.bits.Union(&X.bits, &Y.bits)
   323  		for n := range X.hash {
   324  			U.hash[n] = true
   325  		}
   326  		for n := range Y.hash {
   327  			U.hash[n] = true
   328  		}
   329  		U.check(t, "U.Union(X, Y)")
   330  
   331  		// U.Union(X, X)
   332  		U.bits.Union(&X.bits, &X.bits)
   333  		U.hash = X.hash
   334  		U.check(t, "U.Union(X, X)")
   335  
   336  		// U.Union(U, Y)
   337  		U = makePset()
   338  		U.bits.Copy(&X.bits)
   339  		U.bits.Union(&U.bits, &Y.bits)
   340  		for n := range X.hash {
   341  			U.hash[n] = true
   342  		}
   343  		for n := range Y.hash {
   344  			U.hash[n] = true
   345  		}
   346  		U.check(t, "U.Union(U, Y)")
   347  
   348  		// U.Union(X, U)
   349  		U.bits.Copy(&Y.bits)
   350  		U.bits.Union(&X.bits, &U.bits)
   351  		U.check(t, "U.Union(X, U)")
   352  
   353  		// U.UnionWith(U)
   354  		U.bits.UnionWith(&U.bits)
   355  		U.check(t, "U.UnionWith(U)")
   356  
   357  		// I.Intersection(X, Y)
   358  		I := makePset()
   359  		I.bits.Intersection(&X.bits, &Y.bits)
   360  		for n := range X.hash {
   361  			if Y.hash[n] {
   362  				I.hash[n] = true
   363  			}
   364  		}
   365  		I.check(t, "I.Intersection(X, Y)")
   366  
   367  		// I.Intersection(X, X)
   368  		I.bits.Intersection(&X.bits, &X.bits)
   369  		I.hash = X.hash
   370  		I.check(t, "I.Intersection(X, X)")
   371  
   372  		// I.Intersection(I, X)
   373  		I.bits.Intersection(&I.bits, &X.bits)
   374  		I.check(t, "I.Intersection(I, X)")
   375  
   376  		// I.Intersection(X, I)
   377  		I.bits.Intersection(&X.bits, &I.bits)
   378  		I.check(t, "I.Intersection(X, I)")
   379  
   380  		// I.Intersection(I, I)
   381  		I.bits.Intersection(&I.bits, &I.bits)
   382  		I.check(t, "I.Intersection(I, I)")
   383  
   384  		// D.Difference(X, Y)
   385  		D := makePset()
   386  		D.bits.Difference(&X.bits, &Y.bits)
   387  		for n := range X.hash {
   388  			if !Y.hash[n] {
   389  				D.hash[n] = true
   390  			}
   391  		}
   392  		D.check(t, "D.Difference(X, Y)")
   393  
   394  		// D.Difference(D, Y)
   395  		D.bits.Copy(&X.bits)
   396  		D.bits.Difference(&D.bits, &Y.bits)
   397  		D.check(t, "D.Difference(D, Y)")
   398  
   399  		// D.Difference(Y, D)
   400  		D.bits.Copy(&X.bits)
   401  		D.bits.Difference(&Y.bits, &D.bits)
   402  		D.hash = make(map[int]bool)
   403  		for n := range Y.hash {
   404  			if !X.hash[n] {
   405  				D.hash[n] = true
   406  			}
   407  		}
   408  		D.check(t, "D.Difference(Y, D)")
   409  
   410  		// D.Difference(X, X)
   411  		D.bits.Difference(&X.bits, &X.bits)
   412  		D.hash = nil
   413  		D.check(t, "D.Difference(X, X)")
   414  
   415  		// D.DifferenceWith(D)
   416  		D.bits.Copy(&X.bits)
   417  		D.bits.DifferenceWith(&D.bits)
   418  		D.check(t, "D.DifferenceWith(D)")
   419  
   420  		// SD.SymmetricDifference(X, Y)
   421  		SD := makePset()
   422  		SD.bits.SymmetricDifference(&X.bits, &Y.bits)
   423  		for n := range X.hash {
   424  			if !Y.hash[n] {
   425  				SD.hash[n] = true
   426  			}
   427  		}
   428  		for n := range Y.hash {
   429  			if !X.hash[n] {
   430  				SD.hash[n] = true
   431  			}
   432  		}
   433  		SD.check(t, "SD.SymmetricDifference(X, Y)")
   434  
   435  		// X.SymmetricDifferenceWith(Y)
   436  		SD.bits.Copy(&X.bits)
   437  		SD.bits.SymmetricDifferenceWith(&Y.bits)
   438  		SD.check(t, "X.SymmetricDifference(Y)")
   439  
   440  		// Y.SymmetricDifferenceWith(X)
   441  		SD.bits.Copy(&Y.bits)
   442  		SD.bits.SymmetricDifferenceWith(&X.bits)
   443  		SD.check(t, "Y.SymmetricDifference(X)")
   444  
   445  		// SD.SymmetricDifference(X, X)
   446  		SD.bits.SymmetricDifference(&X.bits, &X.bits)
   447  		SD.hash = nil
   448  		SD.check(t, "SD.SymmetricDifference(X, X)")
   449  
   450  		// SD.SymmetricDifference(X, Copy(X))
   451  		X2 := makePset()
   452  		X2.bits.Copy(&X.bits)
   453  		SD.bits.SymmetricDifference(&X.bits, &X2.bits)
   454  		SD.check(t, "SD.SymmetricDifference(X, Copy(X))")
   455  
   456  		// Copy(X).SymmetricDifferenceWith(X)
   457  		SD.bits.Copy(&X.bits)
   458  		SD.bits.SymmetricDifferenceWith(&X.bits)
   459  		SD.check(t, "Copy(X).SymmetricDifferenceWith(X)")
   460  	}
   461  }
   462  
   463  // TestUnionWithChanged checks the 'changed' result of UnionWith.
   464  func TestUnionWithChanged(t *testing.T) {
   465  	setOf := func(elems ...int) *intsets.Sparse {
   466  		s := new(intsets.Sparse)
   467  		for _, elem := range elems {
   468  			s.Insert(elem)
   469  		}
   470  		return s
   471  	}
   472  
   473  	checkUnionWith := func(x, y *intsets.Sparse) {
   474  		xstr := x.String()
   475  		prelen := x.Len()
   476  		changed := x.UnionWith(y)
   477  		if (x.Len() > prelen) != changed {
   478  			t.Errorf("%s.UnionWith(%s) => %s, changed=%t", xstr, y, x, changed)
   479  		}
   480  	}
   481  
   482  	// The case marked "!" is a regression test for Issue 50352,
   483  	// which spuriously returned true when y ⊂ x.
   484  
   485  	// same block
   486  	checkUnionWith(setOf(1, 2), setOf(1, 2))
   487  	checkUnionWith(setOf(1, 2, 3), setOf(1, 2)) // !
   488  	checkUnionWith(setOf(1, 2), setOf(1, 2, 3))
   489  	checkUnionWith(setOf(1, 2), setOf())
   490  
   491  	// different blocks
   492  	checkUnionWith(setOf(1, 1000000), setOf(1, 1000000))
   493  	checkUnionWith(setOf(1, 2, 1000000), setOf(1, 2))
   494  	checkUnionWith(setOf(1, 2), setOf(1, 2, 1000000))
   495  	checkUnionWith(setOf(1, 1000000), setOf())
   496  }
   497  
   498  func TestIntersectionWith(t *testing.T) {
   499  	// Edge cases: the pairs (1,1), (1000,2000), (8000,4000)
   500  	// exercise the <, >, == cases in IntersectionWith that the
   501  	// TestSetOperations data is too dense to cover.
   502  	var X, Y intsets.Sparse
   503  	X.Insert(1)
   504  	X.Insert(1000)
   505  	X.Insert(8000)
   506  	Y.Insert(1)
   507  	Y.Insert(2000)
   508  	Y.Insert(4000)
   509  	X.IntersectionWith(&Y)
   510  	if got, want := X.String(), "{1}"; got != want {
   511  		t.Errorf("IntersectionWith: got %s, want %s", got, want)
   512  	}
   513  }
   514  
   515  func TestIntersects(t *testing.T) {
   516  	prng := rand.New(rand.NewSource(0))
   517  
   518  	for i := uint(0); i < 12; i++ {
   519  		X, Y := randomPset(prng, 1<<i), randomPset(prng, 1<<i)
   520  		x, y := &X.bits, &Y.bits
   521  
   522  		// test the slow way
   523  		var z intsets.Sparse
   524  		z.Copy(x)
   525  		z.IntersectionWith(y)
   526  
   527  		if got, want := x.Intersects(y), !z.IsEmpty(); got != want {
   528  			t.Errorf("Intersects(%s, %s): got %v, want %v (%s)", x, y, got, want, &z)
   529  		}
   530  
   531  		// make it false
   532  		a := x.AppendTo(nil)
   533  		for _, v := range a {
   534  			y.Remove(v)
   535  		}
   536  
   537  		if got, want := x.Intersects(y), false; got != want {
   538  			t.Errorf("Intersects: got %v, want %v", got, want)
   539  		}
   540  
   541  		// make it true
   542  		if x.IsEmpty() {
   543  			continue
   544  		}
   545  		i := prng.Intn(len(a))
   546  		y.Insert(a[i])
   547  
   548  		if got, want := x.Intersects(y), true; got != want {
   549  			t.Errorf("Intersects: got %v, want %v", got, want)
   550  		}
   551  	}
   552  }
   553  
   554  func TestSubsetOf(t *testing.T) {
   555  	prng := rand.New(rand.NewSource(0))
   556  
   557  	for i := uint(0); i < 12; i++ {
   558  		X, Y := randomPset(prng, 1<<i), randomPset(prng, 1<<i)
   559  		x, y := &X.bits, &Y.bits
   560  
   561  		// test the slow way
   562  		var z intsets.Sparse
   563  		z.Copy(x)
   564  		z.DifferenceWith(y)
   565  
   566  		if got, want := x.SubsetOf(y), z.IsEmpty(); got != want {
   567  			t.Errorf("SubsetOf: got %v, want %v", got, want)
   568  		}
   569  
   570  		// make it true
   571  		y.UnionWith(x)
   572  
   573  		if got, want := x.SubsetOf(y), true; got != want {
   574  			t.Errorf("SubsetOf: got %v, want %v", got, want)
   575  		}
   576  
   577  		// make it false
   578  		if x.IsEmpty() {
   579  			continue
   580  		}
   581  		a := x.AppendTo(nil)
   582  		i := prng.Intn(len(a))
   583  		y.Remove(a[i])
   584  
   585  		if got, want := x.SubsetOf(y), false; got != want {
   586  			t.Errorf("SubsetOf: got %v, want %v", got, want)
   587  		}
   588  	}
   589  }
   590  
   591  func TestBitString(t *testing.T) {
   592  	for _, test := range []struct {
   593  		input []int
   594  		want  string
   595  	}{
   596  		{nil, "0"},
   597  		{[]int{0}, "1"},
   598  		{[]int{0, 4, 5}, "110001"},
   599  		{[]int{0, 7, 177}, "1" + strings.Repeat("0", 169) + "10000001"},
   600  		{[]int{-3, 0, 4, 5}, "110001.001"},
   601  		{[]int{-3}, "0.001"},
   602  	} {
   603  		var set intsets.Sparse
   604  		for _, x := range test.input {
   605  			set.Insert(x)
   606  		}
   607  		if got := set.BitString(); got != test.want {
   608  			t.Errorf("BitString(%s) = %s, want %s", set.String(), got, test.want)
   609  		}
   610  	}
   611  }
   612  
   613  func TestFailFastOnShallowCopy(t *testing.T) {
   614  	var x intsets.Sparse
   615  	x.Insert(1)
   616  
   617  	y := x // shallow copy (breaks representation invariants)
   618  	defer func() {
   619  		got := fmt.Sprint(recover())
   620  		want := "interface conversion: interface {} is nil, not intsets.to_copy_a_sparse_you_must_call_its_Copy_method"
   621  		if got != want {
   622  			t.Errorf("shallow copy: recover() = %q, want %q", got, want)
   623  		}
   624  	}()
   625  	_ = y.String() // panics
   626  	t.Error("didn't panic as expected")
   627  }
   628  
   629  // -- Benchmarks -------------------------------------------------------
   630  
   631  // TODO(adonovan):
   632  // - Add benchmarks of each method.
   633  // - Gather set distributions from pointer analysis.
   634  // - Measure memory usage.
   635  
   636  func benchmarkInsertProbeSparse(b *testing.B, size, spread int) {
   637  	prng := rand.New(rand.NewSource(0))
   638  	// Generate our insertions and probes beforehand (we don't want to benchmark
   639  	// the prng).
   640  	insert := make([]int, size)
   641  	probe := make([]int, size*2)
   642  	for i := range insert {
   643  		insert[i] = prng.Int() % spread
   644  	}
   645  	for i := range probe {
   646  		probe[i] = prng.Int() % spread
   647  	}
   648  
   649  	b.ResetTimer()
   650  	var x intsets.Sparse
   651  	for tries := 0; tries < b.N; tries++ {
   652  		x.Clear()
   653  		for _, n := range insert {
   654  			x.Insert(n)
   655  		}
   656  		hits := 0
   657  		for _, n := range probe {
   658  			if x.Has(n) {
   659  				hits++
   660  			}
   661  		}
   662  		// Use the variable so it doesn't get optimized away.
   663  		if hits > len(probe) {
   664  			b.Fatalf("%d hits, only %d probes", hits, len(probe))
   665  		}
   666  	}
   667  }
   668  
   669  func BenchmarkInsertProbeSparse_2_10(b *testing.B) {
   670  	benchmarkInsertProbeSparse(b, 2, 10)
   671  }
   672  
   673  func BenchmarkInsertProbeSparse_10_10(b *testing.B) {
   674  	benchmarkInsertProbeSparse(b, 10, 10)
   675  }
   676  
   677  func BenchmarkInsertProbeSparse_10_1000(b *testing.B) {
   678  	benchmarkInsertProbeSparse(b, 10, 1000)
   679  }
   680  
   681  func BenchmarkInsertProbeSparse_100_100(b *testing.B) {
   682  	benchmarkInsertProbeSparse(b, 100, 100)
   683  }
   684  
   685  func BenchmarkInsertProbeSparse_100_10000(b *testing.B) {
   686  	benchmarkInsertProbeSparse(b, 100, 1000)
   687  }
   688  
   689  func BenchmarkUnionDifferenceSparse(b *testing.B) {
   690  	prng := rand.New(rand.NewSource(0))
   691  	for tries := 0; tries < b.N; tries++ {
   692  		var x, y, z intsets.Sparse
   693  		for i := 0; i < 1000; i++ {
   694  			n := int(prng.Int()) % 100000
   695  			if i%2 == 0 {
   696  				x.Insert(n)
   697  			} else {
   698  				y.Insert(n)
   699  			}
   700  		}
   701  		z.Union(&x, &y)
   702  		z.Difference(&x, &y)
   703  	}
   704  }
   705  
   706  func BenchmarkUnionDifferenceHashTable(b *testing.B) {
   707  	prng := rand.New(rand.NewSource(0))
   708  	for tries := 0; tries < b.N; tries++ {
   709  		x, y, z := make(map[int]bool), make(map[int]bool), make(map[int]bool)
   710  		for i := 0; i < 1000; i++ {
   711  			n := int(prng.Int()) % 100000
   712  			if i%2 == 0 {
   713  				x[n] = true
   714  			} else {
   715  				y[n] = true
   716  			}
   717  		}
   718  		// union
   719  		for n := range x {
   720  			z[n] = true
   721  		}
   722  		for n := range y {
   723  			z[n] = true
   724  		}
   725  		// difference
   726  		z = make(map[int]bool)
   727  		for n := range y {
   728  			if !x[n] {
   729  				z[n] = true
   730  			}
   731  		}
   732  	}
   733  }
   734  
   735  func BenchmarkAppendTo(b *testing.B) {
   736  	prng := rand.New(rand.NewSource(0))
   737  	var x intsets.Sparse
   738  	for i := 0; i < 1000; i++ {
   739  		x.Insert(int(prng.Int()) % 10000)
   740  	}
   741  	var space [1000]int
   742  	for tries := 0; tries < b.N; tries++ {
   743  		x.AppendTo(space[:0])
   744  	}
   745  }
   746
View as plain text