Лучший способ кешировать сложные данные

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