Comment accélérer l'allocation de mémoire pour la matrice triangulaire 2D en C++?

Question

J'ai besoin d'allouer de la mémoire pour un très grand tableau qui représente une matrice triangulaire. Je écrit le code suivant:

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

Le problème est que le temps nécessaire pour le faire (pour allouer la mémoire) augmente rapidement avec la taille croissante de la matrice. Est-ce que quelqu'un sait une meilleure solution pour ce problème?

Merci.

Answer 1

Affecter un tableau unidimensionnel et convertir les indices en indices et vice versa. Une allocation par rapport aux allocations O(N) devrait être beaucoup plus rapide.

EDIT

Plus précisément, juste allouer N(N+1)/2 éléments, et quand vous voulez accéder [r][c] dans l'original, juste accéder à la place [r*(r+1)/2 + c].

Answer 2

Oui. Commencez par votre boucle interne. Commencez par ... commencer par ... votre boucle interne.

« nouveau flotteur [2] »

qui alloue un tableau, que j'imagine est plus lente à affecter qu'un objet de taille fixe qui arrive à avoir 2 flotteurs. Struct Float2D { float a; flotteur b; };

x = nouveau Float2D;

cela semble mieux.

Mais vraiment, oublie tout ça. Si vous le voulez vite ... juste un tas de flotteurs.

Je dirais ... que certains flotteurs soient gaspillés. Juste allouer un tableau 2D simple. Float * f = (float *) malloc (max_number_of_particles * max_number_of_particles * 2 * sizeof (float))

La seule taille que vous pouvez économiser, c'est une taille de 2x en utilisant un triangle au lieu d'un carré.

Cependant, je suis sacrément sûr que vous avez déjà TUÉ cette "sauvegarde de taille" entière, en utilisant "new float [2]", et "new float * [i];". Je ne sais pas à quel point les frais généraux de "nouveau" sont, mais j'imagine que c'est comme malloc sauf pire. Et je pense que la plupart des mallocs ont environ 8 octets d'overhead par allocation.

Donc, ce que vous avez déjà est pire qu'une taille 2X perdu en allouant un carré.

De plus, cela simplifie les calculs. Vous auriez besoin de faire un peu de maths «nombre triangulaire» pour obtenir le pointeur. Quelque chose comme (n + 1) * n/2 ou quoi que ce soit :)