otter 最近又优化了吧, 看 benchmark 混合读写速度非常惊人, 我把最小堆去掉估计也赶不上

goos: linux
goarch: amd64
pkg: github.com/lxzan/memorycache/benchmark
cpu: 13th Gen Intel(R) Core(TM) i5-1340P
BenchmarkMemoryCache_SetAndGet-4 17393630 79.82 ns/op 0 B/op 0 allocs/op
BenchmarkOtter_SetAndGet-4 36321264 29.74 ns/op 0 B/op 0 allocs/op
BenchmarkRistretto_SetAndGet-4 5968552 179.7 ns/op 32 B/op 1 allocs/op
BenchmarkTheine_SetAndGet-4 5518321 237.0 ns/op 0 B/op 0 allocs/op
PASS
ok github.com/lxzan/memorycache/benchmark 27.342s

@cchq 一个递归方法搞定, 从 1809 ns/op 提高到了 883 ns/op

// 降序遍历 中序遍历是有序的
func (c *RBTree[K, V]) rangeDesc(curNode *rbtree_node[K, V], qb *QueryBuilder[K, V]) {
if c.end(curNode) || len(qb.results) >= qb.limit {
return
}

state := 0
if qb.rightFilter(curNode.data.Key) {
state += 1
}
if qb.leftFilter(curNode.data.Key) {
state += 2
}

switch state {
case 3:
c.rangeDesc(curNode.right, qb)
if len(qb.results) < qb.limit {
qb.results = append(qb.results, *curNode.data)
} else {
return
}
c.rangeDesc(curNode.left, qb)
case 2:
c.rangeDesc(curNode.left, qb)
case 1:
c.rangeDesc(curNode.right, qb)
default:
}
}

@kneo @cchq

感谢二位, 已经搞定了
在我现有逻辑上稍微改下就行了, 利用中序遍历一次得到多个结果, 减少重复计算. 原来 LIMIT N 要查 N 次, 现在最坏才是 N 次.

@cchq 只了解最基本的性质。左子结点比父节点小，右子结点比父节点大

@kneo ok ，我先去了解一下中序遍历的特性

@cchq 不从根节点开始找的话，可能会漏掉一些数据，有排序的

@MoYi123 调用次数多了会很慢，大量重复计算

@kneo 如果条件范围比较小，全部查出来再排序是个好办法

@kneo

> 为什么用红黑树

因为我在给红黑树加 feature

如果符合条件的结果非常多，全查出来会非常慢

一个一个地查虽然慢，但耗时非常稳定

怎么才能上 trending

苹果编译速度确实快，不仅仅是 clang, go 和 java 都是如此

49 年入国军, 好多有经验的开发都失业了

@lysShub 不过 string 底层还是有指针，这个解决起来很麻烦

@flynnlemon bucket 是缓存库的基本存储结构, 源码见 https://github.com/lxzan/memorycache/tree/swiss .
现在的代码里面直接用指针式链表维护 LRU 缓存了, 实测数组链表对于 GC 优化帮助不大. 虽然数据表面都是值类型, 但实际上 string 底层是有指针的, any 可能也会被扫描.

@flynnlemon 这里只讨论 GC

@zhazi 这里 https://docs.spring.io/spring-boot/docs/current/reference/html/data.html#data

@zhazi springboot data jdbc 那一段，看了半天都不知道 @Query 怎么用，去 github 看了下别人的 demo 一下就会了

@zhazi 不是公认的烂吗

我想到了, 再加一个堆, 以查询次数作为比较基准