package main
import (
"flag"
"fmt"
"sort"
"time"
"algo/metrics"
)
// All three searches answer the SAME question, or the comparison would be
// meaningless: return the index of the FIRST item whose Title is >= target.
// That is "at-or-after" — the same semantics transit uses for "the next
// departure at or after this time", and it is the shape you actually want.
// An exact-match search is this plus one equality check.
// LinearAtOrAfter walks from the front. O(n).
func LinearAtOrAfter(items []Item, target string, c *metrics.Counter) int {
for i := range items {
c.Hit()
if items[i].Title >= target {
return i
}
}
return len(items)
}
// LowerBound is the hand-rolled binary search. O(log n).
//
// The invariant is the whole thing: the answer is always in [lo, hi]. lo starts
// at 0, hi at len(items) — ONE PAST the end, because "not found" is a legal
// answer and it lives there.
func LowerBound(items []Item, target string, c *metrics.Counter) int {
lo, hi := 0, len(items)
for lo < hi {
mid := int(uint(lo+hi) >> 1) // >>1 not /2, and uint to avoid overflow
c.Hit()
if items[mid].Title < target {
lo = mid + 1 // mid is too small, so it cannot be the answer
} else {
hi = mid // mid might BE the answer, so it stays in range
}
}
return lo
}
// LowerBoundStd is the same job through the standard library.
func LowerBoundStd(items []Item, target string, c *metrics.Counter) int {
return sort.Search(len(items), func(i int) bool {
c.Hit()
return items[i].Title >= target
})
}
// timeIt runs f until it has spent at least d, then reports the per-call cost.
// Lesson 1 showed a single run reporting "wall 0s"; this is the fix, and it is
// the same trick transit uses for the same reason.
func timeIt(d time.Duration, f func()) (time.Duration, int) {
runs := 0
start := time.Now()
for time.Since(start) < d {
for i := 0; i < 128; i++ {
f()
}
runs += 128
}
return time.Since(start) / time.Duration(runs), runs
}
func cmdSweep(args []string) error {
fs := flag.NewFlagSet("sweep", flag.ContinueOnError)
scattered := fs.Bool("scattered", false, "reach each slice through a map, as a real index would")
ints := fs.Bool("ints", false, "search int32 keys (transit's shape) instead of Titles")
if err := fs.Parse(args); err != nil {
return err
}
sizes := []int{2, 4, 8, 12, 16, 24, 32, 64, 127, 256, 1024, 2254}
// One sorted collection per size. In -scattered mode each is reached
// through a map, so it is not sitting in cache when the search starts.
byN := make(map[int][]Item, len(sizes))
intsByN := make(map[int][]int32, len(sizes))
for _, n := range sizes {
s := make([]Item, n)
xs := make([]int32, n)
for i := range s {
s[i] = Item{ID: i, Title: fmt.Sprintf("%08d", i*2)}
xs[i] = int32(i * 2)
}
byN[n] = s
intsByN[n] = xs
}
key := "Title (string)"
if *ints {
key = "int32"
}
layout := "contiguous"
if *scattered {
layout = "reached through a map"
}
fmt.Printf("key: %s layout: %s\n\n", key, layout)
fmt.Printf("%6s | %10s %10s | %12s %12s | %s\n",
"n", "lin cmps", "bin cmps", "lin ns/op", "bin ns/op", "winner by CLOCK")
fmt.Println("-------|-----------------------|---------------------------|----------------")
for _, n := range sizes {
var cl, cb metrics.Counter
var lin, bin time.Duration
if *ints {
target := int32(n)
get := func() []int32 { return intsByN[n] }
if !*scattered {
xs := intsByN[n]
get = func() []int32 { return xs }
}
LinearInts(get(), target, &cl)
LowerBoundInts(get(), target, &cb)
lin, _ = timeIt(40*time.Millisecond, func() { linearIntsRaw(get(), target) })
bin, _ = timeIt(40*time.Millisecond, func() { lowerBoundIntsRaw(get(), target) })
} else {
target := fmt.Sprintf("%08d", n)
get := func() []Item { return byN[n] }
if !*scattered {
s := byN[n]
get = func() []Item { return s }
}
LinearAtOrAfter(get(), target, &cl)
LowerBound(get(), target, &cb)
lin, _ = timeIt(40*time.Millisecond, func() { linearRaw(get(), target) })
bin, _ = timeIt(40*time.Millisecond, func() { lowerBoundRaw(get(), target) })
}
win := "binary"
if lin < bin {
win = "LINEAR"
}
fmt.Printf("%6d | %10d %10d | %12d %12d | %s\n",
n, cl.N(), cb.N(), lin.Nanoseconds(), bin.Nanoseconds(), win)
}
return nil
}
func cmdStd(args []string) error {
fs := flag.NewFlagSet("std", flag.ContinueOnError)
n := fs.Int("n", 2254, "slice size")
if err := fs.Parse(args); err != nil {
return err
}
s := make([]Item, *n)
for i := range s {
s[i] = Item{ID: i, Title: fmt.Sprintf("%08d", i*2)}
}
target := fmt.Sprintf("%08d", *n/3*2)
var c1, c2 metrics.Counter
a := LowerBound(s, target, &c1)
b := LowerBoundStd(s, target, &c2)
hand, _ := timeIt(120*time.Millisecond, func() { lowerBoundRaw(s, target) })
std, _ := timeIt(120*time.Millisecond, func() { lowerBoundStdRaw(s, target) })
fmt.Printf("n = %d, same answer: hand=%d std=%d (%v)\n\n", *n, a, b, a == b)
fmt.Printf("%-22s %12s %12s\n", "", "comparisons", "ns/op")
fmt.Printf("%-22s %12d %12d\n", "hand-rolled LowerBound", c1.N(), hand.Nanoseconds())
fmt.Printf("%-22s %12d %12d\n", "sort.Search", c2.N(), std.Nanoseconds())
return nil
}
// ── The same two searches over a cheap key ──────────────────────────────
//
// transit searches []int32 departure times, not strings. One int comparison
// is a single machine instruction; one string comparison is a function call
// that may walk several bytes. That difference moves the crossover, which is
// why the sweep measures both.
func LinearInts(xs []int32, target int32, c *metrics.Counter) int {
for i := range xs {
c.Hit()
if xs[i] >= target {
return i
}
}
return len(xs)
}
func LowerBoundInts(xs []int32, target int32, c *metrics.Counter) int {
lo, hi := 0, len(xs)
for lo < hi {
mid := int(uint(lo+hi) >> 1)
c.Hit()
if xs[mid] < target {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}
// ── Uncounted twins, for TIMING only ────────────────────────────────────
//
// The counted versions above call c.Hit() once per comparison. That call is
// cheap, but the linear scan makes n/2 of them and the binary search makes
// log n — so instrumenting the code penalises the linear scan far more than
// the binary one, and the timing would be measuring the COUNTER.
//
// So: count with one version, time with the other. Same algorithm, no probe.
func linearIntsRaw(xs []int32, target int32) int {
for i := range xs {
if xs[i] >= target {
return i
}
}
return len(xs)
}
func lowerBoundIntsRaw(xs []int32, target int32) int {
lo, hi := 0, len(xs)
for lo < hi {
mid := int(uint(lo+hi) >> 1)
if xs[mid] < target {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}
func linearRaw(items []Item, target string) int {
for i := range items {
if items[i].Title >= target {
return i
}
}
return len(items)
}
func lowerBoundRaw(items []Item, target string) int {
lo, hi := 0, len(items)
for lo < hi {
mid := int(uint(lo+hi) >> 1)
if items[mid].Title < target {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}
func lowerBoundStdRaw(items []Item, target string) int {
return sort.Search(len(items), func(i int) bool { return items[i].Title >= target })
}
