Выбор наиболее эффективного контейнера (массива)

Это мой маленький большой вопрос о контейнерах, в частности, массивах.

Я пишу физический код, который в основном манипулирует большим ( > 1 000 000) набором "частиц" (с координатами 6 double). Я ищу лучший способ (с точки зрения производительности) реализовать класс, который будет содержать контейнер для этих данных, и который предоставит примитивы манипуляции для этих данных (например, экземпляр, operator[] и т.д.).

Существует несколько ограничений на использование этого набора:

его размер считывается из файла конфигурации и не изменяется во время выполнения.
его можно рассматривать как большой двумерный массив из N (например, 1 000 000) строк и 6 столбцов (каждый из которых хранит координату в одном измерении).
массив обрабатывается в большом цикле, к каждой "частице/линии" обращаются, и вычисление происходит с его координатами, а результаты сохраняются для этой частицы и т.д. для каждой частицы и т.д. для каждого итерация большой петли.
новые элементы не добавляются и не удаляются во время выполнения

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

Я изучил несколько вещей, и я хотел бы получить ваше мнение о том, что может дать мне лучшие результаты.

Как я понимаю, нет преимущества использовать динамически выделенный массив вместо std::vector, поэтому такие вещи, как double** array2d = new ..., loop of new, etc, исключаются.

Так что неплохо использовать std::vector<double>?

Если я использую std::vector, должен ли я создать двумерный массив вроде std::vector<std::vector<double> > my_array, который может быть проиндексирован как my_array[i][j], или это плохая идея, и было бы лучше использовать std::vector<double> other_array и использовать его с other_array[6*i+j].

Может быть, это может обеспечить лучшую производительность, тем более, что количество столбцов фиксировано и известно с самого начала.

Если вы считаете, что это лучший вариант, можно ли обернуть этот вектор таким образом, чтобы к нему можно было обращаться с помощью оператора индекса, определенного как other_array[i,j] // same as other_array[6*i+j] без накладных расходов (например, вызов функции при каждом доступе)?

Другим вариантом, который я использую до сих пор, является использование Blitz, в частности blitz::Array:

typedef blitz::Array<double,TWO_DIMENSIONS> store_t;
store_t my_store;

Где доступны мои элементы: my_store(line, column);.

Я думаю, что нет никакого преимущества использовать Blitz в моем случае, потому что я обращаюсь к каждому элементу один за другим, и что Блиц был бы интересен, если бы я использовал операции непосредственно с массивом (например, с матричным умножением), которым я не являюсь.

Считаете ли вы, что Blitz в порядке, или это бесполезно в моем случае?

Это те возможности, которые я рассмотрел до сих пор, но, возможно, лучший из них, я еще один, поэтому не стесняйтесь предлагать мне другие вещи.

Большое спасибо за вашу помощь по этой проблеме!

Edit:

Из очень интересных ответов и комментариев ниже хорошее решение выглядит следующим образом:

Используйте структуру particle (содержащую 6 двойников) или статический массив из 6 удвоений (это позволяет избежать использования двумерных динамических массивов)
Используйте vector или deque этой структуры или массива particle. Затем полезно перемещать их с помощью итераторов, и это позволит впоследствии перейти от одного к другому.

Кроме того, я могу использовать Blitz::TinyVector<double,6> вместо структуры.

Ответ 1

Прежде всего, вы не хотите разбросать координаты одной данной частицы по всему месту, поэтому я бы начал писать простой struct:

struct Particle { /* coords */ };

Тогда мы можем сделать простой одномерный массив этих Particles.

Я бы, вероятно, использовал deque, потому что этот контейнер по умолчанию, но вы можете попробовать vector, это всего лишь 1.000.000 частиц означает один кусок из нескольких МБ. Он должен держаться, но это может повредить вашу систему, если это когда-либо будет расти, а deque выделит несколько кусков.

Внимание

Как заметил Alexandre C, если вы идете по дороге deque, воздержитесь от использования operator[] и предпочитаете использовать стиль итерации. Если вам действительно нужен произвольный доступ и он чувствителен к производительности, vector должен быть быстрее.

Ответ 2

Так что неплохо использовать std::vector<double>?

Обычно, std::vector должен быть первым выбором контейнера. Вы можете использовать либо std::vector<>::reserve(), либо std::vector<>::resize(), чтобы избежать перераспределения при заполнении вектора. Лучше ли какой-либо другой контейнер можно найти с помощью измерения. И только путем измерения. Но сначала измерьте, все ли что-либо, в котором участвует контейнер (заполнение, доступ к элементам), стоит оптимизировать вообще.

Если я использую std::vector, должен ли я создать двухмерный массив, например std::vector<std::vector<double> > [...]?

Нет. IIUC, вы получаете доступ к своим данным для каждой частицы, а не к каждой строке. Если это так, почему бы не использовать a std::vector<particle>, где particle - это структура, содержащая шесть значений? И даже если я неправильно понял, лучше написать двумерную оболочку вокруг одномерного контейнера. Затем выровняйте свои данные в строках или столбцах - что быстрее с вашими шаблонами доступа.

Считаете ли вы, что Blitz в порядке, или это бесполезно в моем случае?

У меня нет практических знаний о blitz ++ и областях, в которых он используется. Но разве blitz ++ не все о шаблонах выражений для разворачивания операций цикла и оптимизации временных времен при манипулировании матрицами? ICBWT.

Ответ 3

Первое правило при выборе из контейнеров - использовать std::vector. Затем, только после того, как ваш код будет завершен, и вы сможете измерить производительность, вы можете попробовать другие контейнеры. Но сначала придерживайтесь вектора. (И используйте reserve() с самого начала)

Тогда вы не должны использовать std::vector<std::vector<double> >. Вы знаете размер ваших данных: он 6 удваивается. Не нужно, чтобы он был динамичным. Он постоянный и фиксированный. Вы можете определить структуру, которая удерживает вас в элементах частиц (шесть парных), или вы можете просто набрать ее: typedef double particle[6]. Затем используйте вектор частиц: std::vector<particle>.

Кроме того, поскольку ваша программа последовательно использует данные о частицах, содержащиеся в векторе, вы сможете воспользоваться преимуществами современной функции чтения кэш-памяти CPU с максимальной эффективностью.

Ответ 4

Вы можете пойти несколькими способами. Но в вашем случае не объявить std::vector<std::vector<double> >. Вы выделяете vector (и копируете его) на каждые 6 удвоений. Это слишком дорого.

Ответ 5

Если вы считаете, что это лучший вариант, можно ли обернуть этот вектор таким образом, чтобы к нему можно было обращаться с помощью оператора индекса, определенного как other_array [i, j]//так же, как other_array [6 * я + j] без накладных расходов (например, вызов функции при каждом доступе)?

(other_array[i,j] не будет работать слишком хорошо, поскольку i, j использует оператор запятой для оценки значения "i", затем отбрасывает и вычисляет и возвращает "j", поэтому он эквивалентен other_array[i]).

Вам нужно будет использовать один из:

other_array[i][j]
other_array(i, j)  // if other_array implements operator()(int, int),
                   // but std::vector<> et al don't.
other_array[i].identifier // identifier is a member variable
other_array[i].identifier() // member function getting value
other_array[i].identifier(double) // member function setting value

Вы можете или не хотите ставить get_ и set_ или аналогичные по двум последним функциям, если вы найдете их полезными, но из вашего вопроса, я думаю, вы не будете: функции предпочтительны в API-интерфейсах между частями больших систем с участием многих разработчиков или когда элементы данных могут меняться, и вы хотите, чтобы алгоритмы, работающие с данными, были независимыми от них.

Итак, хороший тест: если вы обнаружите, что пишете код типа other_array[i][3], где вы решили, что "3" - это двойное число со скоростью в нем и other_array[i][5], потому что "5" - это ускорение, тогда прекратите делать это и дайте им правильные идентификаторы, чтобы вы могли сказать other_array[i].speed и .acceleration. Тогда другие разработчики могут читать и понимать это, и вы гораздо менее склонны совершать случайные ошибки. С другой стороны, если вы повторяете эти 6 элементов, которые делают одинаковые вещи для каждого, тогда вы, вероятно, захотите, чтобы Particle удерживал двойную [6] или предоставлял operator[](int). Там нет проблем с выполнением обоих:

struct Particle
{
    double x[6];
    double& speed() { return x[3]; }
    double speed() const { return x[3]; }
    double& acceleration() { return x[5]; }
    ...
};

BTW/причина, по которой vector<vector<double> > может быть слишком дорогостоящей, состоит в том, что каждый набор из 6 удваивается будет распределяться в куче, а для быстрого выделения и освобождения многих реализаций кучи используют ведра фиксированного размера, поэтому ваш небольшой запрос будет округляется до следующего размера: это может быть значительным накладным расходами. Внешнему вектору также потребуется записать дополнительный указатель на эту память. Кроме того, распределение кучи и освобождение относительно медленное - в вашем случае вы будете делать это только при запуске и завершении работы, но нет особого смысла в том, чтобы сделать вашу программу медленнее без причины. Еще важнее то, что области в куче могут иметь место только в памяти, поэтому ваш оператор [] может иметь ошибки кэша, занимая более важные страницы памяти, чем необходимо, замедляя всю программу. Другими словами, векторы сохраняют элементы смежно, но направленные к векторам могут не быть смежными.