сокращение периода алгоритмов двумерного динамического массива в C ++

Question

Я определил двумерный динамический массив и выделил память для массивов. Размеры массивов совпадают друг с другом (256 * 256):

    double **I1,**I2;

    int M=256;
    int N=256;
    int i,j;

    I1= new double *[M+1];
    for(i=1;i<=M;i++)
    {I1[i]=new double [N+1];}

    I2= new double *[M+1];
    for(i=1;i<=M;i++)
    {I2[i]=new double [N+1];}

Затем я присвоил значения элементам массивов. Мне нужновыполнять математические алгоритмы на этих массивах. Я использовал много для циклов. И мой код работал очень и очень медленно.

Например, если я вычитаю I2 из I1 и назначил субстрактный массив другому двумерному массиву I3, я использовалэтот код:

double **I3;
double temp;
//allocate I3;
I3= new double *[M+1];
 for(i=1;i<=M;i++)
{I3[i]=new double [N+1];}


 //I3=I1-I2


for(i=1;i<=M;i++){
    for(j=1;j<=N;j++){
          temp=I1[i][j]-I2[i][j];
          I3[i][j]=temp;}
}

Как я могу сократить время выполнения C ++ без использования циклов for?Не могли бы вы посоветовать мне другие методы, пожалуйста?

С наилучшими пожеланиями ..

Answer 1

Прежде всего, в большинстве случаев я бы не советовал так вручную управлять вашей памятью.Я уверен, что вы слышали, что C ++ предлагает контейнерные классы, к которым могут применяться «алгоритмы».Эти контейнеры менее подвержены ошибкам (особенно в случае исключений), операции более выразительны, оптимизированы и обычно хорошо протестированы, поэтому доказали свою работоспособность.

В вашем случае, с размером массива, известным ранееможно использовать std :: vector без потери производительности (кроме как при создании), поскольку память гарантированно будет непрерывной и, следовательно, может использоваться как массив.Вам также следует подумать о выравнивании массива, так как вызов процедуры выделения в цикле не совсем быстрый - выделение затратно.При выполнении умножения матриц учитывайте распределение в парах строка-майор / столбец-мажор, это помогает кешированию ... но я отвлекся.

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

В этом конкретном случае, поскольку вы упомянули, что хотите «выполнять математические алгоритмы», я бы посоветовал вам взглянуть начисловая библиотека, которая может выполнять матричные / векторные операции, так как это, кажется, то, что вам нужно.

Для C ++ есть, например, Newmat и (более или менее)) канонические реализации BLAS / LAPACK (то есть Netlib , AMD ACML , ATLAS ).Они позволяют вам выполнять обычные (и не очень распространенные) операции, такие как сложение / вычитание векторов, умножение матриц и т. Д., Намного быстрее, как с использованием оптимизированных алгоритмов, так и оптимизаций в качестве инструкций SIMD, которые может предложить ваш процессор (например, SSE).

Очевидно, что при выполнении вычислений невозможно избежать итерации по этим значениям, но вы можете сделать это оптимизированным способом и со стандартным интерфейсом.

Answer 2

В порядке важности:

• Включите оптимизацию компилятора.
• Выделите один массив для каждой матрицы и используйте что-то вроде M * i + j для индексации.Это приведет к более быстрому распределению и, возможно, что более важно, будет более компактным и менее фрагментированным, чем множественные распределения.
• Привыкните к индексированию, начинающемуся с нуля, это сэкономит вам один элемент массива, и в целом нулевые сравнения могут быть быстрее..
• Я не вижу ничего плохого в использовании циклов for.
• Если вы готовы потратить еще больше усилий, вы можете использовать векторизованную библиотеку линейной алгебры сторонних производителей или векторизовать себя, используя такие вещи, какSSE * или графические процессоры.

Answer 3

Все уже в STL, используйте valarray .

См. Также: Как я могу использовать std :: valarray для хранения / манипулирования непрерывным 2D-массивом?

Answer 4

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

Вы могли бы рассмотреть возможность выделения 256 * 256 операций с плавающей запятой за один развместо того, чтобы вызывать новые 256 раз (а затем использовать некоторую арифметику индексации, потому что у вас есть только один индекс), но тогда, вероятно, проще найти библиотеку матриц, которая сделает это за вас.

Answer 5

Некоторые архитектуры имеют аппаратную поддержку векторной арифметики, так что одна инструкция будет суммировать все элементы массива значений типа double.

Однако первое, что вы должны сделать, чтобы ускорить программу, это измерить ее. Вы рассчитали свою программу, чтобы увидеть, где происходит замедление?

Например, одна вещь, которую вы, похоже, делаете в цикле for, - это большое выделение кучи, которое обычно медленное. Вы можете объединить все ваши массивы в один массив для большей скорости.

В настоящее время вы делаете логический эквивалент этого:

I3 = I1 - I2;

Если вы сделали это:

I1 -= I2;

Теперь I1 будет хранить результат. Это разрушит исходное значение I1, но позволит избежать выделения нового массива массивов.

Также цель C ++ состоит в том, чтобы определить классы для представления типа данных и операций над ним. Таким образом, вы можете написать класс для представления вашего динамического массива хранения. Или используйте существующий - проверьте библиотеку uBLAS .