Java: Как сделать индексирование на основе позиции (x, y) с чрезвычайно высокой производительностью?

Question

У меня есть игровое поле квадратного двухмерного пространства размером до 64 на 64 плитки. Каждая плитка может, но не всегда содержит игровой элемент. Как часть алгоритма ИИ, который генерирует возможные будущие состояния для анализа, я должен быть в состоянии:

• Вставка и удаление игровых фигур в координатах x, y (1 м + раз в секунду)

• Проверьте, присутствует ли игровой фрагмент, используя координаты x, y (1 м + раз в секунду)

• Доступ к этим частям игры (1 м + раз в секунду)

• Клонирование доски (100k + раз в секунду)

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

Мне нужно клонировать доски и не могу повторно использовать доски, поскольку изменения в досках должны происходить только на той доске, с которой я работаю. Поэтому мне нужно найти способ генерировать достаточное количество объектов, которые позволяют индексировать местоположение, при этом обеспечивая достаточную скорость. Теоретически, решение, которое не производит новые платы, но использует и очищает устаревшие платы, могло бы работать, но для этого требовался бы тип контейнера, который был бы дешев для очистки, обеспечивая при этом грязный доступ к O (1), вставку и удаление.

Вещи, которые я пробовал:

• Метод 2d-массива (создание платы достигает предела пропускной способности памяти)

• массив 1d длины ширина * высота (создание платы достигает предела пропускной способности памяти)

• HashMap, который индексирует фрагменты с использованием класса упаковщика точек (время вставки и доступа слишком велико)

• Использование списка игровых объектов вместо индексации местоположения (время доступа слишком велико, поскольку оно O (N))

• Разделение карты на куски, инициализация только тех разделов доски, которые содержат объекты (посредственная производительность для всех, в целом не достаточно хорошая)

Могу ли я попробовать еще какие-нибудь решения?

Answer 1

После еще нескольких попыток я нашел решение, которое работает достаточно хорошо:

При запуске создайте гигантское хранилище готовых пустых досок 64x64, сделанных из массивов GamePiece 64x64.

Когда мне нужна доска. Я перебираю репозиторий, используя статический инкремент int, который возвращается к нулю, когда достигает конца. Я выбираю первую найденную доску, которая еще не используется, и устанавливаю ее как рабочую доску моего объекта Plan, который выполняет моделирование. Я помечаю эту доску как использованную (простой логический массив), чтобы другие объекты не пытались ее использовать. Если мне не удается найти чистую доску, я просто создаю новую с нуля (очень редко).

Я перебираю список фигур, полученных с клонируемой доски, и помещаю их на мою доску.

Затем я выполняю симуляцию, перемещаю фигуры и т. Д.

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

В итоге все получилось довольно хорошо. За исключением начала, мне, по сути, никогда не нужно создавать новые контейнеры или объекты, которые я уже не использовал, поэтому избегайте создания мусора. И клонирование, и очистка доски - это O (N), так как мне нужно перебирать только части, а не всю доску. Доступ / проверка и перемещение деталей по местоположению - все О (1) и очень дешево.

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

Answer 2

Иерархия

Какое бы решение вы ни выбрали, клонирование всех 64 * 64 = 4096 элементов - это слишком много. Поскольку ваши изменения незначительны, вы можете использовать иерархическое неизменное представление , например, 64 × 64 массива, и всегда клонировать только те части, которые изменяются:

Piece[][] getModifiedClone(Piece[][] original, int x, int y, Piece newPiece) {
    Piece[][] result = original.clone(); // clones 64 pointers only
    result[x] = result[x].clone(); // also clones 64 pointers only
    result[x][y] = newPiece;
    return result;
}

Это уменьшает накладные расходы с 64 * 64 до 64 + 64. Вам не нужно следовать вашей структуре строк / столбцов здесь. За счет некоторой манипуляции с индексным битом вы можете использовать другую структуру. Вам не нужно организовывать внутреннюю иерархию как 2D; Вы можете использовать 3 или 4 уровня и уменьшить накладные расходы до 16 + 16 + 16 или 8 + 8 + 8 + 8.

Microoptimizations

Существует только один тип объекта, но у него есть три важные переменные. Все три являются целыми числами, которые всегда <= 2000. Я мог бы упаковать все это в одно целое, но преобразования назад и вперед уничтожили бы время доступа. </p>

Вы можете быть правы, но что-то вроде

int pack(int a, int b, int c) {
    return (a << 22) + (b << 11) + (c << 0);
}

int unpackA(int packed) {
    return (packed >> 22) & 0x7FF;
}

int unpackB(int packed) {
    return (packed >> 11) & 0x7FF;
}

int unpackC(int packed) {
    return (packed >> 0) & 0x7FF;
}

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

Использование отмены

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

Основная информация

Полагаю, я бы выбрал комбинацию 4D-иерархии и упаковки, т. Е.

int getPackedPieceAt(int[][][][] board, int x, int y) {
   return board[x >> 3][x & 7][y >> 3][y & 7];
}

Работа с массивами 4D довольно уродлива, но все, что вам нужно, это вышеописанный метод, а этот

int[][][][] getModifiedClone(int[][][][] original, int x, int y, int newPiece) {
    ... just like above

}

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