package main
import (
"flag"
"fmt"
"sort"
"time"
"algo/metrics"
)
func cmdIndex(args []string) error {
fs := flag.NewFlagSet("index", flag.ContinueOnError)
in := fs.String("in", "library.jsonl", "library file")
nogrow := fs.Bool("nogrow", false, "never resize: keep the starting bucket count")
buckets := fs.Int("buckets", 16, "starting bucket count")
if err := fs.Parse(args); err != nil {
return err
}
items, err := load(*in)
if err != nil {
return err
}
idx := NewHashIndex(*buckets)
idx.NoGrow = *nogrow
var build metrics.Counter
start := time.Now()
for _, it := range items {
idx.Put(it, &build)
}
buildTime := time.Since(start)
longest, empty, mean := idx.ChainStats()
fmt.Printf("n = %d, resize = %v\n\n", len(items), !*nogrow)
fmt.Printf(" buckets %d\n", idx.Buckets())
fmt.Printf(" stored %d\n", idx.Len())
fmt.Printf(" resizes %d\n", idx.Resizes)
fmt.Printf(" load factor %.3f\n", idx.LoadFactor())
fmt.Printf(" empty buckets %d\n", empty)
fmt.Printf(" mean chain %.3f\n", mean)
fmt.Printf(" LONGEST chain %d\n", longest)
fmt.Printf(" build time %s\n\n", buildTime.Round(time.Microsecond))
// Look up every title and count the comparisons: that is the chain walked.
var lookup metrics.Counter
t0 := time.Now()
for _, it := range items {
idx.Get(it.Title, &lookup)
}
el := time.Since(t0)
fmt.Printf(" %d lookups: %d comparisons (%.3f per lookup), %s\n",
len(items), lookup.N(), float64(lookup.N())/float64(len(items)), el.Round(time.Microsecond))
// The same lookups by linear scan, for scale (lesson 1's baseline).
var lin metrics.Counter
t1 := time.Now()
for _, it := range items {
LinearFind(items, it.Title, &lin)
}
el2 := time.Since(t1)
fmt.Printf(" same by linear scan: %d comparisons (%.1f per lookup), %s\n",
lin.N(), float64(lin.N())/float64(len(items)), el2.Round(time.Millisecond))
return nil
}
// cmdOrdered is the closing question: ask the hash index for the library in
// alphabetical order.
func cmdOrdered(args []string) error {
fs := flag.NewFlagSet("ordered", flag.ContinueOnError)
in := fs.String("in", "library.jsonl", "library file")
n := fs.Int("n", 6, "how many titles to show")
if err := fs.Parse(args); err != nil {
return err
}
items, err := load(*in)
if err != nil {
return err
}
idx := NewHashIndex(16)
var c metrics.Counter
for _, it := range items {
idx.Put(it, &c)
}
keys := idx.Keys()
fmt.Printf("the first %d titles, as the index stores them:\n", *n)
for i := 0; i < *n && i < len(keys); i++ {
fmt.Printf(" %s\n", keys[i])
}
sorted := append([]string(nil), keys...)
sort.Strings(sorted)
fmt.Printf("\nthe first %d in alphabetical order:\n", *n)
for i := 0; i < *n && i < len(sorted); i++ {
fmt.Printf(" %s\n", sorted[i])
}
fmt.Printf("\ngetting the second list from the index cost a full sort of all %d keys.\n", len(keys))
fmt.Println("the index itself could not answer the question at all.")
return nil
}
