Kodas

Matavimo aplinka ir vienintelė riba

Trys failai: matavimo aplinka, testai ir dvi naujos komandos.

komanda	ką daro
`algo route`	vienas maršrutas: BFS prieš Dijkstrą, ir dvi eilės
`algo frontier`	tas pats visomis kryptimis — kad santykis būtų teiginys, ne anekdotas

Testai

testas	ką reikalauja
`TestBothFrontiersReturnTheSameCost`	abi eilės grąžina identišką kainą kiekvienai krypčiai; kelias sudedamas ir sutampa
`TestFewestHopsIsNotCheapest`	BFS kelias niekada ne pigesnis ir kartais brangesnis
`TestTheHeapHoldsStaleEntries`	krūvoje daugiau įrašų nei apdorotų mazgų
`TestDijkstraIsWrongOnNegativeWeights`	su neigiama briauna atsakymas neteisingas

Pirmasis yra svarbiausias, ir ne dėl to, ką tikrina, o dėl to, ką jis leidžia tvirtinti. Penktame žingsnyje lyginsi dvi eiles — palyginimas turi prasmę tik tada, jei jos atsako tą patį. Todėl tai tikrinama pirma.

Trečiasis saugo antro žingsnio sprendimą:

629 pushes settled 562 nodes: 67 stale entries skipped (1.12 pushes per node)

1.12 įdėjimo mazgui. Jei kada nors gausi lygiai 1.00, būsi realizavęs raktų mažinimą — kitą struktūrą su kita kaina, ir testas apie tai pasakys.

Ketvirtasis testas — vienintelė riba, kurią Dijkstra turi

Antrame žingsnyje įrodymas rėmėsi prielaida: jokia briauna nėra neigiama. Štai kas būna be jos.

   0 ──1── 2               tiesioginis kelias, kaina 1
   0 ──2── 1 ──(−5)── 2    aplinkkelis, kaina 2 + (−5) = −3

Dijkstra answered 1; the true cheapest route costs -3

Mazgas 2 pasiekiamas už 1 ir apdorojamas anksčiau, nei mazgas 1 apskritai ištraukiamas — tad pigesnis aplinkkelis niekada nesvarstomas.

Nėra nei klaidos pranešimo, nei ciklo, nei lėtumo. Tiesiog neteisingas atsakymas, pateiktas su tokiu pat pasitikėjimu kaip teisingas. Vienuoliktoje pamokoje išsigimęs medis buvo lėtas ir teisingas; čia atvirkščiai.

Testas reikalauja, kad taip ir liktų — kad niekas „nepataisytų" Dijkstros apsimesdamas, jog ji dirba su neigiamomis kainomis. Tam yra kiti algoritmai (Bellman–Ford), ir jie kainuoja daugiau.

wgraphbench.go SUKURTI

Sukurk šį failą kataloge ./

package main

import (
	"flag"
	"fmt"
	"math/rand"
	"time"

	"algo/metrics"
)

// buildWeightedTrails is lesson 14's generator with a cost on every edge: the
// number of DAYS the reader waited before the next book. Same seed, same trails,
// same shape — only the weights are new.
func buildWeightedTrails(n, trails, length int, seed int64) *WGraph {
	rng := rand.New(rand.NewSource(seed))
	g := NewWGraph(n)
	for t := 0; t < trails; t++ {
		v := int32(rng.Intn(n))
		for i := 0; i < length; i++ {
			w := int32(rng.Intn(n))
			g.AddEdge(v, w, int32(1+rng.Intn(60))) // 1..60 days
			v = w
		}
	}
	return g
}

func cmdRoute(args []string) error {
	fs := flag.NewFlagSet("route", flag.ContinueOnError)
	in := fs.String("in", "library.jsonl", "library file")
	trails := fs.Int("trails", 0, "how many borrowing trails (default n/16)")
	length := fs.Int("length", 12, "books per trail")
	seed := fs.Int64("seed", 1, "trail seed")
	from := fs.Int("from", 0, "start node")
	to := fs.Int("to", -1, "end node (default: the pair where hops and cost disagree most)")
	if err := fs.Parse(args); err != nil {
		return err
	}
	items, err := load(*in)
	if err != nil {
		return err
	}
	n := len(items)
	if *trails == 0 {
		*trails = n / 16
	}
	g := buildWeightedTrails(n, *trails, *length, *seed)

	dst := int32(*to)
	if *to < 0 {
		dst = mostDisagreeing(g, int32(*from))
	}

	var bc, hc, sc metrics.Counter
	bfsPath, okB := BFSW(g, int32(*from), dst, &bc)
	t0 := time.Now()
	heapPath, heapCost, heapSettled, okH := DijkstraHeap(g, int32(*from), dst, &hc)
	heapTime := time.Since(t0)
	t0 = time.Now()
	_, scanCost, scanSettled, okS := DijkstraScan(g, int32(*from), dst, &sc)
	scanTime := time.Since(t0)

	if !okB || !okH || !okS {
		fmt.Printf("no route from %d to %d\n", *from, dst)
		return nil
	}

	fmt.Printf("nodes %d, edges %d, weights = days between borrows (1..60)\n", g.Nodes(), g.Edges())
	fmt.Printf("route from %d to %d\n\n", *from, dst)

	fmt.Printf("  %-26s %8s %10s\n", "", "hops", "days")
	fmt.Printf("  %-26s %8d %10d\n", "BFS (fewest hops)", len(bfsPath)-1, g.PathCost(bfsPath))
	fmt.Printf("  %-26s %8d %10d\n", "Dijkstra (fewest days)", len(heapPath)-1, heapCost)
	fmt.Printf("\n  the cheapest route takes %d more hops and saves %d days\n",
		(len(heapPath)-1)-(len(bfsPath)-1), g.PathCost(bfsPath)-heapCost)

	fmt.Printf("\n  %-26s %14s %12s %12s\n", "same answer, two frontiers", "queue work", "settled", "time")
	fmt.Printf("  %-26s %14d %12d %12s\n", "binary heap (lesson 13)", hc.N(), heapSettled, heapTime.Round(time.Microsecond))
	fmt.Printf("  %-26s %14d %12d %12s\n", "linear min-scan", sc.N(), scanSettled, scanTime.Round(time.Microsecond))
	fmt.Printf("\n  identical cost: %v (%d vs %d)\n", heapCost == scanCost, heapCost, scanCost)
	fmt.Printf("  work ratio %.1fx", float64(sc.N())/float64(hc.N()))
	if heapTime > 0 {
		fmt.Printf(", time ratio %.1fx", float64(scanTime)/float64(heapTime))
	}
	fmt.Println()
	return nil
}

// mostDisagreeing finds the destination where the fewest-hops route and the
// cheapest route differ most in days — the clearest illustration that a hop
// count is not a cost.
func mostDisagreeing(g *WGraph, from int32) int32 {
	best, bestGap := from, int32(-1)
	for t := 0; t < g.Nodes(); t++ {
		if int32(t) == from {
			continue
		}
		var a, b metrics.Counter
		bp, ok1 := BFSW(g, from, int32(t), &a)
		_, cost, _, ok2 := DijkstraHeap(g, from, int32(t), &b)
		if !ok1 || !ok2 {
			continue
		}
		if gap := g.PathCost(bp) - cost; gap > bestGap {
			best, bestGap = int32(t), gap
		}
	}
	return best
}

// cmdFrontier is the two-frontier comparison across every reachable
// destination, so the ratio is a claim rather than an anecdote.
func cmdFrontier(args []string) error {
	fs := flag.NewFlagSet("frontier", flag.ContinueOnError)
	in := fs.String("in", "library.jsonl", "library file")
	trails := fs.Int("trails", 0, "how many trails (default n/16)")
	length := fs.Int("length", 12, "books per trail")
	from := fs.Int("from", 0, "start node")
	rounds := fs.Int("rounds", 5, "repeat the whole sweep this many times, for the timings")
	if err := fs.Parse(args); err != nil {
		return err
	}
	items, err := load(*in)
	if err != nil {
		return err
	}
	n := len(items)
	if *trails == 0 {
		*trails = n / 16
	}
	g := buildWeightedTrails(n, *trails, *length, 1)

	var hc, sc metrics.Counter
	var heapTime, scanTime time.Duration
	pairs, agree := 0, 0
	var hopsDiffer int
	for r := 0; r < *rounds; r++ {
		var rhc, rsc metrics.Counter
		pairs, agree, hopsDiffer = 0, 0, 0
		for t := 0; t < n; t++ {
			if int32(t) == int32(*from) {
				continue
			}
			t0 := time.Now()
			hp, hcost, _, ok1 := DijkstraHeap(g, int32(*from), int32(t), &rhc)
			heapTime += time.Since(t0)
			t0 = time.Now()
			_, scost, _, ok2 := DijkstraScan(g, int32(*from), int32(t), &rsc)
			scanTime += time.Since(t0)
			if !ok1 || !ok2 {
				continue
			}
			pairs++
			if hcost == scost {
				agree++
			}
			var bcc metrics.Counter
			if bp, ok := BFSW(g, int32(*from), int32(t), &bcc); ok && len(bp) != len(hp) {
				hopsDiffer++
			}
		}
		hc, sc = rhc, rsc // one round's counts; they are identical every round
	}
	heapTime /= time.Duration(*rounds)
	scanTime /= time.Duration(*rounds)
	fmt.Printf("nodes %d, edges %d, %d reachable destinations from %d\n\n", g.Nodes(), g.Edges(), pairs, *from)
	fmt.Printf("  %-26s %16s %12s\n", "", "queue work", "time")
	fmt.Printf("  %-26s %16d %12s\n", "binary heap (lesson 13)", hc.N(), heapTime.Round(time.Millisecond))
	fmt.Printf("  %-26s %16d %12s\n", "linear min-scan", sc.N(), scanTime.Round(time.Millisecond))
	fmt.Printf("\n  identical cost on %d of %d destinations\n", agree, pairs)
	fmt.Printf("  work ratio  %.1fx\n", float64(sc.N())/float64(hc.N()))
	fmt.Printf("  time ratio  %.1fx\n", float64(scanTime)/float64(heapTime))
	fmt.Printf("\n  BFS's route differed from Dijkstra's on %d of %d (%.1f%%)\n",
		hopsDiffer, pairs, 100*float64(hopsDiffer)/float64(pairs))
	return nil
}

wgraph_test.go SUKURTI

Sukurk šį failą kataloge ./

package main

import (
	"testing"

	"algo/metrics"
)

func testWGraph() *WGraph { return buildWeightedTrails(1000, 62, 12, 1) }

// isWPath checks a path is real and that its edges add up to the reported cost.
func isWPath(g *WGraph, p []int32, from, to, cost int32) bool {
	if len(p) == 0 || p[0] != from || p[len(p)-1] != to {
		return false
	}
	total := int32(0)
	for i := 1; i < len(p); i++ {
		found := false
		for _, e := range g.Neighbors(p[i-1]) {
			if e.To == p[i] {
				total += e.Cost
				found = true
				break
			}
		}
		if !found {
			return false
		}
	}
	return total == cost
}

// THE TWO FRONTIERS MUST AGREE. Swapping the priority queue changes how long the
// search takes and nothing else — which is what makes the comparison in step 5
// meaningful at all.
func TestBothFrontiersReturnTheSameCost(t *testing.T) {
	g := testWGraph()
	var hc, sc metrics.Counter
	checked := 0
	for to := int32(1); int(to) < g.Nodes(); to++ {
		hp, hcost, _, ok1 := DijkstraHeap(g, 0, to, &hc)
		_, scost, _, ok2 := DijkstraScan(g, 0, to, &sc)
		if ok1 != ok2 {
			t.Fatalf("node %d: heap found %v, scan found %v", to, ok1, ok2)
		}
		if !ok1 {
			continue
		}
		checked++
		if hcost != scost {
			t.Fatalf("node %d: heap cost %d, scan cost %d", to, hcost, scost)
		}
		if !isWPath(g, hp, 0, to, hcost) {
			t.Fatalf("node %d: the heap's path does not add up to %d", to, hcost)
		}
	}
	if checked < 100 {
		t.Fatalf("only %d destinations checked", checked)
	}
	t.Logf("%d destinations, identical cost every time; heap queue work %d, scan %d (%.1fx)",
		checked, hc.N(), sc.N(), float64(sc.N())/float64(hc.N()))
}

// FEWEST HOPS IS NOT CHEAPEST. Lesson 14's answer is never better than
// Dijkstra's and is often worse — asserted so the distinction survives.
func TestFewestHopsIsNotCheapest(t *testing.T) {
	g := testWGraph()
	var bc, hc metrics.Counter
	worse, equal := 0, 0
	var worstGap int32
	for to := int32(1); int(to) < g.Nodes(); to++ {
		bp, ok1 := BFSW(g, 0, to, &bc)
		_, cost, _, ok2 := DijkstraHeap(g, 0, to, &hc)
		if !ok1 || !ok2 {
			continue
		}
		bcost := g.PathCost(bp)
		if bcost < cost {
			t.Fatalf("node %d: BFS route costs %d, cheaper than the cheapest (%d)", to, bcost, cost)
		}
		if bcost == cost {
			equal++
		} else {
			worse++
			if gap := bcost - cost; gap > worstGap {
				worstGap = gap
			}
		}
	}
	if worse == 0 {
		t.Fatal("the fewest-hops route was always the cheapest — then the weights are doing nothing")
	}
	t.Logf("BFS route: cheapest %d, more expensive %d, worst excess %d days", equal, worse, worstGap)
}

// LAZY DELETION MEANS THE HEAP HOLDS MORE ENTRIES THAN THERE ARE NODES. If a
// version of this settles exactly one entry per node, it is doing decrease-key,
// which is a different structure with a different cost.
func TestTheHeapHoldsStaleEntries(t *testing.T) {
	g := testWGraph()
	var c metrics.Counter
	pushes, settled := 0, 0
	// Re-run the search counting pushes by hand.
	const inf = int32(1) << 30
	dist := make([]int32, g.Nodes())
	done := make([]bool, g.Nodes())
	for i := range dist {
		dist[i] = inf
	}
	dist[0] = 0
	h := NewNodeHeap(g.Nodes())
	h.Push(0, 0, &c)
	pushes++
	for h.Len() > 0 {
		v, d, _ := h.Pop(&c)
		if done[v] {
			continue
		}
		done[v] = true
		settled++
		for _, e := range g.Neighbors(v) {
			if nd := d + e.Cost; nd < dist[e.To] {
				dist[e.To] = nd
				h.Push(e.To, nd, &c)
				pushes++
			}
		}
	}
	if pushes <= settled {
		t.Fatalf("%d pushes for %d settled nodes — no stale entries, so this is not lazy deletion", pushes, settled)
	}
	t.Logf("%d pushes settled %d nodes: %d stale entries skipped (%.2f pushes per node)",
		pushes, settled, pushes-settled, float64(pushes)/float64(settled))
}

// THE HONEST LIMIT, ASSERTED. Dijkstra requires non-negative weights. Given a
// negative edge it does not slow down or error — it returns a WRONG answer,
// because it settles a node before a cheaper route to it has been found.
//
// The graph, searching from 0 to 2:
//
//	0 --1--- 2          the direct route, cost 1
//	0 --2--- 1 --(-5)--- 2   the detour, cost 2 + (-5) = -3
//
// Node 2 is reached at 1 and SETTLED before node 1 is ever popped, so the
// cheaper detour is never considered. The order in which nodes are settled is
// the whole of Dijkstra's argument, and a negative edge destroys it: settling a
// node no longer means its distance is final.
func TestDijkstraIsWrongOnNegativeWeights(t *testing.T) {
	g := NewWGraph(3)
	g.AddEdge(0, 2, 1)
	g.AddEdge(0, 1, 2)
	g.AddEdge(1, 2, -5)

	var c metrics.Counter
	_, cost, _, ok := DijkstraHeap(g, 0, 2, &c)
	if !ok {
		t.Fatal("no route found at all")
	}
	const truth = int32(-3)
	if cost == truth {
		t.Fatal("Dijkstra returned the true optimum on a negative edge — " +
			"that is luck, not correctness, and the demonstration is gone")
	}
	t.Logf("Dijkstra answered %d; the true cheapest route costs %d", cost, truth)
}

func BenchmarkDijkstraHeap(b *testing.B) {
	g := testWGraph()
	var c metrics.Counter
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		DijkstraHeap(g, 0, 999, &c)
	}
}

func BenchmarkDijkstraScan(b *testing.B) {
	g := testWGraph()
	var c metrics.Counter
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		DijkstraScan(g, 0, 999, &c)
	}
}

func BenchmarkDijkstraHeapAllPairs(b *testing.B) {
	g := testWGraph()
	var c metrics.Counter
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		for to := int32(1); int(to) < g.Nodes(); to += 10 {
			DijkstraHeap(g, 0, to, &c)
		}
	}
}

func BenchmarkDijkstraScanAllPairs(b *testing.B) {
	g := testWGraph()
	var c metrics.Counter
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		for to := int32(1); int(to) < g.Nodes(); to += 10 {
			DijkstraScan(g, 0, to, &c)
		}
	}
}

main.go MODIFIKUOTI 6 eilutės pakeistos

Redaguok šį failą kataloge ./

package main

import (
	"fmt"
	"os"
)

func usage() {
	fmt.Fprint(os.Stderr, `algo — your library workbench

  algo gen  [-n N] [-seed S] [-o FILE] [-sorted|-reverse|-shuffled] [-dup-rate R]
  algo find -title TITLE [-in FILE]
  algo load [-in FILE]
  algo stats -growth [-n N]
  algo playlist -from I -to J [-in FILE]
  algo history [-n N] [-in FILE]
  algo queue [-n N]
  algo walk [-depth D] [-branch B] [-per P]
  algo depth -n N [-iterative]
  algo sweep [-scattered]
  algo std [-n N]
  algo sort [-algo A] [-order O] [-in FILE]
  algo dc [-order O] [-in FILE]
  algo stable [-n N]
  algo count [-in FILE]
  algo radix [-in FILE]
  algo index [-in FILE] [-nogrow] [-buckets N]
  algo ordered [-in FILE] [-n N]
  algo alpha [-in FILE] [-n N] [-from A -to B]
  algo tree [-in FILE]
  algo shape [-shuffled FILE] [-sorted FILE]
  algo balance [-shuffled FILE] [-sorted FILE]
  algo rotate [-in FILE]
  algo reload [-in FILE]
  algo top [-in FILE] [-k N] [-show]
  algo pq [-in FILE] [-rounds N]
  algo net [-in FILE] [-trails N] [-length L] [-from I] [-to J]
  algo dense [-in FILE] [-trails N] [-length L]
  algo route [-in FILE] [-from I] [-to J]
  algo frontier [-in FILE] [-from I]
`)
}

func main() {
	if len(os.Args) < 2 {
		usage()
		os.Exit(2)
	}
	var err error
	switch os.Args[1] {
	case "gen":
		err = cmdGen(os.Args[2:])
	case "find":
		err = cmdFind(os.Args[2:])
	case "load":
		err = cmdLoad(os.Args[2:])
	case "stats":
		err = cmdStats(os.Args[2:])
	case "playlist":
		err = cmdPlaylist(os.Args[2:])
	case "history":
		err = cmdHistory(os.Args[2:])
	case "queue":
		err = cmdQueue(os.Args[2:])
	case "walk":
		err = cmdWalk(os.Args[2:])
	case "depth":
		err = cmdDepth(os.Args[2:])
	case "sweep":
		err = cmdSweep(os.Args[2:])
	case "std":
		err = cmdStd(os.Args[2:])
	case "sort":
		err = cmdSort(os.Args[2:])
	case "dc":
		err = cmdDC(os.Args[2:])
	case "stable":
		err = cmdStable(os.Args[2:])
	case "count":
		err = cmdCount(os.Args[2:])
	case "radix":
		err = cmdRadix(os.Args[2:])
	case "index":
		err = cmdIndex(os.Args[2:])
	case "ordered":
		err = cmdOrdered(os.Args[2:])
	case "alpha":
		err = cmdAlpha(os.Args[2:])
	case "tree":
		err = cmdTree(os.Args[2:])
	case "shape":
		err = cmdShape(os.Args[2:])
	case "balance":
		err = cmdBalance(os.Args[2:])
	case "rotate":
		err = cmdRotate(os.Args[2:])
	case "reload":
		err = cmdReload(os.Args[2:])
	case "top":
		err = cmdTop(os.Args[2:])
	case "pq":
		err = cmdPq(os.Args[2:])
	case "net":
		err = cmdNet(os.Args[2:])
	case "dense":
		err = cmdDense(os.Args[2:])
	case "route":
		err = cmdRoute(os.Args[2:])
	case "frontier":
		err = cmdFrontier(os.Args[2:])
	default:
		usage()
		os.Exit(2)
	}
	if err != nil {
		fmt.Fprintln(os.Stderr, "algo:", err)
		os.Exit(1)
	}
}