Вот интересная головоломка со структурой данных, с которой, возможно, вы все можете мне помочь, для контекста я пишу C #.
Контекст / Ограничения:
Я использую библиотеку (новыйВ частности, пакет предварительного просмотра Unity ECS, который позволяет мне хранить данные очень компактным / эффективным / собственным способом для молниеносного доступа и манипуляций без сбора мусора.Некоторое время он поддерживал сохранение данных в FixedArray s:
ComponentType.FixedArray<T>(int fixedCapacity) //pseudo-code
. API не позволяет хранить какие-либо управляемые данные в этих массивах из соображений производительности и безопасности, что означает, что они должнывсе они должны быть линейными (без вложенных массивов или нескольких измерений), а сами элементы данных должны быть предельно простыми (примитивы или напрямую сериализуемые структуры, не должны быть причудливые списки LinkedLists или ссылки на другие структуры данных). Я не могу использовать HashTable или Dictionary или любую другую подобную высокоуровневую структуру данных для решения этой проблемы , я должен использовать предоставленную структуру данных!
Проблема:
Я пытаюсь сохранить базовый объект "Entity" в массиве, который имеет связанную целочисленную координату 3D-точки.Я хочу получить доступ к структуре с этой координатой и извлечь / изменить / удалить мой объект из указанной координаты.Таким образом, это была простая проблема доступа к линейному индексируемому массиву фиксированной ширины с использованием трехмерных координат, который стал возможен с помощью хэш-функции.
//Pseudo-Code, this is not the actual code itself.
//In actuality the Fixed Arrays are associated with Entities in an ECS system.
var myStructure = new ComponentType.FixedArray<Entity>(512);//define array
struct DataPair {
Entity entity;//the element we're storing
Vector3 threeDIntegerCoordinate;//from 1x1x1 to 8x8x8
}
//...
int lookupFunction(Vector3 coordinate) {...} //converts 3D coord to 2D linear index
DataPair exampleDataPair = new DataPair(...);
//Data WAS stored like this:
myStructure[lookupFunction(exampleDataPair.threeDIntegerCoordinate)] = exampleDataPair.entity;
//Extremely fast access/lookup time due to using coordinate as index value.
По сути, я сгенерировал переменную величину (от 1 до 512, один 8x8x8куб) Объекты и сохраните их по индексу в FixedArray, используя функцию перевода, которая коррелирует значение линейного индекса с каждой отдельной трехмерной координатой точки.Поиск в фиксированном массиве для значения координаты был чрезвычайно быстрым, так же просто, как доступ к индексу.
Однако !
Пакет был обновлен, и они заменили FixedArray с новой DynamicBuffer структурой данных, которая теперь переменной ширины.Те же ограничения применяются к тому, какие данные могут быть сохранены, но теперь, если куб сущностей является разреженным (не полностью заполненным), ему не нужно резервировать место для этой несуществующей ссылки на сущность в структуре.Это значительно сократит использование памяти, учитывая, что большинство кубов сущностей не полностью заполнены, и я храню в памяти буквально миллионы этих буферов за раз.Элементы буфера индексируются целым числом.Можно использовать несколько DynamicBuffer с одновременно (это означает, что мы можем хранить координаты рядом с элементами в двух параллельных буферах при необходимости).
//New data structure provided. Variable-width! Also indexed linearly.
var myStructure = new ComponentType.DynamicBuffer<Entity>();
//Is very similar to C# List or ArrayList in Java, for example, contains functions:
myStructure.Add(T element);
myStructure.AddRange(...);
myStructure.Length();
myStructure.resizeUninitialized(int capacity);
myStructure.Clear();
По сути, Каков наиболее эффективный способ хранения этого переменного числа элементов в динамической безразмерной структуре данных (аналогично списку) при сохранении трехмерного индексирования на основе координат без использования сложных вложенных структур данных для этого?Моя система больше зависит от производительности по времени поиска / доступа, чем по объему памяти.
Возможные решения:
Наивное решение состоит в том, чтобы сделать все длины DynamicBuffer равнымидо максимального количества элементов, которые я бы хотел сохранить (512 томов сущностей), имитируя FixedArray с.Это потребовало бы минимальных изменений в моей кодовой базе и позволило бы мне получить доступ к ним по координатам, используя мою текущую функцию перевода, но не использовало бы преимущества компактных функций динамической структуры данных.Это выглядело бы так:
//Naive Solution:
myStructure.resizeUninitialized(512); //resize buffer to 512 elements
//DynamicBuffer is now indexed identically to FixedArray
Entity elementToRetrieve = myStructure[exampleDataPair.threeDIntegerCoordinate];
Мое предполагаемое решение - использовать две параллельные DynamicBuffer с: одну со всеми сущностями, другую со всеми трехмерными точками.Затем, когда я хочу найти объект по координатам, я ищу трехмерную точку в буфере координат и использую индекс этого элемента, чтобы найти соответствующий объект в основном буфере.
//Possible better solution:
myStructure1 = new ComponentType.DynamicBuffer<Entity>();
myStructure2 = new ComponentType.DynamicBuffer<Vector3>();
//to access an element:
Entity elementToRetrieve = myStructure1[myStructure2.Find(exampleDataPair.threeDIntegerCoordinate)];
//I would have to create this theoretical Find function.
Минусы этогорешение:
- Требуется поиск, что означает, что, вероятно, также потребуется сортировка.
- Сортировка должна выполняться при каждом значительном изменении структуры, что приведет к добавлению БОЛЬШОГО количествавычислительных затрат.
- Потребуется написать свои собственные алгоритмы поиска / сортировки поверх и без того чрезвычайно сложной структуры данных, которая не предназначена для поиска / сортировки (возможно, она не хранится линейно в памяти).
- Местностьссылки?Очень важно, чтобы кеширование / спекулятивное выполнение процессора сохранялось для высокой производительности.
Как найти удачный посредник между наивным решением и комплексным решением, включающим поиск / сортировку?Существуют ли какие-либо теоретические структуры данных или алгоритмы для решения этой проблемы, которые мне просто не хватает?По сути, мне нужно эффективно использовать список, как карту.
Извините, если это действительно длинный вопрос, но я хотел понять это правильно, это мой первый пост здесь, на StackExchange.Пожалуйста, будьте нежны!Спасибо за вашу помощь!