Тренды

Шаблон Flyweight (Приспособленец) на Go

25.02.2020

Приспособленец — это структурный шаблон проектирования, в котором объект, представляющий себя как уникальный экземпляр в разных местах программы, по факту не является таковым. Цель — оптимизация работы с памятью путём предотвращения создания экземпляров элементов, имеющих общую сущность. Flyweight используется для уменьшения затрат при работе с большим количеством мелких объектов. — Wikipedia

Позже продемонстрирую шаблон «Приспособленец» с двумя примерами на Go, а сначала оптимизируем кэши, использующие базовые данные, а затем другой кэш с повторяющимися данными. Теперь за дело! Все примеры написаны на Golang и в полном объёме приведены в конце статьи.

Предварительные замечания

Для обоих примеров используется тип:

// Player обозначает игрока в игре.
type Player struct {
    ID uint32
    Handle, Name, Country string
    Games []string
}

Определение игрока.

Игроки на игровой платформе. Немного притянуто за уши, но для наших целей в самый раз. Пример:

playerOne := Player {
    ID: 1,
    Handle: "Razzor",
    Name: "Dave McTesty",
    Country: "US",
    Games: []string{"Fire Emblem", "Smash Bros Ultimate"},
}

Первый игрок.

Первый пример: один кэш, три метода поиска

Представьте, что для быстрого доступа к игрокам в приложении нам надо каждого игрока Player поместить в кэш с возможностью находить их по ID, нику Handle и стране Country. Вот как могла бы выглядеть первая (наивная) реализация.

Три структуры данных с одними и теми же игроками:

var (
    playerIDMap      = make(map[uint32]Player)
    playerHandleMap  = make(map[string]Player)
    playerCountryMap = make(map[string][]Player)
)

Эти данные получены из базы данных перебором отдельных строк таблицы и добавлением в карту, причём для каждого загружается экземпляр игрока Player с полями из каждой строки.

Использование карт в поиске объясняется их эффективностью: когда ключ уже есть, не нужно каждый раз перебирать всю структуру данных — O(n) операций —, достаточно провести прямой поиск за постоянное время, O(1).

Важная оптимизация при наличии тысяч или даже миллионов игроков. Остановимся ненадолго на функциях поиска для каждого из наших игроков.

Функции поиска до рефакторинга:

// FindPlayerByID возвращает игрока с данным ID, если таковой находится.
// В противном случае возвращается пустой Player.
func FindPlayerByID(ID uint32) Player {
    if p, ok := playerIDMap[ID]; ok {
        return p
    }
    return Player{}
}

// FindPlayerByHandle возвращает игрока с заданным ником,
// если таковой находится. В противном случае возвращается пустой Player.
func FindPlayerByHandle(handle string) Player {
    if p, ok := playerHandleMap[handle]; ok {
        return p
    }
    return Player{}
}

// FindPlayerByCountry возвращает всех игроков данной страны,
// если таковые находятся. В противном случае возвращается пустой срез.
func FindPlayerByCountry(code string) []Player {
    if ps, ok := playerCountryMap; ok {
        return ps
    }
    return []Player{}
}

Довольно просто.

Но здесь проблема: каждый игрок присутствует здесь трижды, расходуя до трёх раз больше памяти, чем необходимо. Вернёмся к нашим объявлениям кэшей и решим эту проблему.

Объявление, использующее ID игрока Player, подходит по двум причинам: во-первых, потому что ID служит первичным ключом и, во-вторых, потому что uint32 занимает гораздо меньше места, чем Handle игрока Player, строки произвольной длины. Теперь выполним рефакторинг.

Структуры данных после рефакторинга:

var (
    playerIDMap      = make(map[uint32]Player)
    playerHandleMap  = make(map[string]uint32)   // ref: playerIDMap
    playerCountryMap = make(map[string][]uint32) // ref: playerIDMap
)

И playerCountryMap, и playerHandleMap служат указателями на playerIDMap. Очевидно, придётся выполнить рефакторинг функций поиска.

Функции поиска после рефакторинга:

// FindPlayerByID возвращает игрока с данным ID, если таковой находится.
// В противном случае возвращается пустой Player.
func FindPlayerByID(ID uint32) Player {
    if p, ok := playerIDMap[ID]; ok {
        return p
    }
    return Player{}
}

// FindPlayerByHandle возвращает игрока с данным ником,
// если таковой находится. В противном случае возвращается пустой Player.
func FindPlayerByHandle(handle string) Player {
    if id, ok := playerHandleMap[handle]; ok {
        return FindPlayerByID(id)
    }
    return Player{}
}

// FindPlayerByCountry возвращает всех игроков данной страны,
// если таковые находятся. В противном случае возвращается пустой срез.
func FindPlayerByCountry(code string) []Player {
    if ids, ok := playerCountryMap; ok {
        ps := make([]Player, len(ids))
        for i, id := range ids {
            p := FindPlayerByID(id)
            ps[i] = p
        }
        return ps
   }
    return []Player{}
}

Примечательно, что первая функция FindPlayerByID не изменилась. Вторая, FindPlayerByHandle, вместо игрока Player теперь будет получать ID игрока Player и в завершение поиска перейдёт к вызову FindPlayerByID. Теперь у нас два поиска и сложность возросла с O(1) до O(2), но это по-прежнему постоянное время и разница здесь будет несущественной.

А вот с третьей функцией уже поинтереснее. Мы создаём срез, инициализированный размером среза ID, который получаем в первом поиске, а затем перебираем эти ID, пытаясь найти каждый из них отдельно и добавляя игрока Player в срез.

Причём не нужно проверять наличие ID, потому что мы контролируем кэш: мы знаем, что он есть. Из-за цикла сложность становится O(n+1) или просто O(n). Это хуже прямого поиска. Здесь возможны две стратегии:

Продолжать работать с этой реализацией: чуть более медленной, но позволяющей сэкономить память.
Придерживаться первоначальной реализации: она требует больше памяти, зато поиск ускорится.

Всегда выбирайте ту стратегию, которая подходит той или иной ситуации. Кроме того, эти стратегии можно и даже нужно комбинировать в зависимости от каждого конкретного случая.

Завершая первый пример, отметим, что вместо uint32 можно использовать указатели для ссылки. Подход останется неизменным, а вы сможете всегда использовать указатели, ссылающиеся на исходные структуры, вместо того, чтобы выполнять несколько взаимозависимых поисков.

Но не надо забывать о том, что кэш с тысячами и даже миллионами указателей увеличивает и количество указателей, с которыми приходится управляться сборщику мусора. Это может негативно сказаться на времени работы механизма автоматического управления памятью, затягивая паузы при сборке мусора.

Второй пример: репликация данных

Представим сценарий, где мы снова помещаем в кэш игроков Player, причём все они играли в одни и те же игры.

Возможно, один из издателей видеоигр, CrashyGames, Inc., запросил локально управляемый список всех игроков в платформе, игравших во все их игры, решив таким образом извиниться за сомнительное качество этих игр?

Сразу можно заметить, что можно сэкономить много памяти, не сохраняя поле игр Games для каждого игрока Player. Но это поле нам нужно как часть типа данных, поэтому сохраним его отдельно. Мы сможем добавить его конкретному игроку Player, когда на него поступит запрос. Для этого нам понадобится второй тип данных. Назовём его cachedPlayer:

// cachedPlayer — это игрок Player, только без поля игр Games.
type cachedPlayer struct {
    ID uint32
    Handle, Name, Country string
}

Определение cachedPlayer.

Этот тип данных мы написали со строчной буквы. Не будем экспортировать этот тип, используем его только внутри, в нашем кэше. Вот он наш кэш вместе со списком игр:

var games = []string{"Flappy Fish", "Ducks'n'Dogs", "Backflip Pro"}

var crashyGamesPlayers map[uint32]cachedPlayer

Кэш и список игр.

На этот раз будем находить их только непосредственно по ID, которые представляет uint32. В игры CrashyGames играют миллионы людей, поэтому делать эту оптимизацию имеет смысл.

Итак, перейдём к коду. Много работы здесь не требуется. Сначала объявим удобный метод на cachedPlayer, который преобразует его в обычного игрока Player:

// convertWith возвращает игрока Player, соответствующего типу данных cachedPlayer,
// с названиями игр.
func (c cachedPlayer) convertWith(games []string) Player {
    return Player{
        ID: c.ID,
        Handle: c.Handle,
        Name: c.Name,
        Country: c.Country,
        Games: games,
   }
}

Метод преобразователя для cachedPlayer.

Теперь можем реализовать поиск кэша:

// FindPlayerByID возвращает игрока с данным ID, если таковой находится.
// В противном случае возвращается пустой Player.
func FindPlayerByID(ID uint32) Player {
    if cp, ok := crashyGamesPlayers[ID]; ok {
        // Найден cachedPlayer.
        return cp.convertWith(games) // Использование игр в глобальном кэше.
    }
    return Player{}
}

Реализация FindPlayerByID.

Я оставил метод cachedPlayer.convertWith чистым. Он принимает в качестве параметров дополнительные поля, а FindPlayerByID — это функция-замыкание с переменной games, которая просто сохраняется в переменной, описанной в спецификации пакета, но вы можете реализовать её как-нибудь по-своему.

Вот и всё! Теперь у нас сохраняется всё сразу! Можно пойти ещё дальше и сохранять имена игроков Player в отдельной структуре данных в случае, если имеется много повторяющихся имён.

Старайтесь избегать лишних трат ресурсов, связанных со сравнением имён и ростом структуры данных с именами. Делайте эти сохранения только тогда, когда в них есть реальная необходимость.

Заключение

С шаблоном «Приспособленец» следует подружиться, но везде нужно находить золотую середину: переборщив с оптимизацией, можно всё только усложнить, а недооптимизировав — сделать приложение медленным и неповоротливым.

Прежде чем использовать шаблон «Приспособленец», надо учесть такие факторы, как размер структуры данных и влияние на читаемость и лёгкость в сопровождении кода приложения. И помните старую пословицу Дональда Кнута:

«Преждевременная оптимизация — корень всех зол».

А теперь оптимизируйте свой код!

Приложение

Первый пример после применения шаблона «Приспособленец»:

// Player — это игрок в игре.
type Player struct {
    ID uint32
    Handle, Name, Country string
    Games []string
}

var (
    playerIDMap      = make(map[uint32]Player)
    playerHandleMap  = make(map[string]uint32)   // ref: playerIDMap
    playerCountryMap = make(map[string][]uint32) // ref: playerIDMap
)

// FindPlayerByID возвращает игрока с данным ID, если таковой находится.
// В противном случае возвращается пустой Player.
func FindPlayerByID(ID uint32) Player {
    if p, ok := playerIDMap[ID]; ok {
        return p
    }
    return Player{}
}

// FindPlayerByHandle возвращает игрока с данным Handle,
// если таковой находится. В противном случае возвращается пустой Player.
func FindPlayerByHandle(handle string) Player {
    if id, ok := playerHandleMap[handle]; ok {
        return FindPlayerByID(id)
    }
    return Player{}
}

// FindPlayerByCountry возвращает всех игроков данной страны,
// если таковые находятся. В противном случае возвращается пустой срез.
func FindPlayerByCountry(code string) []Player {
    if ids, ok := playerCountryMap; ok {
        ps := make([]Player, len(ids))
        for i, id := range {
            p := FindPlayerByID(id)
            ps[i] = p
        }
        return ps
   }
    return []Player{}
}

Второй пример после применения шаблона «Приспособленец»:

// Player — это игрок в игре.
type Player struct {
    ID uint32
    Handle, Name, Country string
    Games []string
}

// cachedPlayer — это игрок Player, только без поля игр Games.
type cachedPlayer struct {
    ID uint32
    Handle, Name, Country string
}

var games = []string{"Flappy Fish", "Ducks'n'Dogs", "Backflip Pro"}

var crashyGamesPlayers map[uint32]cachedPlayer

// convertWith возвращает игрока Player, соответствующего типу данных cachedPlayer,
// с названиями игр.
func (c cachedPlayer) convertWith(games []string) Player {
    return Player{
        ID: c.ID,
        Handle: c.Handle,
        Name: c.Name,
        Country: c.Country,
        Games: games,
   }
}

// FindPlayerByID возвращает игрока с данным ID, если таковой находится.
// В противном случае возвращается пустой Player.
func FindPlayerByID(ID uint32) Player {
    if cp, ok := crashyGamesPlayers[ID]; ok {
        // Найден cachedPlayer.
        return cp.convertWith(games) // Использование игр в глобальном кэше.
    }
    return Player{}
}

Шаблон Flyweight (Приспособленец) на Go

Предварительные замечания

Первый пример: один кэш, три метода поиска

Второй пример: репликация данных

Заключение

Приложение

Читайте также

Векторы - прошлое ИИ, хэши - будущее

Rust: взгляд старого программиста

Как легко развертывать модели МО в 2022 году с помощью Streamlit,...

Тесты

Насколько хорошо вы знакомы с Mac?

Насколько хорошо вы знаете React?

Насколько хорошо вы разбираетесь в сетях?