间接用哈希表记录时间戳很简略，大家都会，参考代码中的ShouldPrintMessageDefault，等同官网题解2。然而奇怪的是在这题中，如果应用Go语言配合LRU定期删除map中键值对，参考ShouldPrintMessageLRU，相似官网题解1，不过队列改成了LRU缓存。仿佛对优化并不显著。不论是惯例benchmark还是leetcode计时器都显示区别不大。
剖析了下起因有几个。
Go map自身不会放大。
map自身如果因为某种起因产生了增长，则再也不会放大，即便删除了局部甚至全副键值对。因为删除键值对只是将map中键值对置0，但曾经调配的桶不会被回收。然而短期来看，删除键值对的确能够减缓map增长的速率。因为map中的键值对少了，就不容易产生扩容。而主动扩容会导致不必要的内存调配，以及扩容过程中长期桶会造成额定的性能抖动。不过在足够多的测试下，map会因为哈希抵触必然扩容。
该题值类型为
int，自身太小了，无奈应用指针优化。因为即便map自身不会放大，指针类型的值在置0后也会被GC回收。
数据问题。
在单次benchmark中，10次调用，优化后内存占用相比不优化是2倍，也就是负优化。100次调用则为40%，开始有优化了，1000次则为21%，优化很显著。然而在数据始终减少大略到1千万时，就是没有区别了。leetcode的数据都偏小，而benchamrk的规范基准测试都很大，而且会通过测试次数取平均值，最初后果是相似的。
package leetcodeimport ( "fmt")type Logger struct { logHist map[string]int //log历史，k:log信息，v:工夫戳 lruQueue []struct { //lru缓存 msg string ts int } timeLimit int capacity int //设定LRU容量 maxMapLen int //呈现过的最长map maxSliceLen int //呈现过的最长slice长度}//调试用，察看字段呈现的最长长度func (l *Logger) PrintMaxLen() { fmt.Println("map", l.maxMapLen) fmt.Println("slice", l.maxSliceLen)}//调试用，记录字段呈现的最长长度func (l *Logger) logMaxLen() { max := func(a, b int) int { if a > b { return a } else { return b } } l.maxMapLen = max(l.maxMapLen, len(l.logHist)) l.maxSliceLen = max(l.maxSliceLen, len(l.lruQueue))}func Constructor359() Logger { const CAPACITY = 10 const TIMELIMIT = 10 return Logger{ logHist: make(map[string]int, CAPACITY), lruQueue: make([]struct { msg string ts int }, 0, CAPACITY), timeLimit: TIMELIMIT, capacity: CAPACITY}}//简略的实现，间接在map中记录时间戳，map会有限增长func (l *Logger) ShouldPrintMessageDefault(ts int, msg string) bool { l.logMaxLen() if lastTs, ok := l.logHist[msg]; ok && ts-lastTs < 10 { return false } l.logHist[msg] = ts return true}//简略的LRU实现，然而map依然可能忽然增长func (l *Logger) ShouldPrintMessageLRU(ts int, msg string) bool { // get l.logMaxLen() var existed bool var lastTs int if lastTs, existed = l.logHist[msg]; existed && ts-lastTs < 10 { return false } //clean if len(l.lruQueue) > l.capacity && ts-l.lruQueue[0].ts > l.timeLimit { delete(l.logHist, l.lruQueue[0].msg) l.lruQueue[0] = struct { //防止内存泄露 msg string ts int }{} //l.lruQueue = l.lruQueue[1:] //防止数组始终往后缩导致重新分配 l.lruQueue = append(l.lruQueue[:0], l.lruQueue[1:]...) } //put newNode := struct { msg string ts int }{msg, ts} if existed { l.logHist[msg] = ts if len(l.lruQueue) > 1 { var oldIndex int for oldIndex = 0; l.lruQueue[oldIndex].msg == msg; oldIndex++ { } l.lruQueue = append(l.lruQueue[:oldIndex], l.lruQueue[oldIndex+1:]...) l.lruQueue[len(l.lruQueue)-1] = newNode } } else { l.logHist[msg] = ts l.lruQueue = append(l.lruQueue, newNode) } return true}benchmark
import ( "fmt" "math/rand" "runtime" "src/leetcode" "testing")var words = []string{ "apple", "banana", "cherry", "date", "elderberry", "fig", "grape", "honeydew", "kiwi", "lemon", "mango", "orange", "peach", "quince", "raspberry", "strawberry", "tangerine", "uva", "watermelon", "xylophone", "yam", "zucchini", "avocado", "blueberry", "carrot", "dragonfruit", "eggplant", "flan", "grapefruit", "huckleberry", "icecream", "jackfruit", "kiwifruit", "leek", "melon", "nectarine", "olive", "pineapple", "quail", "radish", "starfruit", "tomato", "ugli", "vanilla", "walnut", "ximenia", "yizdu", "ziti", "golang", "python",}//内存占用打印func printAlloc() { var m runtime.MemStats runtime.ReadMemStats(&m) fmt.Printf("%d MB\n", m.Alloc/1024/1024)}func BenchmarkDefault(b *testing.B) { b.ResetTimer() l := leetcode.Constructor359() for i := 0; i < b.N; i++ { msg := words[rand.Intn(50)] + words[rand.Intn(50)] + words[rand.Intn(50)] l.ShouldPrintMessageDefault(i, msg) } //单次测试的调试信息 //B := *(*uint8)(unsafe.Pointer(uintptr(unsafe.Pointer(*(**int)(unsafe.Pointer(&l)))) + 9)) //fmt.Println("\nthe hmap B size", B) //printAlloc() //l.PrintMaxLen()}func BenchmarkOptimized(b *testing.B) { b.ResetTimer() l := leetcode.Constructor359() for i := 0; i < b.N; i++ { msg := words[rand.Intn(50)] + words[rand.Intn(50)] + words[rand.Intn(50)] l.ShouldPrintMessageLRU(i, msg) } //单次测试的调试信息 //B := *(*uint8)(unsafe.Pointer(uintptr(unsafe.Pointer(*(**int)(unsafe.Pointer(&l)))) + 9)) //fmt.Println("\nthe hmap B size", B) //printAlloc() //l.PrintMaxLen()}benchmark 后果
#规范测试$ go test -bench=. -run=none -benchmem goos: linuxgoarch: amd64BenchmarkDefault-4 3917066 292.1 ns/op 27 B/op 1 allocs/opBenchmarkOptimized-4 4292064 306.7 ns/op 27 B/op 1 allocs/op#单次一万次测试$ go test -bench=. -run=none -benchmem -benchtime=1x goos: linuxgoarch: amd64BenchmarkDefault-4 1 2304085 ns/op 1211632 B/op 10289 allocs/opBenchmarkOptimized-4 1 2903396 ns/op 297440 B/op 10221 allocs/op