Структура данных и алгоритм для многомерного планировщика "объемной аренды"

Question

Абстрактная проблема. Представьте, что мир - это куб, состоящий из множества кубических ячеек по всем измерениям куба.

Теперь представьте, что вы можете арендовать определенные объемы на определенные периоды времени, например: вы арендуете объем 3x3x3 с координатами [1, 1, 1] - [3, 3, 3] на 2012 год. Затем вы арендовать объем 2x2x2 с координатами [4, 1, 1] до [5, 2, 2] на 2012 год.

Теперь представьте, что вы можете выпустить тома, которые вы арендовали, в периоды, за которые вы их приобрели. Например, арендовав тома, как определено выше, вы выделили объем ячейки 5x2x1 с координатами [1, 1, 1] - [5, 2, 1] для Q1'2012. Затем вы выходите из ячейки [5, 2, 2] за весь 2012 год.

Вы можете арендовать одни и те же объемы в нескольких «договорах аренды» и сдавать их в аренду, также в нескольких «договорах».

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

• Когда я могу выпустить определенную клетку?
• Какие клетки я могу выпустить за определенный период?
• Могу ли я выпустить ячейки с определенными координатами, не включая все измерения (например, кто-то хочет арендовать любые ячейки с координатой X между 2 и 4 на 2012 год)?

Подход с использованием грубой силы (попробуйте каждую комбинацию для проверки) не подлежит сомнению. Набор данных, который мне нужен, чтобы работать, является 5-мерным (с большим количеством измерений, которые скоро появятся), а размеры в среднем составляют 100-200 элементов.

Answer 1

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

Это подсказывает мне кое-чтонапример, http://en.wikipedia.org/wiki/K-d_tree или, возможно, какая-то n-мерная версия http://en.wikipedia.org/wiki/Octree.. Выгода, конечно, в том, что эти структуры данных исчерпывают свои возможности по мере увеличения числа измерений.

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

Answer 2

Как указывает mcdowella, деревья Octree и kd теряют эффективность, поскольку число измерений увеличилось за пределы примерно 4 или 5. Поскольку вы еще не сказали, что это за измерения, я предполагаю, что они являются свойствами объектов, которые выговорим о.Просто поместите их в СУБД и используйте индексы для этих полей.Хорошая реализация может иметь хорошую производительность при выполнении запроса к элементам с множественным индексированием.

Если у ваших измерений есть двоичные значения (или небольшие перечисления), то, вероятно, что-то еще будет лучше.