Kodas

Kraštiniai atvejai — čia ji ir lūžta

Sukurk search_test.go (žr. dešinėje). Šitą testą rašom mes; tavo darbas — kad LowerBound jį praeitų.

Laimingas atvejis — „įrašas kažkur viduryje" — yra lengvas. Visos toliau išvardytos vietos yra ten, kur ranka rašyta dvejetainė paieška iš tikrųjų lūžta.

Dešimt kraštinių atvejų

$ go test -run TestLowerBoundBoundaries -v .
=== RUN   TestLowerBoundBoundaries/exact_match,_first
=== RUN   TestLowerBoundBoundaries/exact_match,_middle
=== RUN   TestLowerBoundBoundaries/exact_match,_last
=== RUN   TestLowerBoundBoundaries/between_two_items
=== RUN   TestLowerBoundBoundaries/before_everything
=== RUN   TestLowerBoundBoundaries/AFTER_everything
=== RUN   TestLowerBoundBoundaries/empty_slice
=== RUN   TestLowerBoundBoundaries/single_item,_before
=== RUN   TestLowerBoundBoundaries/single_item,_exact
=== RUN   TestLowerBoundBoundaries/single_item,_after
--- PASS: TestLowerBoundBoundaries (0.00s)

Trys iš jų verti atskiro žodžio.

„AFTER everything" grąžina 4, kai bibliotekoje 4 įrašai. Indeksas, kurio nėra. Būtent todėl hi pradedamas nuo len(items), o ne nuo len(items)-1: atsakymas „už galo" turi turėti kur tilpti. Pradėk nuo len-1 ir šis atvejis tyliai grąžins paskutinį įrašą.

Tuščias slice grąžina 0 ir neišvis nepatenka į ciklą, nes lo < hi iškart neteisinga. Nulinis atvejis pasitvarko pats — jei invariantas teisingas.

Vieno įrašo biblioteka tikrinama tris kartus, nes joje mid visada 0 ir klaida su mid + 1 čia virsta amžinuoju ciklu.

Dublikatai: kurį iš trijų?

lib := sorted("a", "b", "b", "b", "c")
LowerBound(lib, "b")  // → 1

Trys „b". Teisingas atsakymas — pirmasis, indeksas 1. Tai ir reiškia lower bound.

Jei tavo paieška grąžina 2 arba 3, ji atrodo teisinga ir praeis paviršutinišką patikrinimą. Bet kodas, kuris nuo rezultato eina pirmyn rinkdamas visus sutampančius įrašus, praleis dalį jų — ir klaida išlįs kur nors kitur, visiškai kitoje vietoje.

transit savo paieškos semantiką irgi testuoja, o ne prielaidauja.

Ir svarbiausias testas

$ go test -run TestUnsortedInputSilentlyLies -v .
    search_test.go:93: unsorted input: linear says 0, binary says 2 —
                       binary is wrong, and silent

Nesurikiuotas įvedimas dvejetainei paieškai nėra klaida. Ji nepraneša nieko. Ji tiesiog grąžina neteisingą skaičių.

Spąstai

Surikiuota tvarka yra prielaida, o ne rekomendacija. Tiesinė paieška veikia visada; dvejetainė veikia tik tada, kai jos sąlyga išpildyta, ir pati to netikrina — patikrinimas kainuotų O(n) ir sunaikintų visą prasmę. Prielaidas saugo tavo programa, ne paieška.

search_test.go SUKURTI

Sukurk šį failą kataloge ./

package main

import (
	"fmt"
	"testing"

	"algo/metrics"
)

// sorted builds a sorted library from the titles given, in order.
func sorted(titles ...string) []Item {
	items := make([]Item, len(titles))
	for i, t := range titles {
		items[i] = Item{ID: i + 1, Title: t}
	}
	return items
}

// THE BOUNDARIES ARE THE LESSON. A binary search that works on "the item is
// somewhere in the middle" is easy. Every one of these cases is where a
// hand-rolled one actually breaks.
func TestLowerBoundBoundaries(t *testing.T) {
	lib := sorted("b", "d", "f", "h")
	cases := []struct {
		name   string
		items  []Item
		target string
		want   int
	}{
		{"exact match, first", lib, "b", 0},
		{"exact match, middle", lib, "f", 2},
		{"exact match, last", lib, "h", 3},
		{"between two items", lib, "e", 2},
		{"before everything", lib, "a", 0},
		{"AFTER everything", lib, "z", 4}, // len(items) — one past the end
		{"empty slice", nil, "a", 0},
		{"single item, before", sorted("m"), "a", 0},
		{"single item, exact", sorted("m"), "m", 0},
		{"single item, after", sorted("m"), "z", 1},
	}
	for _, tc := range cases {
		t.Run(tc.name, func(t *testing.T) {
			var c metrics.Counter
			if got := LowerBound(tc.items, tc.target, &c); got != tc.want {
				t.Errorf("LowerBound(%q) = %d, want %d", tc.target, got, tc.want)
			}
		})
	}
}

// With duplicates there is more than one correct-looking answer. LOWER BOUND
// is defined to land on the FIRST. If yours lands on any of them, it is not a
// lower bound — and code that scans forward from the result will miss rows.
func TestLowerBoundLandsOnTheFirstDuplicate(t *testing.T) {
	lib := sorted("a", "b", "b", "b", "c")
	var c metrics.Counter
	got := LowerBound(lib, "b", &c)
	if got != 1 {
		t.Fatalf("LowerBound(\"b\") = %d, want 1 (the FIRST of three)", got)
	}
}

// The three searches must agree everywhere, or comparing their speed is
// meaningless. This is the same discipline transit uses before benchmarking:
// prove they are the same function first.
func TestAllThreeAgree(t *testing.T) {
	lib := make([]Item, 0, 200)
	for i := 0; i < 200; i++ {
		lib = append(lib, Item{ID: i, Title: fmt.Sprintf("%04d", i*3)})
	}
	for probe := 0; probe < 620; probe++ {
		target := fmt.Sprintf("%04d", probe)
		var c1, c2, c3 metrics.Counter
		a := LinearAtOrAfter(lib, target, &c1)
		b := LowerBound(lib, target, &c2)
		d := LowerBoundStd(lib, target, &c3)
		if a != b || b != d {
			t.Fatalf("target %q: linear=%d hand=%d std=%d", target, a, b, d)
		}
	}
}

// A sorted input is a PRECONDITION, not a suggestion. On unsorted data binary
// search does not error — it silently returns a wrong answer.
func TestUnsortedInputSilentlyLies(t *testing.T) {
	lib := sorted("f", "b", "h", "d") // NOT sorted
	var c1, c2 metrics.Counter
	linear := LinearAtOrAfter(lib, "d", &c1)
	binary := LowerBound(lib, "d", &c2)
	if linear == binary {
		t.Skip("this input happened not to expose the difference")
	}
	t.Logf("unsorted input: linear says %d, binary says %d — binary is wrong, and silent", linear, binary)
}