Каков наиболее эффективный (но достаточно гибкий) способ хранения многомерных данных переменной длины?

Часто такие виды динамических сетчатых структур могут быть очень сложными для эффективной работы, но в блочно-структурированных адаптивных кодах уточнения сетки (распространенных в астрофизике, где сложная геометрия не важна) или коде спектральных элементов, где у вас большие размеры блоков. , это часто гораздо меньшая проблема. У вас так много работы для каждого блока/элемента (по крайней мере, 10 ^ 5 ячеек x 2 точки/ячейка в вашем случае), что стоимость переключения между блоками сравнительно невелика.

Имейте также в виду, что обычно вы не можете делать слишком много тяжелой работы над каждым элементом или блоком, пока значительный объем данных этого блока уже не находится в кэше. Вам уже придется сбросить большую часть данных блока N из кеша, прежде чем вы все равно проделаете большую работу над блоком N + 1. (В вашем коде могут быть некоторые операции, которые являются исключениями из этого, но это, вероятно, не те операции, на которые вы в любом случае тратите много времени, с кэшем или без кэша, потому что повторное использование данных невелико — например, поэлементные операции над значения ячейки). Таким образом, размещение блоков/элементов рядом друг с другом не обязательно является большой проблемой; с другой стороны, вы определенно хотите, чтобы блоки/элементы были смежными.

Также обратите внимание, что вы можете перемещать блоки, чтобы они оставались непрерывными при изменении размера, но не только все эти копии памяти также будут стирать ваш кеш, но и сами копии памяти становятся очень дорогими. Если ваша проблема заключается в заполнении значительной части памяти (а так ли это всегда?), скажем, 1 ГБ, и вам нужно переместить 20% этого места после уточнения, чтобы снова сделать все непрерывным, это 0,2 ГБ (чтение + запись). ) / ~ 20 ГБ / с ~ 20 мс по сравнению с перезагрузкой (скажем) 16 000 строк кэша со скоростью ~ 100 нс каждая ~ 1,5 мс. И ваш кеш все равно удаляется после перетасовки. Возможно, это все же стоило бы сделать, если бы вы знали, что будете выполнять уточнение/удаление определения очень редко.

Но на практике большинство кодов адаптивной сетки в астрофизической гидродинамике (где я знаю коды достаточно хорошо, чтобы сказать) просто поддерживают список блоков и их метаданных и не беспокоятся об их смежности. YMMV, конечно. Мое предложение: прежде чем тратить слишком много времени на создание идеальной структуры данных, сначала просто протестируйте операцию на двух элементах дважды; первый, с элементами в порядке и вычислениями над ними 1-2, а второй, выполняя операцию в «неправильном» порядке, 2-1, и несколько раз синхронизируя два вычисления.

Для каждой ячейки сохраните смещение, по которому можно найти данные ячейки в непрерывном массиве. Это отображение смещения очень эффективно и широко используется. Вы можете изменить порядок ячеек для повторного использования кеша в обходах. При изменении порядка или количества ячеек создайте новый массив и выполните интерполяцию, а затем выбросьте старые массивы. Это хранилище намного лучше для внешнего анализа, потому что такими операциями, как внутренние произведения в методах Крылова и стадиями в методах Рунге-Кутта, можно управлять без привязки к сетке. Это также требует минимальной памяти на вектор (например, в базах Крылова и с интегрированием по времени).