2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Подскажите название и ссылку на алгоритм
Сообщение29.09.2019, 19:15 
Аватара пользователя


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

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

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

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

 Профиль  
                  
 
 Re: Подскажите название и ссылку на алгоритм
Сообщение29.09.2019, 19:57 
Заслуженный участник


27/04/09
28128
MGM в сообщении #1418207 писал(а):
Заранее прошу прощение за сумбурное объяснение, но программированием занялся лишь через пять лет после окончания физфака, и было это очень давно.
Ещё раз расскажите, какие операции (и с какой желательно временной сложностью) нужно уметь делать над такой структурой, а то действительно не очень-то ясно.

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

 Профиль  
                  
 
 Re: Подскажите название и ссылку на алгоритм
Сообщение12.10.2019, 16:29 


27/08/16
9426
MGM в сообщении #1418207 писал(а):
Поэтому навеняка есть алгоритм, который работает напрямую с заранее выделенной памятью
Угу, есть, усли все узлы одного размера. Выделяете память в виде большого массива узлов, объединяете все узлы в один список свободных узлов, после чего аллокацию и деаллокацию узла делаете не через malloc, а забирая новый узел из списка и возвращая освободившийся узел в список свободных. Можно и не выделять сразу всё место, а доаллоцировать из общей кучи блоки памяти для новых узлов при исчерпанеии списка свободных.

 Профиль  
                  
 
 Re: Подскажите название и ссылку на алгоритм
Сообщение12.10.2019, 17:19 
Аватара пользователя


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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group