mud_test.go

     1  // Copyright 2017 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 trace
     6  
     7  import (
     8  	"math/rand"
     9  	"testing"
    10  )
    11  
    12  func TestMUD(t *testing.T) {
    13  	// Insert random uniforms and check histogram mass and
    14  	// cumulative sum approximations.
    15  	rnd := rand.New(rand.NewSource(42))
    16  	mass := 0.0
    17  	var mud mud
    18  	for i := 0; i < 100; i++ {
    19  		area, l, r := rnd.Float64(), rnd.Float64(), rnd.Float64()
    20  		if rnd.Intn(10) == 0 {
    21  			r = l
    22  		}
    23  		t.Log(l, r, area)
    24  		mud.add(l, r, area)
    25  		mass += area
    26  
    27  		// Check total histogram weight.
    28  		hmass := 0.0
    29  		for _, val := range mud.hist {
    30  			hmass += val
    31  		}
    32  		if !aeq(mass, hmass) {
    33  			t.Fatalf("want mass %g, got %g", mass, hmass)
    34  		}
    35  
    36  		// Check inverse cumulative sum approximations.
    37  		for j := 0.0; j < mass; j += mass * 0.099 {
    38  			mud.setTrackMass(j)
    39  			l, u, ok := mud.approxInvCumulativeSum()
    40  			inv, ok2 := mud.invCumulativeSum(j)
    41  			if !ok || !ok2 {
    42  				t.Fatalf("inverse cumulative sum failed: approx %v, exact %v", ok, ok2)
    43  			}
    44  			if !(l <= inv && inv < u) {
    45  				t.Fatalf("inverse(%g) = %g, not ∈ [%g, %g)", j, inv, l, u)
    46  			}
    47  		}
    48  	}
    49  }
    50  
    51  func TestMUDTracking(t *testing.T) {
    52  	// Test that the tracked mass is tracked correctly across
    53  	// updates.
    54  	rnd := rand.New(rand.NewSource(42))
    55  	const uniforms = 100
    56  	for trackMass := 0.0; trackMass < uniforms; trackMass += uniforms / 50 {
    57  		var mud mud
    58  		mass := 0.0
    59  		mud.setTrackMass(trackMass)
    60  		for i := 0; i < uniforms; i++ {
    61  			area, l, r := rnd.Float64(), rnd.Float64(), rnd.Float64()
    62  			mud.add(l, r, area)
    63  			mass += area
    64  			l, u, ok := mud.approxInvCumulativeSum()
    65  			inv, ok2 := mud.invCumulativeSum(trackMass)
    66  
    67  			if mass < trackMass {
    68  				if ok {
    69  					t.Errorf("approx(%g) = [%g, %g), but mass = %g", trackMass, l, u, mass)
    70  				}
    71  				if ok2 {
    72  					t.Errorf("exact(%g) = %g, but mass = %g", trackMass, inv, mass)
    73  				}
    74  			} else {
    75  				if !ok {
    76  					t.Errorf("approx(%g) failed, but mass = %g", trackMass, mass)
    77  				}
    78  				if !ok2 {
    79  					t.Errorf("exact(%g) failed, but mass = %g", trackMass, mass)
    80  				}
    81  				if ok && ok2 && !(l <= inv && inv < u) {
    82  					t.Errorf("inverse(%g) = %g, not ∈ [%g, %g)", trackMass, inv, l, u)
    83  				}
    84  			}
    85  		}
    86  	}
    87  }
    88
View as plain text