缓存复杂数据的最佳方法

Question

我有一个表,用于根据号码的前缀存储语音呼叫的费用:

Prefix  ratio 
44      0.01597
447     0.04958
447530  0.03
447531  0.048
447532  0.04950
1       0.1
97      0.1

在表中查找数字的前缀有点复杂,因为需要最大匹配前缀.例如,
前缀4475122112是447
,前缀4475302112是447530

我想将表缓存在内存中,以通过减少数据库交互来提高性能.获取数字前缀(然后是它的速率)需要在缓存上进行搜索

我发现了两种方法:

1. 将它们存储在纯地图中.在地图上搜索可以很简单,因为扫描所有地图(可能是懒惰的).
2. 将链表结构创建为树.而短前缀接近根,最长前缀接近叶子.

现在,缓存此类数据的最佳方法是什么？还是有其他机制吗？

Answer 1

将它们存储在地图中,然后尝试您要查找其成本的数字.如果数字(键)不在地图中,请剪掉其最后一位数字并重复.这样,如果找到匹配项,保证将是最长的前缀.

这是一个示例查找功能:

var prefixCostMap = map[uint64]float64{
    44:     0.01597,
    447:    0.04958,
    447530: 0.03,
    447531: 0.048,
    447532: 0.04950,
    1:      0.1,
    97:     0.1,
}

func lookup(num uint64) (longestPrefix uint64, cost float64, ok bool) {
    longestPrefix = num

    for longestPrefix > 0 {
        cost, ok = prefixCostMap[longestPrefix]
        if ok {
            break
        }
        longestPrefix = longestPrefix / 10 // Cut off last digit
    }

    return
}

测试它:

fmt.Println(lookup(4475122112))
fmt.Println(lookup(4475302112))
fmt.Println(lookup(999))

输出(在Go Playground上试试):

447 0.04958 true
447530 0.03 true
0 0 false

注意:这不支持从0开始的数字.如果您还需要处理它,您可以将数字存储为字符串值,因此0将保留初始数字.

这是string版本的样子:

var prefixCostMap = map[string]float64{
    "44":     0.01597,
    "447":    0.04958,
    "447530": 0.03,
    "447531": 0.048,
    "447532": 0.04950,
    "1":      0.1,
    "97":     0.1,
    "0123":   0.05,
}

func lookup(num string) (longestPrefix string, cost float64, ok bool) {
    longestPrefix = num

    for longestPrefix != "" {
        cost, ok = prefixCostMap[longestPrefix]
        if ok {
            break
        }
        longestPrefix = longestPrefix[:len(longestPrefix)-1] // Cut off last digit
    }

    return
}

测试它:

fmt.Println(lookup("4475122112"))
fmt.Println(lookup("4475302112"))
fmt.Println(lookup("999"))
fmt.Println(lookup("0123456"))

输出(在Go Playground上试试):

447 0.04958 true
447530 0.03 true
 0 false
0123 0.05 true