dictionary - 缓存复杂数据的最佳方式

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. 将它们存储在纯映射中。在 map 上搜索可以像扫描所有 map 一样简单(也许是懒惰的)。
2. 将链表结构创建为树。而短前缀接近根，最长前缀接近叶子。

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

Answer 1

将它们存储在 map 中，然后尝试您要查找其成本的数字。如果数字(键)不在 map 中，则切断其最后一位数字并重复。这样，如果您找到匹配项，则保证这将是最长的前缀。

这是一个示例查找函数:

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