Kodas

Prijungiam history ir queue

Prijunk history ir queue prie main.go.

$ algo history -n 4
viewing:
  → Gubątėva
  → Pūlolė
  → Pugopa
  → Šąguke Gako

history holds 4

undo:
  ← Šąguke Gako
  ← Pugopa
  ← Pūlolė
  ← Gubątėva

history holds 0

Atgal ta pačia tvarka, tik atvirkščiai. Tai visas stekas.

Tikroje sistemoje: eilė, kuri ieško kelio

transit maršrutų programa turi grafą iš 1 531 stotelės ir 2 190 jungčių — tai Vilniaus tinklas. Klausimui „per kiek mažiausiai stotelių nuvažiuosiu iš A į B" ji naudoja paiešką platyn (BFS), o BFS varo eilė: paimk stotelę, apžiūrėk kaimynus, sudėk juos į eilės galą, kartok.

Mūsų matavimu tai trunka 5,8–8,3 µs vienai užklausai.

Skaičius mažas, ir tai svarbu suprasti teisingai: eilė čia nėra siaurasis kaklelis, ir niekas jos neoptimizuoja. Bet struktūra dirba tikrą darbą tikroje sistemoje — būtent ji nustato, kuria tvarka aplankomos stotelės, ir būtent todėl BFS randa trumpiausią kelią, o ne bet kokį.

Pakeisk eilę steku ir gausi paiešką gilyn — teisingą programą, atsakančią į kitą klausimą. 14 pamokoje pastatysi abi.

Spąstai

BFS transite parašytas cikliškai, su aiškia eile, o ne rekursija. Kodėl būtent taip — penktoji pamoka, kuri prasideda nuo šito steko.

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]
`)
}

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:])
	default:
		usage()
		os.Exit(2)
	}
	if err != nil {
		fmt.Fprintln(os.Stderr, "algo:", err)
		os.Exit(1)
	}
}