C++에서 2D 삼각 행렬에 대한 메모리 할당 속도를 높이려면 어떻게해야합니까?

Question

삼각형 행렬을 나타내는 매우 큰 배열에 메모리를 할당해야합니다. 나는 다음과 같은 코드를 작성 :

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]; 

문제는 그것 (메모리 할당)을 수행하는 데 필요한 시간이 빨리 행렬의 크기 증가에 따라 증가한다는 것이다. 누구든지이 문제에 대한 더 나은 해결책을 알고 있습니까?

감사합니다.

Answer 1

1 차원 배열을 할당하고 인덱스를 첨자로 변환하거나 그 반대로 변환합니다. 하나의 할당은 O(N) 할당과 비교할 때 훨씬 빠릅니다.

편집

특히, 단지 N(N+1)/2 요소를 할당하고 원래의 [r][c]에 액세스하려고 할 때, 단지 대신 [r*(r+1)/2 + c]에 액세스 할 수 있습니다.

Answer 2

예.

먼저 ... 내부 루프로 시작하십시오.

"부동 소수점 [2]"I 2 수레이 일어나는 고정 된 크기 개체보다 느린 할당 상상 배열을 할당

.

struct Float2D { float a; float b; };

x = new Float2D;

그럴 것 같습니다.

하지만 실제로 모든 것을 잊어 버리십시오. 빨리 원한다면 ... 그냥 malloc 한 무리의 수레.

나는 말하지만 ... 일부 수레는 낭비하도록하겠습니다. 일반 오래된 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 바이트의 오버 헤드가 있다고 생각합니다.

그래서 이미 정사각형을 할당하여 2 배 크기보다 손실이 큽니다.

또한 수학이 더 간단 해집니다. 포인터를 얻으려면 "삼각 수"수학을 수행해야합니다. 뭔가 (n + 1) * n/2 또는 무엇이든간에 :