Хранение данных листов, превышающих 100 миллионов плиток на слой, несколько слоев

Question

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

это означает, что 1 слой из 100 миллионов плиток будет равен ~ 96 МБ. однако я упустил из виду, сколько данных я могу на самом деле хранить в байте, и получается, что, конечно, я могу хранить только 256 тайлов. в результате получается квадратный корень из 256 * размеров текстур размером с плитку (в данном случае 256, поскольку размеры плиток равны 16). 256 * 256 размеров текстур слишком малы, поскольку каждая палитра может иметь только одну текстуру. строго ограничивает плитки, которые я могу иметь в слое.

Теперь я застрял в привязке, как будто я использую 2 байта (короткий) вместо 1 байта для хранения данных тайла. Я удвою использование памяти до ~ 192 МБ на слой. и я хочу 4 слоя как минимум. раздувать конечный продукт до 768 МБ оперативной памяти. я также не могу описать данные в данных, так как смещение массива каждого байта также является описанием его местоположения.

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

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

Answer 1

Я предлагаю представлять ваши данные в массиве, который отображается на двухмерную плоскость, используя кривую заполнения пространства, такую ​​как кривая Гильберта .

Затем сожмите ее, используя комбинацию кодирование Хаффмана и кодирование длин серий .Это будет особенно эффективно, если ваши данные часто повторяются локально (т. Е. Есть много разделов, которые находятся на одной плитке рядом друг с другом).

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

Например, начало второго байта блока (элемент 256) может быть в позиции 103, а началотретий блок (фрагмент 512) может быть в позиции 192.

Затем, скажем, чтобы получить доступ к 400-му фрагменту, вы можете решить, что это из второго блока, поэтому распакуйте второй блок (в данном случае из байта 103).до байта 191) и отсюда получаем плитку 400 - 256 = 144.Сохраните (кэшируйте) эти распакованные данные на данный момент, вероятно, если вы получаете соседние тайлы, они также будут в этом распакованном блоке.Возможно, в вашем массиве смещений вы должны также указать, какие блоки были недавно кэшированы, и где они находятся в кэше.

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

---

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