J'ai une matrice dynamique contenant des milliers d'éléments ou encore plus, afin de ne pas consommer d'une grande taille de mémoire, je peux éliminer les éléments indésirables de celui-ci (les éléments ont été utilisés et aucun besoin pour eux, de plus en plus). Le début, je peux affecter une taille de mémoire plus petite en estimant la taille maximale requise après avoir retiré les éléments à chaque fois.
J'utilise de cette façon, mais cela prend très longtemps pour finir, parfois 30 minutes! < Pré> xxx
y a-t-il un moyen plus rapide que cela?
4 Réponses :
Au lieu de retirer des éléments un à la fois, avec deux boucles pour une solution O (N 2 sup>), vous pouvez créer une seule boucle, avec une seule lecture et un seul index d'écriture. Passez à travers la matrice, copier des articles comme vous allez: int rd = 0, wr = 0;
while (rd != size_of_array) {
if (keep_element(array[rd])) {
array[wr++] = array[rd];
}
rd++;
}
Il semble que vous fassiez essentiellement
int y;
for (y = 0; y<size_of_array; y++){
array[y] = array[y+numbre_of_elements_to_remove];
}
Et avec le tien. Si vous exécutez votre boucle en tant que telle, vous arriverez à Y == Taille_of_array - 1 Essayer d'accéder à Array [Y + Number_Of_Elements_TO_REMOVE] qui traite d'accéder au passé des limites Dès que number_of_elements_to_remove> 0 .
Comme je me suis remarqué, vous ne voulez que supprimer uniquement des éléments du début de la matrice, essayez ceci: de cette façon que vous utilisez un pour la boucle qui réduit la complexité beaucoup
Voici le code pour défragmenter la matrice.
int remove_element(int*from, int total, int index) {
if(index != (total-1))
from[index] = from[total-1];
return total; // **DO NOT DECREASE** the total here
}
Je ne comprends pas l'exemple.
Sauf si je suis erroné sur votre exemple de code, X n'est utilisé nulle part dans l'indexation de la boucle ou du tableau, alors quel est le point?
Qu'est-ce que vous voulez faire? Est-ce que vous souhaitez effacer les données dans certains éléments du tableau ou souhaitez-vous réduire la mémoire en supprimant définitivement les blocs indésirables?
Avez-vous testé ce code (sur des intrants plus petits)? Est-ce que ça marche comme vous avez l'intention?
Il existe deux possibilités IMHO: allouer un autre tableau pour les valeurs souhaitées, les copier uniquement, puis annouez l'ancien tableau; ou utiliser une liste liée.
Une solution consiste à faire "une gamme de pointeurs à des données" au lieu de "une gamme de données", et chaque élément est rempli de mémoire allouée dynamiquement. De cette manière 1) une exigence de continuité de la mémoire est détendue, une allocation est donc plus susceptible de réussir dans un pool de mémoire fragmenté; 2) la matrice elle-même est plus petite alors la redimensionnement est moins chère; 3) Ou vous n'avez même pas besoin de le redimensionner car votre cas d'utilisation est "rétrécissant seulement", vous pouvez donc simplement annouer le pointeur, puis vous attribuer null à celui-ci pour la marquer non valide.