bfs_cost_test.go raw

   1  package cayley
   2  
   3  import (
   4  	"fmt"
   5  	"math"
   6  	"testing"
   7  	"time"
   8  )
   9  
  10  func TestBFSCost(t *testing.T) {
  11  	primes := []int64{11, 31, 101}
  12  	for _, P := range primes {
  13  		gs := StandardGens(P)
  14  		volume := P * (P*P - 1)
  15  
  16  		start := time.Now()
  17  		pf := gs.BFS(-1)
  18  		elapsed := time.Since(start)
  19  
  20  		// Estimate memory: Dist map + Parent map + Edge map.
  21  		// Each Mat2 = 4 int64 = 32 bytes. Each Path/node = ~diam * 1 byte.
  22  		// Rough: 3 maps × (32B key + 8B value overhead) × N
  23  		memKB := float64(len(pf.Dist)) * 80.0 / 1024.0
  24  
  25  		opsPerSec := float64(volume) / elapsed.Seconds()
  26  		microsPerOp := elapsed.Microseconds() / int64(volume)
  27  
  28  		t.Logf("P=%2d |G|=%9d  time=%8s  speed=%.0f v/s  μs/v=%d  mem≈%d KB  diam=%d",
  29  			P, volume, elapsed.Round(time.Microsecond), opsPerSec, microsPerOp,
  30  			int(memKB), pf.MaxDist())
  31  	}
  32  }
  33  
  34  func TestBFSCostExtrapolation(t *testing.T) {
  35  	// Extrapolate from small primes.
  36  	// BFS time = O(|G|) = O(P^3).
  37  	// At P=101: 1M vertices, ~4s.
  38  	// At P=2^216: ops/s stays roughly constant (~250K vertices/s).
  39  	// Time = (2^216)^3 / 250K seconds.
  40  
  41  	opsPerSec := 250000.0 // from P=101 measurement (1M / 4s)
  42  
  43  	for _, Pbits := range []int{10, 20, 30, 40, 60, 80, 100} {
  44  		P := math.Pow(2, float64(Pbits))
  45  		volume := P * P * P
  46  		seconds := volume / opsPerSec
  47  		//years := seconds / 31536000.0
  48  
  49  		memBytes := volume * 80.0 // 80 bytes per vertex (map overhead)
  50  		memGB := memBytes / 1e9
  51  
  52  		t.Logf("P=2^%d  |G|≈2^%.0f  time=%s  mem=%s",
  53  			Pbits, math.Log2(volume),
  54  			formatDuration(seconds),
  55  			formatMem(memGB))
  56  	}
  57  }
  58  
  59  func formatDuration(secs float64) string {
  60  	if secs < 60 { return fmt.Sprintf("%.0fs", secs) }
  61  	if secs < 3600 { return fmt.Sprintf("%.0fm", secs/60) }
  62  	if secs < 86400 { return fmt.Sprintf("%.0fh", secs/3600) }
  63  	if secs < 31536000 { return fmt.Sprintf("%.0fd", secs/86400) }
  64  	return fmt.Sprintf("%.0fy", secs/31536000)
  65  }
  66  
  67  func formatMem(gb float64) string {
  68  	if gb < 1 { return fmt.Sprintf("%.0fMB", gb*1000) }
  69  	if gb < 1000 { return fmt.Sprintf("%.0fGB", gb) }
  70  	if gb < 1e6 { return fmt.Sprintf("%.0fTB", gb/1000) }
  71  	return fmt.Sprintf("%.0fPB", gb/1e6)
  72  }
  73