blob: 3f6f58ee99d1b261094c3667ce539ab53c28797b [file] [log] [blame]
// Copyright ©2015 The Gonum Authors. All rights reserved.
// Use of this code is governed by a BSD-style
// license that can be found in the LICENSE file
package sampleuv
import (
"flag"
"reflect"
"testing"
"time"
"golang.org/x/exp/rand"
"gonum.org/v1/gonum/floats"
)
var prob = flag.Bool("prob", false, "enables probabilistic testing of the random weighted sampler")
const sigChi2 = 16.92 // p = 0.05 df = 9
var (
newExp = func() []float64 {
return []float64{1 << 0, 1 << 1, 1 << 2, 1 << 3, 1 << 4, 1 << 5, 1 << 6, 1 << 7, 1 << 8, 1 << 9}
}
exp = newExp()
obt = []float64{1020, 1909, 3937, 7881, 15687, 31486, 62310, 124632, 250453, 500685}
)
func newTestWeighted() Weighted {
weights := make([]float64, len(obt))
for i := range weights {
weights[i] = float64(int(1) << uint(i))
}
return NewWeighted(weights, nil)
}
func TestWeightedUnseeded(t *testing.T) {
rand.Seed(0)
want := Weighted{
weights: []float64{1 << 0, 1 << 1, 1 << 2, 1 << 3, 1 << 4, 1 << 5, 1 << 6, 1 << 7, 1 << 8, 1 << 9},
heap: []float64{
exp[0] + exp[1] + exp[3] + exp[4] + exp[7] + exp[8] + exp[9] + exp[2] + exp[5] + exp[6],
exp[1] + exp[3] + exp[4] + exp[7] + exp[8] + exp[9],
exp[2] + exp[5] + exp[6],
exp[3] + exp[7] + exp[8],
exp[4] + exp[9],
exp[5],
exp[6],
exp[7],
exp[8],
exp[9],
},
}
ts := newTestWeighted()
if !reflect.DeepEqual(ts, want) {
t.Fatalf("unexpected new Weighted value:\ngot: %#v\nwant:%#v", ts, want)
}
f := make([]float64, len(obt))
for i := 0; i < 1e6; i++ {
item, ok := newTestWeighted().Take()
if !ok {
t.Fatal("Weighted unexpectedly empty")
}
f[item]++
}
exp := newExp()
fac := floats.Sum(f) / floats.Sum(exp)
for i := range f {
exp[i] *= fac
}
if !reflect.DeepEqual(f, obt) {
t.Fatalf("unexpected selection:\ngot: %#v\nwant:%#v", f, obt)
}
// Check that this is within statistical expectations - we know this is true for this set.
X := chi2(f, exp)
if X >= sigChi2 {
t.Errorf("H₀: d(Sample) = d(Expect), H₁: d(S) ≠ d(Expect). df = %d, p = 0.05, X² threshold = %.2f, X² = %f", len(f)-1, sigChi2, X)
}
}
func TestWeightedTimeSeeded(t *testing.T) {
if !*prob {
t.Skip("probabilistic testing not requested")
}
t.Log("Note: This test is stochastic and is expected to fail with probability ≈ 0.05.")
rand.Seed(uint64(time.Now().Unix()))
f := make([]float64, len(obt))
for i := 0; i < 1e6; i++ {
item, ok := newTestWeighted().Take()
if !ok {
t.Fatal("Weighted unexpectedly empty")
}
f[item]++
}
exp := newExp()
fac := floats.Sum(f) / floats.Sum(exp)
for i := range f {
exp[i] *= fac
}
// Check that our obtained values are within statistical expectations for p = 0.05.
// This will not be true approximately 1 in 20 tests.
X := chi2(f, exp)
if X >= sigChi2 {
t.Errorf("H₀: d(Sample) = d(Expect), H₁: d(S) ≠ d(Expect). df = %d, p = 0.05, X² threshold = %.2f, X² = %f", len(f)-1, sigChi2, X)
}
}
func TestWeightZero(t *testing.T) {
rand.Seed(0)
want := Weighted{
weights: []float64{1 << 0, 1 << 1, 1 << 2, 1 << 3, 1 << 4, 1 << 5, 0, 1 << 7, 1 << 8, 1 << 9},
heap: []float64{
exp[0] + exp[1] + exp[3] + exp[4] + exp[7] + exp[8] + exp[9] + exp[2] + exp[5],
exp[1] + exp[3] + exp[4] + exp[7] + exp[8] + exp[9],
exp[2] + exp[5],
exp[3] + exp[7] + exp[8],
exp[4] + exp[9],
exp[5],
0,
exp[7],
exp[8],
exp[9],
},
}
ts := newTestWeighted()
ts.Reweight(6, 0)
if !reflect.DeepEqual(ts, want) {
t.Fatalf("unexpected new Weighted value:\ngot: %#v\nwant:%#v", ts, want)
}
f := make([]float64, len(obt))
for i := 0; i < 1e6; i++ {
ts := newTestWeighted()
ts.Reweight(6, 0)
item, ok := ts.Take()
if !ok {
t.Fatal("Weighted unexpectedly empty")
}
f[item]++
}
exp := newExp()
fac := floats.Sum(f) / floats.Sum(exp)
for i := range f {
exp[i] *= fac
}
if f[6] != 0 {
t.Errorf("unexpected selection rate for zero-weighted item: got: %v want:%v", f[6], 0)
}
if reflect.DeepEqual(f[:6], obt[:6]) {
t.Fatalf("unexpected selection: too few elements chosen in range:\ngot: %v\nwant:%v",
f[:6], obt[:6])
}
if reflect.DeepEqual(f[7:], obt[7:]) {
t.Fatalf("unexpected selection: too few elements chosen in range:\ngot: %v\nwant:%v",
f[7:], obt[7:])
}
}
func TestWeightIncrease(t *testing.T) {
rand.Seed(0)
want := Weighted{
weights: []float64{1 << 0, 1 << 1, 1 << 2, 1 << 3, 1 << 4, 1 << 5, 1 << 9 * 2, 1 << 7, 1 << 8, 1 << 9},
heap: []float64{
exp[0] + exp[1] + exp[3] + exp[4] + exp[7] + exp[8] + exp[9] + exp[2] + exp[5] + exp[9]*2,
exp[1] + exp[3] + exp[4] + exp[7] + exp[8] + exp[9],
exp[2] + exp[5] + exp[9]*2,
exp[3] + exp[7] + exp[8],
exp[4] + exp[9],
exp[5],
exp[9] * 2,
exp[7],
exp[8],
exp[9],
},
}
ts := newTestWeighted()
ts.Reweight(6, ts.weights[len(ts.weights)-1]*2)
if !reflect.DeepEqual(ts, want) {
t.Fatalf("unexpected new Weighted value:\ngot: %#v\nwant:%#v", ts, want)
}
f := make([]float64, len(obt))
for i := 0; i < 1e6; i++ {
ts := newTestWeighted()
ts.Reweight(6, ts.weights[len(ts.weights)-1]*2)
item, ok := ts.Take()
if !ok {
t.Fatal("Weighted unexpectedly empty")
}
f[item]++
}
exp := newExp()
fac := floats.Sum(f) / floats.Sum(exp)
for i := range f {
exp[i] *= fac
}
if f[6] < f[9] {
t.Errorf("unexpected selection rate for re-weighted item: got: %v want:%v", f[6], f[9])
}
if reflect.DeepEqual(f[:6], obt[:6]) {
t.Fatalf("unexpected selection: too many elements chosen in range:\ngot: %v\nwant:%v",
f[:6], obt[:6])
}
if reflect.DeepEqual(f[7:], obt[7:]) {
t.Fatalf("unexpected selection: too many elements chosen in range:\ngot: %v\nwant:%v",
f[7:], obt[7:])
}
}
func chi2(ob, ex []float64) (sum float64) {
for i := range ob {
x := ob[i] - ex[i]
sum += (x * x) / ex[i]
}
return sum
}
func TestWeightedNoResample(t *testing.T) {
const (
tries = 10
n = 10e4
)
ts := NewWeighted(make([]float64, n), nil)
w := make([]float64, n)
for i := 0; i < tries; i++ {
for j := range w {
w[j] = rand.Float64() * n
}
ts.ReweightAll(w)
taken := make(map[int]struct{})
var c int
for {
item, ok := ts.Take()
if !ok {
if c != n {
t.Errorf("unexpected number of items: got: %d want: %d", c, int(n))
}
break
}
c++
if _, exists := taken[item]; exists {
t.Errorf("unexpected duplicate sample for item: %d", item)
}
taken[item] = struct{}{}
}
}
}