Как ускорить выделение памяти для 2D треугольной матрицы в c ++? - PullRequest
Новая
       26

Как ускорить выделение памяти для 2D треугольной матрицы в c ++?

2 голосов
/ 23 ноября 2010

Мне нужно выделить память для очень большого массива, который представляет собой треугольную матрицу.Я написал следующий код: 

const int max_number_of_particles=20000;
float **dis_vec;

dis_vec = new float **[max_number_of_particles];

for (i = 0; i<max_number_of_particles; i++)
  dis_vec[i] = new float *[i];

for (i = 0; i<max_number_of_particles; i++)
  for (j = 0; j<i; j++)
    dis_vec[i][j] = new float[2];

Проблема в том, что время, необходимое для этого (для выделения памяти), быстро увеличивается с увеличением размера матрицы.Кто-нибудь знает лучшее решение для этой проблемы?

Спасибо.

Ответы [ 2 ]

5 голосов
/ 23 ноября 2010

Выделите одномерный массив и конвертируйте индексы в индексы и наоборот. Одно распределение по сравнению с O(N) должно быть намного быстрее.

EDIT

В частности, просто выделите N(N+1)/2 элементов, а когда вы хотите получить доступ к [r][c] в оригинале, просто используйте [r*(r+1)/2 + c] вместо.

0 голосов
/ 23 ноября 2010

Да.

Сначала ... начните с внутреннего цикла.

"new float [2]"

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

struct Float2D {float a;плавать б;};

x = новый Float2D;

, который кажется лучше.

Но действительно, забудьте все это.Если ты хочешь это быстро ... просто выдели кучу поплавков.

Я бы сказал ... пусть некоторые поплавки пропадут.Просто выделите старый простой 2D-массив.

float * f = (float *) malloc (max_number_of_particles * max_number_of_particles * 2 * sizeof (float));

Единственный размер, который вы можете сохранитьэто 2-кратное сохранение размера с использованием треугольника вместо квадрата.

Тем не менее, я чертовски уверен, что вы уже УБИЛИ все это «сохранение размера», используя «new float [2]»,и "new float * [i];".Я не уверен, сколько стоит «new», но я думаю, что это похоже на malloc, только хуже.И я думаю, что большинство malloc имеет около 8 байтов на распределение.

Итак, у вас уже есть МЕДШЕЕ, чем размер 2X, потерянный при выделении квадрата.

Кроме того, это упрощает математику.Вам нужно сделать какую-нибудь странную математику «Треугольное число», чтобы получить указатель.Что-то вроде (n + 1) * n / 2 или что-то еще:)

...