J'ai une matrice entière qui doit agir comme un tampon:C: moyen astucieux de "décaler" une matrice?
x = {{0, 0, 0, 0, 0}, {1, 1, 1, 1, 1}, {2, 2, 2, 2, 2}};
Maintenant, si j'ajoute une nouvelle ligne {3, 3, 3, 3, 3}, la nouvelle matrice devrait ressembler à:
x = {{1, 1, 1, 1, 1}, {2, 2, 2, 2, 2}, {3, 3, 3, 3, 3}};
est-il une manière intelligente de faire ceci sans copier tous les éléments autour?
Qu'en est-il du fonctionnement modulo?
Si vous accédez aux éléments que matrix[x + SZ * y] vous pouvez changer à:
matrix[x + SZ * ((y + FIRST_ROW) % SZ)]. De cette manière, pour implémenter ce décalage, vous n'avez qu'à placer la nouvelle ligne {3, 3, 3 ..} où était la ligne {0, 0, 0} et incrémenter le compteur FIRST_ROW pour pointer vers la nouvelle ligne de départ.
Nice, merci! Cet endroit est plein de gens créatifs. :-) –
+1 basé sur la spécification supplémentaire dans les commentaires à la question d'origine, c'est probablement l'alternative qui donnera les meilleures performances. –
Je l'ai maintenant implémenté et ça marche bien. Merci encore, et merci les gars pour toutes les autres réponses! –
Utilisez une liste chaînée.
struct node
{
int row[5];
struct node *next;
};
Ajout d'une ligne est aussi simple que la marche de la liste à l'extrémité, puis en remplaçant le pointeur NULL suivante avec un nouveau noeud (dont le pointeur suivant est NULL).
Cela fonctionne pour l'algorithme, mais ne donnera-t-il pas des résultats extrêmement lents lorsque vous faites des choses avec la matrice? – alternative
Cela dépend de ce que vous faites avec. Si vous ne prolongez pas votre matrice tout le temps, vous feriez probablement mieux d'absorber le mémcpy occasionnel. – nmichaels
Notez que dans la question la nouvelle ligne n'est pas "ajoutée" à la matrice, mais remplace plutôt la 1ère ligne. Donc, si vous choisissez la solution de liste liée, assurez-vous d'annuler votre premier élément dans la liste. – ysap
Pouvez-vous incrémenter x afin qu'il pointe vers la deuxième ligne, puis libérer la première rangée? Évidemment, vous devrez allouer une ligne à la fois, ce qui ne garantira pas que la matrice est contiguë. Si vous en avez besoin, vous pouvez allouer un gros bloc de mémoire pour contenir votre matrice, puis éliminer les parties inutilisées lorsque vous atteignez la fin.
Si votre matrice est définie comme int ** et que vous allouez séparément chaque ligne, vous n'aurez plus qu'à échanger les pointeurs de ligne.
Cela semble bien. J'ai vraiment besoin d'apprendre à penser plus orienté pointeur. :) –
Le seul problème est que contrairement à la solution de liste chaînée proposée ailleurs, vous devez pré-allouer des pointeurs sur le nombre maximum de lignes que vous aurez. Sinon, c'est un moyen plus efficace que la liste chaînée. ** EDIT ** Je viens de remarquer que dans votre question, vous restez avec 3 lignes après l'ajout de la nouvelle ligne. Si cela est représentatif, alors la réponse de @ mikerobi vous convient parfaitement. Vous avez juste besoin de gérer vos pointeurs une fois les lignes échangées. – ysap
@ysap, l'opération O (n) occasionnelle pour augmenter le nombre de lignes, sera généralement plus efficace qu'un O (n) fréquent, pour accéder à une valeur. – mikerobi
Si vous utilisez un tableau de pointeurs vers des tableaux (plutôt qu'un tableau bidimensionnel ordinaire), vous pouvez copier uniquement les pointeurs vers des lignes au lieu de copier tous les éléments.
Et si vous êtes d'accord avec la superposition de la matrice de pointeurs, vous pourriez peut-être ajouter un nouveau pointeur à la fin et avancer le pointeur vers le "début" du tableau. Mais ce ne serait pas une bonne idée si vous souhaitez potentiellement faire ce genre de changement plusieurs fois. Et bien sûr, vous voulez vous assurer que vous avez le pointeur d'origine quelque part afin que vous puissiez correctement vos ressources.
Exemple de code paresseux pour l'écriture - vous pouvez utiliser l'arithmétique modulo pour adresser les lignes. Lorsque vous poussez une nouvelle ligne, augmentez simplement une variable de départ, ajoutez la hauteur de la matrice et modulez le résultat par la hauteur de la matrice. De cette façon, vous obtenez une matrice circulaire sans avoir besoin de copier la matrice entière et de garder le tableau matriciel compact.
Plusieurs réponses ci-dessous sont techniquement correctes, mais elles impliquent toutes des compromis différents. Pouvez-vous développer un peu votre utilisation prévue? Quelle sera la taille de ces matrices? À quelle fréquence prévoyez-vous d'ajouter une ligne, par rapport au nombre de fois où vous allez accéder aux données à partir des matrices? Allez-vous accéder à des éléments individuels de la matrice, ou sera-t-il seulement lu comme une entité entière du début à la fin? Voulez-vous être en mesure de libérer des parties de la matrice de temps en temps? Si oui, juste à la fin, ou depuis le début, ou à partir d'une rangée arbitraire? –
La matrice n'est pas grande (comme 100 éléments au total).Je vais toujours accéder à la totalité de la matrice, la "vieille" ligne peut disparaître (comportement fifo-queue), les mises à jour arrivent très souvent. –
Dans ce cas, l'approche modulo proposée par @ruslik est probablement votre meilleur pari. Juste allouer un tableau qui peut gérer la taille maximale, maintenir un pointeur vers la tête actuelle, et enrouler autour de la fin du tableau lorsque vous manquez de place. –