Kodas

algo find — pirmasis matavimas

Paskutinis gabalas — pati paieška. Sukurk find.go ir find_test.go (žr. dešinėje).

LinearFind eina per biblioteką nuo pradžios ir suskaičiuoja kiekvieną pavadinimo palyginimą. Tai visas algoritmas: trys eilutės ir vienas skaitiklis.

Pirmasis matavimas

$ algo gen -n 1000 -seed 42
wrote 1000 items to library.jsonl (seed=42, order=shuffled, dup-rate=0.00)

$ algo find -title "Gubątėva"
found at index 0: Gubątėva — Gąčuku (2020, rating 20)
n = 1000, comparisons = 1

$ algo find -title "Šibąču"
found at index 999: Šibąču — Žąžame (1940, rating 89)
n = 1000, comparisons = 1000

$ algo find -title "Nėra tokio"
not found: "Nėra tokio"
n = 1000, comparisons = 1000

Trys atvejai, apie kuriuos kalbėjom pirmame žingsnyje, išmatuoti: geriausias — 1, blogiausias — 1000, nepataikymas — irgi 1000. Nepataikymas visada yra blogiausias atvejis: negali pasakyti, kad kažko nėra, neapžiūrėjęs visko.

O(n) reiškia būtent tai

Padidink biblioteką dešimt kartų ir pažiūrėk, kas darosi su skaičiumi:

n=1000     n = 1000,   comparisons = 1000
n=10000    n = 10000,  comparisons = 10000
n=100000   n = 100000, comparisons = 100000

Dešimt kartų daugiau duomenų — dešimt kartų daugiau darbo. Tiesė. Būtent tai sako O(n), ir dabar tu tai matai, o ne tiki.

Testas, kurį turi praeiti

find_test.go tikrina ne tik atsakymą, bet ir kainą:

$ go test -run TestLinearFindCountsAreExact -v .
=== RUN   TestLinearFindCountsAreExact
=== RUN   TestLinearFindCountsAreExact/best_case:_first_item
=== RUN   TestLinearFindCountsAreExact/third_item
=== RUN   TestLinearFindCountsAreExact/worst_case:_last_item
=== RUN   TestLinearFindCountsAreExact/miss:_scans_everything
--- PASS: TestLinearFindCountsAreExact (0.00s)
PASS
ok  	algo	0.417s

Įsidėmėk šitą formą — ji kartosis visą kursą. Testas reikalauja tikslaus palyginimų skaičiaus, ne „maždaug tiek". Vėlesnėse pamokose testas reikalaus „ne daugiau kaip n log n" — ir tokio testo neįmanoma apgauti neteisingu algoritmu, kad ir koks teisingas būtų jo atsakymas.

Tikroje sistemoje

Kad matytum, jog tai ne mokyklinis pratimas: transit yra veikianti Vilniaus viešojo transporto maršrutų programa. Ji tą patį maršrutą suskaičiuoja dviem būdais — su primityvia eile ir su krūva — ir praneša ir laiką, ir veiksmų skaičių. Trys skirtingi maršrutai:

Užklausa	Eilės darbas (primityvi ÷ krūva)	Laikas (primityvi ÷ krūva)
per miestą	249×	16,0×
lėtoji	257×	18,9×
blogiausias atvejis	324×	16,4×

Ta pati užklausa, tas pats atsakymas, o darbo santykis 15–20 kartų didesnis už laiko santykį. Laikrodis nemeluoja — jis tiesiog matuoja ne tą, ką galvoji: primityvi eilė peržiūri masyvą iš eilės, o procesorius tokį skaitymą atlieka labai pigiai. Šimtas milijonų pigių veiksmų trunka trumpiau nei milijonas brangių.

Būtent todėl šioje pamokoje skaičiuojam veiksmus. Jei būtum matavęs tik laikrodžiu, būtum radęs 16 kartų skirtumą ten, kur darbo skirtumas yra 249.

Riba nėra prognozė

Ta pati programa turi ir antrą pamoką. Naivi maršruto paieška pilname dienos grafe teoriškai gali atlikti 4,28 × 10¹⁰ veiksmų. Išmatuota — 558 ms, ir tai tik 19,6 karto lėčiau už gerąjį variantą, o ne ~1000 kartų, kaip buvo prognozuota.

Riba nesuveikė ne todėl, kad ji neteisinga, o todėl, kad riba yra lubos, o ne prognozė: algoritmas sustoja radęs atsakymą ir niekada neapžiūri viso grafo.

Šitą skirtumą — tarp „kiek daugiausia gali kainuoti" ir „kiek kainavo" — laikyk galvoje visą kursą. Big-O sako pirmą dalyką. Skaitiklis sako antrą.

find.go SUKURTI

Sukurk šį failą kataloge ./

package main

import (
	"flag"
	"fmt"

	"algo/metrics"
)

// LinearFind scans the library from the front and returns the index of the
// first item whose Title matches, or -1. Every title comparison is counted.
//
// This is the O(n) baseline. Every structure in the rest of the course is
// measured against this number.
func LinearFind(items []Item, title string, c *metrics.Counter) int {
	for i := range items {
		c.Hit()
		if items[i].Title == title {
			return i
		}
	}
	return -1
}

func cmdFind(args []string) error {
	fs := flag.NewFlagSet("find", flag.ContinueOnError)
	in := fs.String("in", "library.jsonl", "library file")
	title := fs.String("title", "", "exact title to find")
	if err := fs.Parse(args); err != nil {
		return err
	}
	if *title == "" {
		return fmt.Errorf("-title is required")
	}
	items, err := load(*in)
	if err != nil {
		return err
	}
	var c metrics.Counter
	i := LinearFind(items, *title, &c)
	if i < 0 {
		fmt.Printf("not found: %q\n", *title)
	} else {
		it := items[i]
		fmt.Printf("found at index %d: %s — %s (%d, rating %d)\n",
			i, it.Title, it.Artist, it.Year, it.Rating)
	}
	fmt.Printf("n = %d, comparisons = %d\n", len(items), c.N())
	return nil
}

find_test.go SUKURTI

Sukurk šį failą kataloge ./

package main

import (
	"testing"

	"algo/metrics"
)

// lib is a tiny fixed library — small enough to reason about by hand, which is
// the point: you should be able to predict every count below before running it.
func lib() []Item {
	return []Item{
		{ID: 1, Title: "Aidas", Artist: "Vega", Year: 1999, Rating: 70},
		{ID: 2, Title: "Bangos", Artist: "Vega", Year: 2004, Rating: 55},
		{ID: 3, Title: "Ciklas", Artist: "Nova", Year: 2011, Rating: 90},
		{ID: 4, Title: "Dūmai", Artist: "Nova", Year: 1987, Rating: 40},
	}
}

func TestLinearFindLocatesItems(t *testing.T) {
	items := lib()
	for want, it := range items {
		var c metrics.Counter
		if got := LinearFind(items, it.Title, &c); got != want {
			t.Errorf("LinearFind(%q) = %d, want %d", it.Title, got, want)
		}
	}
}

func TestLinearFindMissingReturnsMinusOne(t *testing.T) {
	items := lib()
	var c metrics.Counter
	if got := LinearFind(items, "Nėra tokio", &c); got != -1 {
		t.Errorf("missing title: got %d, want -1", got)
	}
}

// The COUNTS are the specification, not an afterthought. Best case is 1
// comparison, worst case and a miss are both n. If your implementation does
// not produce exactly these numbers it is doing extra work somewhere.
func TestLinearFindCountsAreExact(t *testing.T) {
	items := lib()
	cases := []struct {
		name  string
		title string
		want  int64
	}{
		{"best case: first item", "Aidas", 1},
		{"third item", "Ciklas", 3},
		{"worst case: last item", "Dūmai", 4},
		{"miss: scans everything", "Nėra tokio", 4},
	}
	for _, tc := range cases {
		t.Run(tc.name, func(t *testing.T) {
			var c metrics.Counter
			LinearFind(items, tc.title, &c)
			if c.N() != tc.want {
				t.Errorf("comparisons = %d, want %d", c.N(), tc.want)
			}
		})
	}
}

// Determinism: the same search on the same data must cost the same every time.
// A count that wobbles is not a measurement.
func TestCountIsDeterministic(t *testing.T) {
	items := lib()
	var first int64
	for i := 0; i < 100; i++ {
		var c metrics.Counter
		LinearFind(items, "Dūmai", &c)
		if i == 0 {
			first = c.N()
			continue
		}
		if c.N() != first {
			t.Fatalf("run %d counted %d, first run counted %d", i, c.N(), first)
		}
	}
}