Подскажите название и ссылку на алгоритм

[MGM]

Есть массив векторных дискретных данных (вектор определен на пространстве размености V для примера V=10 )число эленментов массива - N = $10^5$.. Дискретное пространство значений - куб на V допустим 100 на каждое измерение. То есть число дискретных отсчетов $10^{20}$.
Необходимо создать пирамидальную структуру, чтобы легко переходить из пространства данных в пространство значений.
Понятно, что пространсво значений сильно разрежено относительно данных - то есть на каждый вектор приходися $10^{15}$ неиспользованных значений.

Алгоритм создания такой структуры с моей точки зрения выглядит так:
1. создаем 100 узлов первого измерения и далее из каждого выращиваем дерево с ветвлением по мере поступдения значений векторов.
2. Кадое дерево требует выделения новой памаяти как под указатели, так и под параметры ветвления и анализа данных.

Если писать такую программу в С подобных языках, то возникает проблема с переаллокацией - из опыта знаю, что слишком много указателей под каждый из которых выделена память на массив, просто затыкает вычислительный процесс. Поэтому навеняка есть алгоритм, который работает напрямую с заранее выделенной памятью (пусть с некоторым кратным запасом пропорциональным N).
То есть сначала оценивается максимальная память на данные и на указатели, а затем они просто переоаределяются.
Заранее прошу прощение за сумбурное объяснение, но программированием занялся лишь через пять лет после окончания физфака, и было это очень давно.
Так что базовые алгоритмы прошли мимо меня. :)(Одно время даже считал себя автором depth first search и dynamic programming алгоритмов).

Поэтому заранее спасибо, если дадите ссылку на подобный алгоритм (что-то похожее должно быть в базовых классах С++)

[arseniiv]

MGM в сообщении #1418207 писал(а):

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

Ещё раз расскажите, какие операции (и с какой желательно временной сложностью) нужно уметь делать над такой структурой, а то действительно не очень-то ясно.

Наобум предложу что-нибудь типа k-d tree; ещё можно поискать по словам типа «multidimensional spatial index», но вообще это всё может быть мимо. (И ещё кстати $V$ — не очень удобное название для размерности пространства, обычно так обозначают сами пространства.)

[realeugene]

MGM в сообщении #1418207 писал(а):

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

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

[Pavia]

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

А так для каждого массива свой запас надо. Я бы изучил опыт частиц в PhysX там до 0,5*10^9 обрабатывают в реальном времени. Так что ваши 10^15 от 2,5 часов до суток будут считаться.

https://github.com/NVIDIAGameWorks/Phys ... alHash.cpp